https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_g 解説 https://atcoder.jp/contests/ttpc2019/submissions/7237908 操作は逆に行うこともできるので、問題の言い換えができる。 「操作をちょうどK回行うことで、文字列Tを何種類の回分にできるか」 …

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_h 前提知識 動的構築セグメントツリー マージテク 解説 https://atcoder.jp/contests/ttpc2019/submissions/7238575 まずは簡単なことから考えていく。 条件を見ると支援関係は連結成分ごとに考えられ…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_c 解説 https://atcoder.jp/contests/ttpc2019/submissions/7225833 自明な場合分けとして、欠損したものがなければ、XORをとって、Xと一致するかを見ればいい。 0≦ai≦Xであるという条件がなければ、欠…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d 前提知識 grundy数 解説 https://atcoder.jp/contests/ttpc2019/submissions/7225749 以下、grundy数の理解が必須。 太字のルール「一度に取ることができる石の数は素数個で、かつその山の残る石の数…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_b 解説 https://atcoder.jp/contests/ttpc2019/submissions/7225374 各文字列について、それぞれ判定をする。 判定については、「okyo」となる先頭と「ech」となる先頭を全探索する方法で行った。 okyo…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_a 解説 https://atcoder.jp/contests/ttpc2019/submissions/7225294 計算を頑張る。 周期cycle=B-Aである。 B, B+cycle, B+cycle*2, ...のようになるが、Tのままだと扱いにくい。 そこで、T-Bとしてお…

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_f 解説 https://atcoder.jp/contests/ttpc2019/submissions/7237707 有向グラフで最小コストなので、とりあえずダイクストラか。 グラフはDAGなので、ダイクストラというよりDPできそう。 いつものトポ…