脳log[20240217]

2024年02月17日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#2（ABC341）があった。C 問題難しすぎ。では ABDEF のふりかえりを。■A 問題「Print 341」。問題文が意図的に不親切だけど、曖昧ではないので、指示された通りに出力する。■B 問題「Foreign Exchange」。0 から N-1 まで順番に処理する DP。■C 問題「Takahashi Gets Lost」。500 の３乗を計算してみて不穏な気配はあった。制限時間が長めの３秒だけど足りない。しかし Ruby で通すのが不可能というわけではないらしく、１秒、２秒、３秒程度で通している３つの提出がある。だったらしかたないね。想定解が愚直シミュレーションだとしても、それがだめなときに選ぶプランＢを持っていないのが悪い。F を通したあとに 15 分残っていたら慣れない C++ で書き直したけども。Crystal を使わないのはね、処理系がインストールできないからなんだよね。Windows Vista にどうやったらインストールできるんだろう。Rust もできなかった。■D 問題「Only one of two」。二分探索。最初なぜか二分探索を２段階に分けて実行しようとしていたんだけど、２段階目を書いているときにそれがそのまま１ステップで答えを出せることに気がついた。無駄に時間を使ったね。■E 問題「Alternating String」。反転する区間の内部では操作１の前後で状態は変わらない。BIT などで境界部分の状態を記録すると、ある範囲の境界状態の累積が対数時間で取得できる。添字でバグらせてペナルティ 10 分。■F 問題「Breakdown」。残り 10 分ぐらいで一応の解答が完成したんだけど答えが合わない。条件の２つめ「x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、∑y∈S​Wy​<Wx​ であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く」のシグマを見落としていて、Wy<Wx なるすべての y∈S にコマを配置できるものだと思っていた。残り 10 分でこの思い違いは厳しいが、幸いにもある頂点を選ぶ選ばないの愚直２乗 DP が許されていたので間に合った。うれしい。何番目まででいくつ選んだときの最大がいくつという DP が求められていたら無理だった。解法は、W が小さい頂点から順番に答えを計上する。それは配置されているコマ数×倍率。倍率を決めるために W が小さい頂点から順番に DP をしているし、ある頂点の倍率を決めるためにも W 未満の範囲でまた DP をしている。■自分のすべての提出。C 問題が解けていないことを除けば上出来。コンテスト成績証。1400 に復帰しました。1500 にもう一度のせて青を窺いたいところ。■C 問題。提出 #50395575 (C++ / AC / 637 Byte / 93 ms)。提出 #50396690 (Ruby / AC / 259 Byte / 66 ms)。Ruby が速すぎる！ コンテスト中にこれが通せないのはお前が抜けてるからだってはっきりわかんだね。■C 問題。Ruby で最初の AC であるこちらの提出 #50356929 を見ると、18 行目の uniq! がポイントかなと思った。自分の TLE 提出である #50356164 が３行目でやってる文字列置換も目的は同じだけど、やり方が拙くて不十分。自分は経路の冗長性を取り除こうとしているが、経路をたどった結果の到着点の重複を取り除くことで冗長性を除くべきだった。だけどそのときは方法が思いつかなかったんだよ。理由もわかる。重複を取り除くためにはいったん配列などに溜めて並べて比較する必要がある。だけど自分の解答の構成はループを回して逐次的に移動先を更新していた。同時には１つの到着点しか存在していないのだから、それらを比較して重複を取り除くという発想が自然には出てこない。全体を俯瞰して最適な構成を考えることができなかったのは、問題の理解が浅かったからにほかならない。残念だね。