脳log[20250405]

2025年04月05日 (土) [AtCoder] 今日は AtCoder Beginner Contest 400 があった。３桁順位に入りたいよー。■A 問題 ABC400 Party。細かいことだしどうでもいいこだわりかもしれないけど、「テストして実行」よりも「実行してみて可否を見る」方が好み。テストと実行のあいだには無限の隔たりがあるから、テストの成功は必ずしも実行の成功を意味しない。これには鍵をかけたあとで鍵がかかっていることを確認する母の影響もあるかと思う。鍵をかけること(かけたつもり)と鍵がかかることのあいだにも隔たりがある。■B 問題 Sum of Geometric Series。一応まじめに考えようとしたんだけど、さっぱり頭が働かなかった。Ruby なのでオーバーフローを気にせずやるだけでいい。最大ケースでも TLE になる気配はなかった。あ、そうだ。なぜか今日起動した irb (1.6.2 on Ruby 3.2.2) はこれまでなかった補完と色分けが有効になっていて、極めて使いにくかった。なぜなのか。Ruby-1.8 で使っていた mp3info を Ruby-3.2 で使うために gem でインストールしたのだけど(単にコピペしただけではタグのセットはできても取得ができていなかった)、そのときに gem 自体にもアップデートがあるとお知らせされて gem のアップデートをしたというのが唯一関連がありそうな心当たり。なぜ関連があるかというと、ruby/bin/irb にこう書いてあったから。「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^n{q}^m$ を列挙してソートしておいてから、２乗して A を超えない最大のものを二分探索で探した。サンプルの１ケース目が合わなくて困っていたのだけど、これは $p^n{q}^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 が出たら……かなりつらい。固執してペナルティを重ねるか、俺は間違ってないこれが違うならもう何もわからんと投げ出すというのが自分の典型的反応。