HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

HHKB プログラミングコンテスト 2022（AtCoder Beginner Contest 235）　Eまで五完
C dictに突っ込んだ
D DP
E クエリごと重み順にソート
F どう見ても桁DPだが混乱してしまい解けず

— titia (@titia_til) January 15, 2022

F - Variety of Digits

　桁DP。

　コンテスト中は下の桁からやろうとしたが、上の桁からの桁DP（そこまで一致しているかのflagを持つやつ）を書いたらいけた。

　下の桁からでもできるかもしれないけど、そうやろうとして混乱するくらいなら上の桁からやった方が良いかね。

G - Gardens

　解説AC。

　包除原理＋二項係数の和の高速化。

　どちらも無理な発想という感じはしないので、ちゃんと時間をかけたら解けたかもしれない。ただ、コンテスト中は包除原理を全然考えなかったので、厳しかったかも。

Ex - Painting Weighted Graph

　解説放送を聞いてAC。

　最小全域木＋二乗の木DP（の亜種）。

　これも、まあまあ自然な発想を重ねれば解ける問題という気はした。最初の問題の見た目からは、二乗の木に行きつくとは想像し辛いので難しい。

　ただ、DPの遷移式を立てるところは難しい。これで良いはず……と思ってからWAをたくさん出してしまった。