https://atcoder.jp/contests/abc204/tasks/abc204_f 前提知識 bitDP 行列累乗を使ったDP高速化 解説 https://atcoder.jp/contests/abc204/submissions/23263864 今回の問題はとても難しいのだが、典型度は高い。 まず、制約がかなりとがっているので、何を…

https://atcoder.jp/contests/abc204/tasks/abc204_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/abc204/submissions/23263588 問題設定が有向グラフの最短経路問題なので、ダイクストラ法が最初に思いつく。 ダイクストラ法をもじって解くこ…

https://atcoder.jp/contests/abc204/tasks/abc204_d 解説 https://atcoder.jp/contests/abc204/submissions/23262989 この問題はDPで解ける。 いかにDPで解くという所に帰着させるかを説明していこう。 まず、制約がとても小さい。 パッと見て貪欲で行けそ…

https://atcoder.jp/contests/abc204/tasks/abc204_c 前提知識 BFS 解説 https://atcoder.jp/contests/abc204/submissions/23261589 この問題では実装方針から正しく計算量を見積もれるかがポイントとなる。 計算量見積もりをして、オーダーで上限を当てはめ…

https://atcoder.jp/contests/abc204/tasks/abc204_b 解説 https://atcoder.jp/contests/abc204/submissions/23260128 シミュレーションする問題。要求されていることを実装しよう。 それぞれの木の実について、 10以下であれば何もしない 10より大きいならA…

https://atcoder.jp/contests/abc204/tasks/abc204_a 解説 https://atcoder.jp/contests/abc204/submissions/23259935 あいこになるのは全部同じか全部違う場合なので、その2つの状況で場合分けして答えることにしよう。 x=yであれば全部同じの場合なので、x…