脳log[20250728]

2025年07月28日 (月) [AtCoder] 精進。先週あった ABC416-E「Development」。Ruby で３乗が通るのは N<=300 までなんだよ、N<=500 なんて通らねーよ、とふてくされるつもりでいたのだけど、通ってしまったのだな。■提出 #67995573 (AC / 1862 Byte / 3439 ms)。制限時間は 3.5 秒です。実際のところ苦労したのは TLE ではなく WA の方だった。空港に対応した超頂点の扱いが難しかった。勝手に追加した頂点との距離を答えに数えるわけにはいかないのだけど、クエリ３に答えるための距離の総和を差分更新しないと間に合わないこととあいまって、答えを合わせるのが非常に難しかった。適切な場所に差分の更新をばらまくこと、超頂点との距離は差分更新から除外すること、処理時間を気にしながらこれを適切にこなさなければいけない。■提出 #68014713 (TLE×1 / 932 Byte)。オーダーで考えるとクエリ３に答えるのに N^2 の時間を使っても許されるはずなんだけど、実際にやってみると定数倍の関係で random_27.txt というケースが通らなかった。総和を差分更新するコードをばらまくしかないらしい。■提出 #68015824 (AC / 1056 Byte / 3369 ms)。クエリ１とクエリ２の処理を共通化することでよく似た２つのコードブロックが１つになって、総和を差分更新するコードも２行だけにできた。これには別の理由の助けもあって、クエリ３に答えるのに線形時間を費やすのを許すことで、超頂点と他の頂点を区別せずに差分更新が行えるようになっている。超頂点と他の頂点の扱いを分けたことで最初の AC が出るまでに WA を多数出して苦しんだので、クエリ３にちょっとした時間を使うことで頂点の扱いを共通化できたのは重要。時間に余裕さえあれば短く素直な処理を書いて済ませられるところ、定数倍のせいで難易度が増している事実がある。この２つ目の AC が出るまでにもですね、２か所まで減った差分更新が必要な部分のうち１つが漏れていてサンプルが合わなかったということがありまして、本当はクエリ３に答えるのに差分更新をしたくないんです。■C++ では気にする必要がなくて Ruby には影響することとして、入力の K が 0 になりうるということがある。K=0 のとき D_1...D_K という入力行は空行として存在するのか省略されるのか。どうやら空行として存在しているようだった。C++ の cin を使った入力はスペースと改行を区別せずに変数の型に対応したトークンをひとつひとつ読んでいくけれど、Ruby の場合は１バイト、１文字、１行、特定バイト数、全部読むのどれかになるので、いきおい行指向の処理になりがちで、空行の有無に左右される。空行は存在した。ちなみに、「行」というのは概念的な存在で、引数として改行として扱う文字を与えることで各種文字を区切りとする行を単位に読み込むことができる。でもスペースもしくは改行を区切りとする行は扱えなかったんだな。■解法の本丸であるワーシャルフロイド法の差分更新について。今更書く意味もないけど一応。自分にも初めてのときがありました。超シンプルな３重ループが特徴的なアルゴリズムだけど、最外ループが中継点だというのがひと目ではわからないところ。真ん中と最内ループはそれぞれ始点と終点を表しているけれど、これは交換可能なので、重要で交換不可能なのは最外ループ。辺を追加した状況をワーシャルフロイド法に当てはめると、辺が x-y を繋いでいるとして、中継点を x-y に固定して始点と終点を総当たりすることで新しい辺を使った最短経路が反映できる。だから更新が N^2 で済む。Ruby の場合は定数倍が厳しいので、無向辺であることを利用してループの回数を半分の N*(N-1)/2 にしないといけない。そしてこれだけでは足りないのでさらに小細工を弄するのだけどそれは別の話。二重の配列参照を繰り返すのでなく最初の参照結果を変数に保存するとかのしょうもないことだよ。三重ループの一番内側をシンプルにするのが一番効くのでまずはそこから。そしてループをスキップする判断はできるだけ早く外側で。