脳log[20220220]

2022年02月20日 (日) [AtCoder] 今日は ABC240 があった。見たことのある問題が多かったかな(万年 ABC rated だからだよ)。■C 問題「Jumping Takahashi」。アルゴリズムと数学　演習問題集の 96 問目「Cooking」が ABC204-D と同じ問題で、すでに ABC で解いていたけどそのときの解法が思い出せなかったのでビット演算で解き直していた>提出 #29359695 (AC)。それが４日前。今日の提出もビット演算で>提出 #29519763 (AC)。気がついたけど、ほんのちょっと前の ABC-D が ABC-C として出たってことなのね。■D 問題「Strange Balls」。ぷよだと思ったけど連鎖がなくてちょっと物足りない。必要な情報をメモしてシミュレートするだけ>提出 #29524639 (AC)。■E 問題「Ranges on Tree」。問題文が難しい。３割くらい理解を投げ出しかかっていたけど、途中でもうオイラーツアーが見えていたのでそれをガイドにして(予想がついている内容が外れていないことだけを確認して)読み通すことができた。昨日の F 問題「Construct Highway」がコンテスト終了後とはいえ解けていて気力が充実しているのでなければ危なかった。適当なタイミングで数字をインクリメントするだけ>提出 #29531766 (AC)。こういう問題をもっぱらスタックを陽に持ったループで解くのは 20 万回の再帰呼び出しがローカルではスタックオーバーフローを起こしてデバッグも答え合わせもできなくなるから。ネットで読んだ方法が効かないのはなんでなの？■F 問題「Sum Sum Max」。加速度と速度と距離。それは３か月前に解いたこれ「ARC077-E「guruguru」(黄 diff)。それほど難しくはないかな。ABC-D＋α という感じ。プラスアルファで悉くつまずいて AC に辿り着けないのが自分ではあるが。(略)。時間軸に沿って加速度と加速度の累積としての速度と速度の累積としての移動距離を記録して答えにする」。極大値が見えていなかったりとりあえず代入しておいた初期値を答えにしてしまったり、逆に開始点を答えの候補から漏らしてしまったり、答えを合わせるのに大変苦労した。「プラスアルファで悉くつまずいて AC に辿り着けない」とか「区間の左右端と節約回数の上下端が off-by-one エラーを誘発しやすい感じ(ドツボにはまった経験から書いています)」を今日も再現しておかしくはなかった。早々に愚直解とランダム入力を組み合わせてダメケースの発見に努めることができたのが運命の分かれ目。終了３分前の提出 #29545375 (AC)。これ水 diff なんだって。全く同じではないにしてもかつての黄 diff が形無しですよ。