AtCoder Regular Contest 113
51:50 ABCD 4完 ノーペナ (えらい！！！)
レート : 1883 → 1921 (+38)
perf. : 2214
A - A * B * C (3:09)
ABがKを超えない範囲で全探索するとお馴染み調和級数のやつになるのでO(KlogK)でいけちゃう。
B - A ^ B ^ C (15:08)
1の位の値は1の位同士の演算によって決まる。1の位の値は10種類しかないので10以下の周期で遷移することがわかる。愚直に掛け算して遷移の仕方と周期を求める。あとは肩のBC (mod 周期) が求まればおっけー。これは繰り返し二乗法で間に合う。任意modのmodint構造体を前に作っておいたので貼るだけ！
C - String Invasion (31:07)
後ろから貪欲に変換していくのが良さそう、あえて変換しないことが最適になることは無い、はず。あえて変換しないことで別の変換時に変換できる文字の数を増やすことはできるが、合計は変わらないことがわかったのでよし。s[i] = s[i+1] のとき、i+2 以降に存在するs[i]の数 (= cnt[i+2]) がわかっていれば、変換できる文字数が求められる。cnt[] は後ろから見れば作れるが、変換を行った後で分布が変わってしまい、毎回更新していたら間に合わないので、変換した場所以降は別処理することにする。具体的には変換した場所と文字の種類を保持しておき、cntに関しては変換した場所より前で見れば良い。これはセグ木を使うと楽、思考停止でセグ木を26本生やしておっけー。サンプルが合ったので提出！する前に、手元でaaaとかを入力してみたら-1とか返しおる。明らかにミスっている。ミスを見つけて直して提出！AC！ファインプレーだった。
D - Sky Reflector (51:50)
マスに値を書き込んでいって列対を確認するのはちょっと不可能そう。作成できる列対の必要十分条件を考えるのが筋が良さそう。Aを適当に決めてみる、このとき最大値をmaxAとすると、Bの各値はmaxA以上である必要があることがわかる。逆にmaxA以上であれば十分であることもわかる。maxAを固定すると、通り数が計算できて (Aの最大値がmaxAであるようなAの選び方) * (Bの値が全てmaxA以上であるようなBの選び方) になる、Aの方は(maxA)N - (maxA-1)N で求められる。これは典型。N,M のどちらかが1である場合には注意が必要でちゃんと提出前に気づけた。ファインプレーその2。
E, F
嘘貪欲すら投げられず、ひたすらに椅子を暖め続けた。
まとめ
今のベストに近い立ち回りができた気がする。が、結局高難度 (暖色diff.) には歯が立たないのでまだまだ。
