Educational Codeforces Round 75 (virtual) 解法

コンテストページ

https://codeforces.com/contest/1251

解法

✔A - Broken Keyboard

前から見て、奇数文字連続している箇所を検出します。今見ている文字の現状の重複度を管理です。

✔B - Binary Palindromes

0 と 1 がそれぞれ奇数個ずつあって、長さがすべて偶数であるときだけが、すべてを回文にすることが出来ません。その場合も、1 本を犠牲にしてパリティを調整できます。

✔C - Minimize The Integer

偶数同士と奇数同士の位置関係を入れ替えない範囲でいくらでも交換可能です。偶数と奇数を順番にキューに入れていって、小さい方から取り出していきましょう。番兵として、10 を入れておくと良いです。

✔D - Salary Changing

二分探索です。（二分探索をしなくても解けそうではあります。）（TL 3 秒に対して 2 以上掛っていますから、にぶたんをしないのが想定だったかもしれません。）

l の中央値以上 r の中央値以下しかありえませんから、その範囲で二分探索です。中央値 X を決めたら、それ未満しか配れないもの（これは n/2 人以下です）はすべて l を配ります。またそれだけでは人数が足りなければ l の小さい順に l （これは X 以下です）を配ります。残りの方々に min(X,l) を配ります。これで足りているかを見ます。

✔E1 - Voting (Easy Version)

お金をお支払いして投票して頂く人数 K を全探索です。無料で投票していただく方々は、m が K 以上、K+1 以上……でなければいけません。そこで、K 以下のものをすべて入れて、最大があれば取得して消します、なければこのブランチはダメです。次に K+1 以下のものをすべて入れて、どんどん行きます。

なのですが、TLE を頂いてしまったので、C++ に切り替えました。ボトルネックもヒープ（おそらく軽め）とはいえ、N = 5000 で Θ( N ^ 2 * logN ) は攻めすぎたでしょうか。ログを下ろす方法がわかりませんでした。（ Θ( N * log N ) への改善はできましたから、次の E2 は通りました。）

✔E2 - Voting (Hard Version)

先程全探索していた K を二分探索です。さらににぶたんの中でヒープを使うとログが 2 つ乗ってしまいますから、K の探索のときには人数だけを管理してログをおろしましょう。これで Θ( N * logN ) です。

✖F - Red-White Fence

a と b をそれぞれソートです。 a を小さい順に（同じものは纏めて）見て、そこまでの板を使って長さ合計 i の列 2 つが何通り出来るかを DPです。 a が単独の要素なときには、dp[i]+=2*dp[i-1] を干渉しないように更新です。さらに複数なときには dp[i]+=dp[i-2] も同時に干渉しないように更新です。

さて、b より等号付きで大きな白い板まで来たとしましょう。そこで白い板の更新の前に答えを ans[2*(b+i+1)] += dp[i] で更新です。ちなみにこれですと大きな白い板がないときに更新が出来ませんから、a に番兵さんを入れておきましょう。また、白い板一枚で復数の赤い板の更新があることがありますから、if ではなく while です。いいですか？

さて、ボトルネックはどこかといいますと、dp 配列の更新です。これは 2 乗の時間がかかっていますから、このままでは間に合いません。しかし、この更新は多項式 1+2q, 1+q² の掛け算ですから、いくつ書けたかだけ憶えておいて、使うときに一気に計算をしましょう。それぞれを何乗かするのは二項係数でできるのですが、これらの間の掛け算はどうしたものでしょう。

みんなだいすき FFT です（完）

ところで私はコンテスト中 K <= 5 を見落としていて、30 万まであると勘違いをしていました。悲しいですね。