%D や /D で RE を出す罠もあったらしい。でも問題文にしっかり「非負整数 D」って書いてあるよ。MEX が典型なんだけど、否定で定義されると理解が１ステップどころか２ステップも３ステップも遅れるので、今日も「非負整数……非負…非負……ゼロ以上ってことね」と理解に時間を費やしていたおかげで、%D を書くときにすっと場合分けができた。所要 20 分＋１ペナ。■E 問題 Forbidden Prefix。スマートには解けなかった。結構力押し。クエリを先読みして X の集合と Y の集合をソートしておく。X の各要素について、どの Y 要素の接頭辞になっているかという範囲を二分探索で求めておく(演算は普通に String#<= と String#start_with?)。ここまでが事前準備で、クエリに沿って削除された Y 集合の範囲と、まだ削除されていない Y 集合の要素を２つの BIT で管理しながら答えていった。所要 31 分。■F 問題 Shortest One Formula。1 と 11 と 111 と 1111 の構成方法は確定している。あとは１から N までボトムアップで最短の積と最短の和を構成していった。積と和を区別しているので積と和を構成するにあたり括弧の要不要の判断が簡単にできる。また、積は a*b、和は a+b という２項演算だけを考えた。例えば a+b+c という形が最短になるというなら、それは d(=a+b) の最短と c の最短の２項を組み合わせるなどして構成することができる。和の構成は n/2 通りの総当たり。積の構成は√n通りの総当たり。終了１分前のこの提出 #65289442 の何が WA の原因か。24 行目の文字列リテラルで括弧の付け方を間違えている。それだけ！ くやちい！ ５分オーバーで AC (#65291201)。所要 43 分。■結果出た。コンテスト成績証。690 番 1665 青パフォ。F 問題がぎりぎりで通っていても 100 番 100 パフォ上がるくらいの差みたい？ E を通した時点で 40 分弱残していたのがわりと早かったのだな。じゃあ時間外でも F が解けたということが素直に喜べる。■■■F 問題。最初から積の最短と和の最短を持とうとしていたわけではない。必要がなければわざわざ分けたりはしない。最初は最短の文字列を検索して + があれば括弧で括って掛け算に利用したり、括弧なしで利用したりしようとしていた。でも (1+1)*(1+1) だったら + があるけど括弧なしで掛け算に利用できる。パースする？ それは明らかな無駄。文字列ではなく和クラスと積クラスをネストさせて最後に文字列化するのがいいでしょう。もうひとつ。ある数を積で表す方法と和で表す方法の２通りがあるとき、括弧でo の隣は無条件に . に書き換えておいた。DP をするのかな復元するのかなどうやるのかなと最初は考えていたけど、出力が必然の o か . かそれ以外の ? かということで、２通りの可能性があるなら即座に ? が決定するのだった。最終的に見つかった条件は、「? を１つ以上 o に変えるかどうか」「? を最大限 o に変えなければいけないかどうか」「(最大限 ? を o に変えるとして)連続する ? の個数が偶数か奇数か」というものだった。これで T が決まる。方針を定める時間と考えながら実装する時間で 30 分かかった。■E 問題 Reachable Set。不可能なケースがあるのかなとまず考えた。ある。サンプル２がそうなんだけど、頂点５を経由しないと頂点１と２が連結にならないので、k=2,3,4 が -1 (不可) になる。じゃあ使える辺を使ったときに 1-k までが連結かどうかを UnionFind で管理したいね。同時に、使えない辺の先に繋がっている消したい頂点の集合を管理したいね。同時にできる？ できる。14 分かけたので D の半分。■F 問題 Add One Edge 3。直径の候補は木１の直径と、木２の直径と、i-j を結んで新しくできた i-j を通る直径の３種類だと思った。木の直径は DFS ２回で求まる。新しくできる直径は、各頂点について最も遠い頂点がどれだけ遠いかわかっていればわかる。それは全方位木 DP で求まる。２回の DFS を２つの木に対して合計４回やると、２秒を超えてしまって TLE だった。なにかへまをしていて５秒 10 秒かかるようなスクリプトになっているなら惜しくはないけど、制限時間が３秒だったら通っていたというならあまりにも残念。■コンテスト成績証。ぴったりギリギリで青パフォ。973 位だから「３桁順位に入りたいよー」と書いていた前回の雪辱は果たせたけど、最近落ち目なのだから今日くらいはもっと調子に乗らせてほしかった。■■■X で予告されていたけど、955 位 1607 パフォに上方修正されていた。でもなあ、F を通して 1800 パフォが欲しかったなあ。Forbidden The server refuse to browse the page. The URL or value may not be correct. Please confirm the value. TIME: 1743945073.137446 (2025-04-06 22:11:13 (+0900)) METHOD: POST PATH_QUERY: /ds14050/diary/update.rb SAKURA Internet Inc.」 Ruby のバッククオートは外部コマンドを実行して出力を埋め込むリテラルなので、OSコマンドインジェクションが疑われているのだと思う。Ruby が疑っているのなら Ruby で書かれた tDiary を設置して実行している自分の管轄だけど、もちろんそうではないと思っている。hikidoc.rb はプレインテキストを整形するマークダウンに類するスクリプトであって、二重バッククオートにマークアップ以外の意味はないし、バグでなければ外部入力を実行したりはしない。だけど外形的にはそのように見えてもしかたがないと思うし、同時に、いいかげんなものだなと思う。
This file was generated by RubyGems. The application 'irb' is installed as part of a gem」 だけどこのファイルが更新されていたわけではない。たぶん
%USRPROFILE%\.irbrc に書き込むんだけど、どうやって色分けと補完を無効にするんだよ。……。IRB.conf[:USE_AUTOCOMPLETE] = false と IRB.conf[:USE_COLORIZE] = false を書き足して心の平穏を得た。俺は出しゃばりな機械を憎んでいる。■C 問題 2^a b^2。方針を定めるのが難しい。平方数を列挙したいと思ったけど、N の上限が 10 の 18 乗だからといって 10 の 9 乗までを列挙することはできない。それに b が 2 を含んでいるときに同じ良い整数を表す２通り以上の方法があって重複を除かなければいけない。そこで、b は 2 を含まない(奇数である)ということに決めてしまった。a を決め打ってから b の上限を二分探索で。■E 問題 Ringo's Favorite Numbers 3。扱う素数がいくつあるかをまず調べた。８万以下だった。定数倍が２分の１以下だとしても組み合わせを列挙すると２乗で厳しいなーとか考えていた。べつに厳しくはなかった。p^{2n}q^{2m} が 10^{12} を超えない範囲ですべての p^nq^m を列挙してソートしておいてから、２乗して A を超えない最大のものを二分探索で探した。サンプルの１ケース目が合わなくて困っていたのだけど、これは p^nq^n を列挙していたことが原因。p と q の指数は偶数であるという点が共通するだけで独立しているのに勝手に揃えてしまっていた。■D 問題 Takahashi the Wall Breaker。F と D を見比べて見込みがあるのは D だと思ったので一度飛ばした D に戻った。方針が立たなかったのだ。前蹴りしたはいいけど他の連結成分に合流できないケースの扱いに困っていた。それはどういう状態なのか。どの状態からやってきてどの状態へ移行するのか。どうやって現実的な時間で遷移を網羅できるのか。わからなかった。だけどグリッドの処理を書いているときに、前蹴り何回で現在のマスにいるのかを書き込んでいけばいいのだと気がついた。サンプルが有能で助かったんだけど、前蹴りで破壊される２マス目の扱いに罠がある。処理が重複する無駄があると TLE になるおそれがあるので、最短を更新したときだけ次の処理をキューに入れるのがお約束。ところが、前蹴り１マス目が最短を更新しなかったとしても、前蹴り２マス目は最短を更新することがある。前蹴りには向きがあるからこのようなことが起こる。だから前蹴り１マス目に関しては最短を更新しなかったとしても２マス目の処理を進めなければいけなかった。解けてみれば実装問題枠として置かれていたのだと思うけど、普通に考え込んでしまった。もともと大したことがなかった脳みその退行が著しい。悲しいね。自分がやっていたような精進というのは、問題に対するパターンマッチ、ヒューリスティクス、反射神経を鍛えているのであって、規模と速さにおいて決して敵わない AI に対して AI の土俵で戦いを挑む行為なのではないかと思ってしまう。自分は考えるという行為を未だ知らない。■■■Ruby の Integer.sqrt にバグが見つかっていた。「Bug #21217: Integer.sqrt produces wrong results even on input <= 1e18 - Ruby」 きっかけは ABC400 の C 問題らしい。提出 #64512377 (WA×2 / Ruby で C 問題最速の提出)。本番で絶対合ってるのに WA が出たら……かなりつらい。固執してペナルティを重ねるか、俺は間違ってないこれが違うならもう何もわからんと投げ出すというのが自分の典型的反応。