Codeforces Round #608 (Div. 2)のA~Dまでをやりました。
Eはもう少し考えてからやってみます。
バチャおつです
— やまけー (@yamake_cpp) 2020年10月8日
A: 1番目のスーツと2番目のスーツのどちらかを先に売れるだけ売って、残った方を売り切る。先に売る方を両方調べる。
B: 白と黒の偶奇を調べて、どちらかが偶数ならok。全部白 or 黒にする構築は左から貪欲。
C: 出店すべき場所は{sx, sy}の上下左右どれかのマスのみなので全部調べる
D: 前から兵士を何人連れていけるかを累積和して、後ろから兵士が何人余るかを見ていって適切に割り振る。
— やまけー (@yamake_cpp) 2020年10月8日
A問題で、両方試してしまいましたがと
を比べれば十分でした。
B - Blocks
となる
について、
となるように
を選択していくと
両方の色を反転させることができます。
したがって、例えば白いマスが偶数個のとき
白いマスのペアを左から順に消していくことで答えを得られます。
黒いマスが偶数個のときも同様です。
C - Shawarma Tent
実は候補は学校に隣接する4マスしか無いので、全部のマスを調べられます。
D - Prtals
前から城を攻略したあとの兵士の合計人数を配列
などに保存します。
次に、後ろから見ていって「城を攻略したあとに城
を攻略するのに余る人数（つまり
）」を適当な配列
に保存します。
後ろから見ていって、]となる
が現れたとき
番目以降に防衛できる城を貪欲に防衛していくと最適解が得られます。
これは、最適解の集合中に含まれない任意の要素より前にあり、かつが小さい要素が集合中に含まれないことから証明できます。
