脳log[20220529]

2022年05月29日 (日) [AtCoder] 精進。昨日あった NOMURA プログラミングコンテスト2022（AtCoder Beginner Contest 253）-E,F。E と F が精進の対象だということは４完だったということ。無念なり。現実を直視できなくて結果を見ないまま今日の ARC141 に出たからね。そこで +2 だけ元気をもらって復習にとりかかりました。■E 問題「Distance Sequence」(緑 diff)。とくになんということのない DP のはずだったんだけど、最初の提出 #32032452 が TLE になった。このあと 55 分間迷路に迷い込んでいるうちにコンテストが終了していた。□今日の提出 #32096311 (AC / 727 ms)。ちょこちょこ整理した部分はあるけど本質的な差異は sk か sk%P かという違い。余りをとるコストをケチってかえって Bignum のコストを支払って TLE になっていたのだった。あほ。■F 問題「Operations on a Matrix」(青 diff)。昨日は問題を読みもしなかった。やることは明らかだけどどう効率的に実装するかという問題。□最初の提出 #32096736 は TLE/MLE になった。長さ 20 万になりうる配列を最大 20 万回複製しようとしていたのだから、40 ギガを数倍したコストが予期される。TLE/MLE も当然。□次の提出 #32097180 で AC。クエリ先読みで必要な値だけ覚えるようにした。典型です。最近では ABC202-E「Count Descendants」を解くときに同じことをした>TLE、AC。E 問題を AC してから 50 分だから、%P を %P とタイプするだけの手間で E 問題を AC に持って行けていれば６完もありだった。幸せな皮算用。