AtCoder Regular Contest 088
今回から余裕があれば自分の解法とか感想とかを書いていこうかと思う。
思考の過程を整理したり、解法を一度文章にまとめたりすることで競プロ強くなんないかなと淡い期待。
結果はCDEの3完で101位でした。
C - Multiple Gift
必要条件を徐々に広げていく感じで考察していくと、
の漸化式で、となるような最大の
まで生成した数列が、条件を満たす長さが最大となる数列の一つだとわかる。よってこの
が解。
愚直に1つ1つ計算して長さを求めるとで通る。
D - Wide Flip
とする。また、添字は0-basedとする。
制約から想定解法はっぽいし、問題中で「最大の整数
を求めてください。」とあったので、二分探索をまず疑った。
ので、を固定してそのときにすべて
になるような数列にできるかを考えた。
の順で
だったら区間
でフリップ。
- この操作で
は
になる。
- この操作で
がすべて
になれば、もとの数列は条件を満たす。
- 逆に
のうち
が存在すれば、もとの数列は条件を満たさない。
これで条件を満たす数列かの判定ができた。判定にかかる計算量はで、二分探索も加味すると全体で
で間に合わない。
しばらく悩んだけど、次の事実に気づいた。
- フリップ後に「
」であるかは、
に作用したフリップの回数
に対し「
」と等価。
- ここで、
はなにもフリップしていない時点での
を表す。
- ここで、
よってフリップの作用を累積的に計算していくことで計算量をに落とせる。よって全体の計算量は
になる。
解説読んだらこれよりスマートかつでの解法が紹介されてて天才か?ってなった。
E - Papple Sort
回文にできるかどうかの判別は単純なので、以降回文に並び替え可能であると仮定。
- 「隣り合った2つの文字を入れ替えてソートするときの最小入れ替え回数」は転倒数に等しい
この事実を知っていたので、問題を見てすぐ、転倒数を求めることになりそうだなと思った。
ただし、転倒数を求めるには最終的にどのような数列を"整列"とみなすかを考えなくてはならない。今回の場合は回文は一通りとは限らないため、整列となる候補は1つとは限らない。
しばらく最適な回文が何かを考えてたらふと思いついた。(この部分の考察は解説とだいたい同じだったため省略)
BITを手元のライブラリで準備してなかったので転倒数はセグ木で求めた。どうやって計算するのかど忘れしたので無駄に時間かけてしまった。