AtCoder Beginner Contest 456（Promotion of AtCoder Career Design DAY）

　Eまで解いたが、Eは分からず、時間をかけて無理矢理嘘解法を通した。レートが1800を割ってしまった。

コンテストへのリンク

コンテスト後のツイート

E N*W頂点のグラフにした後、サイクルの検出方法が分からなかった。WAが三つ出る嘘解法とTLEが三つ出る嘘解法を思い付き、組み合わせたらACはできたが明らかに嘘。
F 二つ連続で使わないことはありえないので、平方分割で解くことを考えていた。

— titia (@titia_til) May 2, 2026

E - Endless Holidays

　結局敗因はよく分からないけど、多分、サイクル検出すれば良い、と言われていたら解けた気がする。dfsしても良いし、SCCを使っても良いし、出次数が正の辺を消していっても良い。

　曜日の概念があったせいで、一般的な有向グラフのサイクル検出問題とは別の問題に見えていたことが敗因だった気がする。曜日1から始める……みたいなところをコードから消せると気付けていなかった。

　自分がどんな問題を考えているのか、もっと一般化した問題はないか、一般化したら問題は解けなくなくなるのか、といったあたりを意識したい。

F - Plan Holidays

　セグ木で解けると知ってAC。

　公式解説では、min-plus 代数などと難しいことを言っているけど、左右の端を使っているか、使っていないか、で4通り場合分けしてセグ木に乗せればOK。

　これも、セグ木で解けると気付かなかったことが敗因。

　多分、クエリが与えられて、[l,r]の範囲での答えを求めよ、と言われていたら解けていた気がする。

　その問題が解けるならこの問題も解ける、と気付くのが大事。