脳log[20240921]

2024年09月21日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2024 秋（ABC372）があった。脳みそがスポンジ化している。このごろは最初に問題をざっと読むんだけど、E までは普通に解けると思って、F 問題に時間をかけて考えて解けるかどうかだと見通しを立ててから A の実装に取りかかった。番狂わせの D 問題。E 問題を終了 20 秒前に提出するのがやっとだった。■A 問題「delete .」。String#tr メソッドは文字の削除もできます。つい最近他の人の提出で見るまで知らなかったけど、String#delete というメソッドもあります。■B 問題「3^A」。N が出力の制約だと気がつくまで時間がかかった。10 万個の数字を出力してもいいんですかと確かめるつもりで問題とサンプル(の上の方)を眺めてもまだわからなかった。制約さえ把握できたらあとは３進数。Integer#digits メソッドは基数を引数に取る。■C 問題「Count ABC Again」。つどカウントするわけにはいかないから、置換前に ABC の一部であればカウントを１減らし、置換後に ABC の一部であればカウントを１増やす。これも実装で下手をして答えが合わなかった。クエリの x を２回使うので、x を変更するのではなく別の変数にコピーしてから変更していたのだけど、最後に別の変数を参照するところで x を使用していた。■D 問題「Buildings」。来ました D 問題。21:26 に C 問題を提出してから 22:25 に D 問題を提出するまでほぼ１時間ぐだぐだやっていた。問題が全然頭に入ってこないの。いったい何を数えるんだよー。問題を完全に理解したのが 22 時 20 分！ 理解したら実装は５分。「ビル i とビル j の間にビル j より高いビルが存在しない」という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ。サンプル１の解説とサンプル１の出力例を突き合わせて自分の理解の誤りが明らかになったのが 22 時 20 分だったのだ。出力形式もやっかい。合計じゃないんだよ、さりとて j を基準にした数字でもないんだよ。問題を解く筋道を規定されるようでとことん振り回された。解法は後ろから見ていって増加列の列を管理する。いや……ただの増加列なのか。無駄なことをしたかも。■E 問題「K-th Largest Connected Components」。一読してスター型のグラフに殺されるなどうしようかなと考えたときに k が 10 以下との制約が目に入って解けたと思った。連結な頂点のことを隣接頂点だと勘違いしていたのに気がついて途中で UnionFind を(頭の中から)ひっぱり出してきた。連結な頂点に自分自身を数えることも最初はわかっていなかった。Array#max メソッドの戻り値がソート済みではないと知らなかった。そんな感じで実装に 15 分。D 問題のせいで解ける E 問題を落とすのは悔しすぎるので残り 20 秒で間に合って良かった。■F 問題「Teleporting Takahashi 2」。30 分から１時間を残してじっくり考えたかったけど、すべては D 問題のせい。■F 問題。K×N の表を作成していて、K と N がどちらも大きいんだけど、k 行目の値を決めるのに斜めに k 項の和が欲しい。k の２乗はダメだ。左にあって一番近い意味のある頂点が t 個前にあるとして、k-t 番目の値を参照すればいいのかな。■■■F 問題。TLE×8、TLE×27、TLE×12。なんで最初が一番ましなのか。最初だけ送っていて、あと２つはもらっている。TSP 問題ではもらう方が速いのだけど、逆に遅くなる理由がどこにあるのかわからない。■AC！ でも Ruby の他の提出では全部で４つの AC がいずれも 1500 ms 前後しかかけていない。自分のはやっとで 2055 ms。25 % 遅い。正直なにが AC と TLE を分けたのかもわかっていない。他の人の提出を読んだ(眺めた)けど、なんか遷移がシンプルだよね。DP のために用意する配列のサイズが N+K だったり N から継ぎ足して N+K だったり、最初から最後まで N だったりもする。自分は 2M×K の２次元配列(※)を使った。明らかに何かが違って効率が悪い。むむむ。※ C 言語では２次元配列と配列の配列(jagged array)を区別するけど、Ruby には片方しかないので……。■たぶんだけど、ある頂点の場合の数を記録している添字をずらしていくことで１つ先への移動をノーコストで行うんだと思う。初期にはそういうことも考えていたけど、移動したら移動元には場合の数が残らないはずなのに、考え違いをしていて一歩ずつ加算していかなければいけないような気がしていた。今日も実装を始めたときにはまだその勘違いをしていて、過大な答えが出たりしていた。勘違いで解法を潰してしまっていた。提出 #58036342 (AC / 1430 ms)。ほらね、1500 ms グループの仲間入り。提出の中でなんで y から x を引いてまた x を足してるのかはわかりません。差分が生きるような気がしたけど、気の迷いだった。