https://atcoder.jp/contests/abc140/tasks/abc140_b 解説 https://atcoder.jp/contests/abc140/submissions/7443466 シミュレーションしていこう。 前に食べた料理の種類を記録しておけば、満足度Ciを得られるかどうかが分かる。 int N, A[20], B[20], C[20…

https://atcoder.jp/contests/abc140/tasks/abc140_c 解説 https://atcoder.jp/contests/abc140/submissions/7443482 なるべくA[i]を大きくするように考えたい。 A[i]中心に考えてみると、A[i]≦min(B[i-1],B[i])を満たす必要がありそう。 最大化したいので等…

https://atcoder.jp/contests/abc140/tasks/abc140_a 解説 https://atcoder.jp/contests/abc140/submissions/7443443 各桁についてN通りの候補があるため、答えはNNNになる。 つまり、N3を答えよう。 int N; //--------------------------------------------…

https://atcoder.jp/contests/abc139/tasks/abc139_c 解説 https://atcoder.jp/contests/abc139/submissions/7338829 全探索を考える。 始点を全探索して、右側にどれだけ移動できるかを確かめると、O(N2)で解が求まる。 例えば、「6 5 4 9」 となっていて、…

https://atcoder.jp/contests/abc139/tasks/abc139_e 解説 https://atcoder.jp/contests/abc139/submissions/7339484 全くいい方針が思いつかない。 AtCoderなので、貪欲法かもしれない。 先頭から順番にペアでとってこれる場合はとってくる動作を繰り返せば…

https://atcoder.jp/contests/abc139/tasks/abc139_d 解説 https://atcoder.jp/contests/abc139/submissions/7339048 Nの上限が109なので、Nに起因するアルゴリズムではなさそう。 それで400点ということもあり、特殊な解法が存在するっぽい。 という訳で実…

https://atcoder.jp/contests/abc139/tasks/abc139_f 前提知識 幾何問題 解説 https://atcoder.jp/contests/abc139/submissions/7340335 頂点全てを偏角ソートすると、最適な組み合わせは、連続する区間の頂点を選んで選択することである。 言われてみればそ…

https://atcoder.jp/contests/abc139/tasks/abc139_a 解説 https://atcoder.jp/contests/abc139/submissions/7338689 各文字について一致していれば答えのカウントをインクリメントする。 結果を答える。 string S, T; //----------------------------------…

https://atcoder.jp/contests/abc139/tasks/abc139_b 解説 https://atcoder.jp/contests/abc139/submissions/7340535 B口以上に拡張と問題にはあるが、すでに1口はあるので、B-1口増やしたいという問題で考える。 電源タップを1つ使うと、1つの口がA個に増え…

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できそう。 いつものトポ…