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という文字列があるかどうかを判定してもいい。 好きなよ…

https://atcoder.jp/contests/zone2021/tasks/zone2021_e 前提知識 ダイクストラ 解説 https://atcoder.jp/contests/zone2021/submissions/22237607 ダイクストラをする。遷移についてそのまま実装したら通ってしまった。 本番解法 https://atcoder.jp/conte…

https://atcoder.jp/contests/zone2021/tasks/zone2021_d 解説 https://atcoder.jp/contests/zone2021/submissions/22237589 実装問題であるが、一部実装を工夫しないとTLEする。 Tを反転させる 反転操作は時間がかかるので、文字列をなるべく反転させないよ…

https://atcoder.jp/contests/zone2021/tasks/zone2021_c 前提知識 二分探索 解説 https://atcoder.jp/contests/zone2021/submissions/22237545 二分探索で解く。 この部分に気が付くのが第一関門だが、自分もやっとやっと気が付いたので考察過程が共有でき…

https://atcoder.jp/contests/zone2021/tasks/zone2021_b 解説 https://atcoder.jp/contests/zone2021/submissions/22237510 この問題は数学的な知識が要求される。 自分は大学時代に塾講師をしていたので、似たような問題を死ぬほど中学生に教えた経験が競…

https://atcoder.jp/contests/zone2021/tasks/zone2021_a 解説 https://atcoder.jp/contests/zone2021/submissions/22237494 文字列を抜き出してきて比較をするというのを抜き出す文字列の先頭を変えながら試していく。 C++のsubstrでは指定文字数に足りない…