Ai と等しい要素が i の直前に出現した位置を Bi とする」とあったが、等しい要素を A 数列から探すのか B 数列から探すのかわからなくてフリーズしてしまった。サンプルで理解したけども、読み飛ばして「
より正確には」以下を読むのでも理解できた。だけどそこまでたどりつかずにぐるぐるとスタックしてしまった。わかれば値の範囲を見て Hash でメモ。■D 問題 Count Simple Paths。計算量で難しさを出してくるのが D 問題というイメージなので、愚直 DFS が通るのは甘々です。だけど BFS は書けるけど DFS はなんか苦手という時期が自分にもありました。■E 問題 Mod Sigma Problem。解けてないよ。６問解く実力がなくて F 問題が 25 点だけ上なら F 問題を先に解かない理由がないよ。■F 問題 Add One Edge 2。単純グラフというのは自己辺なし多重辺なし。単純グラフというのは自己辺なし多重辺なし(２回目)。問題文を読んでるときにこの通りに補完しているが、ABC なんだからそこまで書いてもいいと思うんだよね。知らなきゃ解けないという問題は門前払いされたようで面白くないよ。それが概念でなく単なる言い替えレベルの用語がどう定義されているかというだけのことであればなおさらしょうもなくて面白くない。次数２の頂点同士を結んでその LCA までのパスがすべて次数３であるか、LCA が次数２の頂点の一方であるかという場合を数える。とにかく実装が下手だった。WA (隣接している次数２の頂点を結んでしまっていた。それは多重辺)、WA (葉を刈り取る DP をしているのに処理順が LIFO だった。20241019と同じミス。手癖で書いてるんじゃないのよ。pop かな shift かな pop でいいよねと考えた結果なのが救われない)、WAWAWA (葉を刈り取る DP をしているのだから、１を仮の根としたときの親に処理を流すのは間違いなのよね。この場合の根とは最後まで残った１ノードのことなのだから。一番深いところから積み上げる DP なら間違いではなかったし、脳内イメージではそうしていたんだけど、実際にやってることがちぐはぐだった)、AC (再帰関数で再実装したら AC だった。だって何度問題を読み直してももう考えることが残っていなかったので、原因がわからなくても実装が悪いことが明らかだった)。■レートは横ばい。デバッグとペナルティで失った 50 分が痛い。■■■精進。E 問題。累積和とか転倒数とか BIT とかのワードを見かけてもいまいちピンときていなかったが、ある動画でエスアールヒクエスエルが負と聞いてやっとやるべきことがわかった。それを正しくやるのにも散々迷走して凡ミスをして苦しむんだけど。提出 #59430244 (AC)。■■■精進。水 diff ながら抜けていた ABC221-E LEQ。さっきの E 問題を解いたあとだと普通に解ける気がして、普通に解けた。提出 #59440817 (AC)。ABC378-E とは類題ってことでいいのでは？ 自分は感覚とかイメージとかのふわっとしたもので問題を解いているので(○○の△△は二分探索(を疑う)みたいなトリガーを記憶しておくことも適切に引き出すこともできなくて、二分探索の雰囲気がするから二分探索をしている。例「二分探索っぽさがあるよね」)、式を操作したり式を見て糸口を見つけるということが苦手というか、まったくアプローチができていない。そういう苦手を突くという点で類題だと思った。この問題では２の冪乗というものについて、足し合わせてみたり、足し合わせたものをまとめて割ったりするとどうなるかな、何の問題もなく個別に計算したのと同じ結果が手に入るなということを確認するだけで解答が書けた。昨日まではそれができなかった。ある範囲の連続部分列の和が Sr-Sl であると、それが mod を取ったあとだとどうなるか、それをどうするかと考えてみることができなかった。そういうアプローチが存在していなかった。