脳log[20241102]

2024年11月02日 (土) [AtCoder] 今日は AtCoder Beginner Contest 378 があった。解ける問題が当たり前に解けなくて無駄に WA を重ねた。実装が下手！■A 問題 Pairing。Array#tally を使うところまでは良かったけど、同じ数が４個ある場合、２個３個ある場合と場合分けをしたのが制約に甘えている。個数を２で切り捨て除算したものを合計するのが正解。他の人の提出を見てこの式は頭が良すぎるだろうと思ったけど、なんのことはない、それが当たり前のやり方だった。作れるペアの数を数える問題なのだから。■B 問題 Garbage Collection。10 分かけました。１つの式でパッと答えを出したいと思ってあれこれやったけどだめだった。ステップを踏んで数えた。■C 問題 Repeating。問題文が難しかった。「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 を取ったあとだとどうなるか、それをどうするかと考えてみることができなかった。そういうアプローチが存在していなかった。