モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 238）

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

D a & (s-a)==aならYesかなー、と未証明で出したら通った。
E グラフの問題にする。最初、「全要素を決定できるか？」と誤読して悩んでいた。
F トポロジカルソートして木DPみたいなことをするのか？　と考えてたけど解説を見たら違ったみたい。

— titia (@titia_til) February 5, 2022

F - Two Exams

　「ソート」というキーワードを見てAC。

　$P_x>P_y$かつ$Q_x>Q_y$を満たす$(x, y)$の組は少ないから、とりあえず列挙してグラフの問題にしようか、と考えると難しい。

　トポロジカルソートを使うのかな、などと考えてしまいやすい。ツイッターを見ても、同じ罠にハマった人は多かったよう。

　二次元平面に$(P_i, Q_i)$をプロットして平面走査っぽく考えてみると、ソートしてDPという方針が自然と思い浮かぶ。

　一般化しすぎて解けない問題に帰着してはダメ。今回は特に、一見解けそうに見えるからハマりやすかったんだと思う。

　解けないかも？　と気付く嗅覚（知識）と、もう一度元の問題を振り返ることが重要。

G - Cubic?

　解説放送を見てAC。

・区間→累積和（今回は累積積）を考える

・ハッシュ化

　と考える問題で、ハッシュ化の仕方が難しい問題だったはずだが、コンテスト中は一点目で詰まっていた。セグメント木でどうにかならないかと考え、もっと簡単な累積和でどうにかできると気付けなかった。