https://atcoder.jp/contests/past202012-open/tasks/past202012_o 前提知識 平方分割 解説 https://atcoder.jp/contests/past202012-open/submissions/22306825 平方分割ではないかもしれないが、雰囲気は似ているのでとりあえず入れておく。 かなりテクニ…

https://atcoder.jp/contests/past202012-open/tasks/past202012_n 解説 https://atcoder.jp/contests/past202012-open/submissions/22304844 クエリ先読みをして解く。 特定のクエリ問題では、クエリを一度にまとめて計算することで計算量の改善を図るもの…

https://atcoder.jp/contests/past202012-open/tasks/past202012_m 前提知識 セグメントツリーを利用したdp高速化 二分探索 累積和 解説 https://atcoder.jp/contests/past202012-open/submissions/22299599 複合的な問題。 しかも、二分探索+セグメントツリ…

https://atcoder.jp/contests/past202012-open/tasks/past202012_l 前提知識 区間DP 解説 https://atcoder.jp/contests/past202012-open/submissions/22298486 区間DPで解くことができる。 なぜ区間DP感があるかというと、削除できる領域を考えてみると、ど…

https://atcoder.jp/contests/past202012-open/tasks/past202012_k 前提知識 bitDP 期待値DP 解説 https://atcoder.jp/contests/past202012-open/submissions/22325031 考え始めが難しい問題。 ここがまず重要であるが、全体の状態を考えると216通りしかない…

https://atcoder.jp/contests/past202012-open/tasks/past202012_j 解説 https://atcoder.jp/contests/past202012-open/submissions/22292068 このような問題を初見で解くのはかなり難しい。 今回の問題で重要なのが「やや再帰的な構造を持っている」という…

https://atcoder.jp/contests/past202012-open/tasks/past202012_i 前提知識 bfs 解説 https://atcoder.jp/contests/past202012-open/submissions/22291597 標高が設定されているが、計算途中に変化したりはしないので、水路と標高を合わせて 有向グラフと考…

https://atcoder.jp/contests/past202012-open/tasks/past202012_h 前提知識 bfs 解説 https://atcoder.jp/contests/past202012-open/submissions/22291073 今回の問題は到達性判定問題といえる。 この手の問題はbfsでの解法が有名であり、今回もbfsで解けな…

https://atcoder.jp/contests/past202012-open/tasks/past202012_g 解説 https://atcoder.jp/contests/past202012-open/submissions/22290363 一筆書きを探す問題。 制約がかなり小さいので全探索で一筆書きを探すことができる。 制約の小ささから全探索は思…

https://atcoder.jp/contests/past202012-open/tasks/past202012_f 解説 https://atcoder.jp/contests/past202012-open/submissions/22284174 制約を見ると、薬品の混ぜ方が全探索できることが分かる。 これは薬品の混ぜ方は214通りであるためである。 ビッ…

https://atcoder.jp/contests/past202012-open/tasks/past202012_e 解説 https://atcoder.jp/contests/past202012-open/submissions/22282335 実装問題。 要求されていることがかなり複雑なので、適度にモジュール化しないと混乱するかもしれない。 特に目立…

https://atcoder.jp/contests/past202012-open/tasks/past202012_d 解説 https://atcoder.jp/contests/past202012-open/submissions/22281196 特殊なソートが要求される問題。 C++ではソート関数を指定したソートを実装できる機能があるので、それを使ってソ…

https://atcoder.jp/contests/past202012-open/tasks/past202012_c 解説 https://atcoder.jp/contests/past202012-open/submissions/22280794 10進数から他の進法への変換アルゴリズムをそのまま適用する。 36進数になるので、36で割った余りを下から文字列…

https://atcoder.jp/contests/past202012-open/tasks/past202012_b 解説 https://atcoder.jp/contests/past202012-open/submissions/22280373 実装問題。 N≦100なので、基本的にはどのような実装をしてもTLEにはならないと思う。 それにかまけて雑な実装で通…

https://atcoder.jp/contests/past202012-open/tasks/past202012_a 解説 https://atcoder.jp/contests/past202012-open/submissions/22280007 実装問題。 連続しているかを判定してもいいし、ooo,xxxという文字列があるかどうかを判定してもいい。 好きなよ…