Codeforces Round 98 (Div 2)
Result
494 / 976 / 1392 / 1704 / 1810
0 Hacks
14位(Out of competitionなのでノーレート)
A. Postcards and photos
問題
CとPが一列に並んでいる。これを全部クローゼットに入れたい。
列の先頭のものから順にクローゼットに入れなければならない。
一度に、5個まで同じ種類のものを持つことができる。
違う種類のものは同時に持つことはできない。
クローゼットまで最低何回往復しなければならないか、求めよ。
制約条件
列の文字数≦100
試行錯誤
ちょっと問題文の読解に手間取る。
まあシミュレーションすればいい。
書いた。提出。
B. Permutation
問題
n個の数が与えられる。
これが、1〜nの順列（1からnまでの整数が1度ずつ現れる列）になるためには、
最低でいくつの数を変更しなければならないか、求めよ。
制約条件
n≦5000
試行錯誤
1〜nの範囲に入ってない奴、一度出た数とかぶってる奴を変更すればいい。
setつかって重複を見る。
おk.書けた。送信。
C. History
制約条件
n≦10^5
1≦区間の左端、右端≦10^9
試行錯誤
ん、n≦10^5？
O(n^2)で出来ないじゃんどうすんのこれ……
RMQ使えばいけるかな？
区間の長さでソートして、左端ごとに右端の値を持っておいて、RMQで自分より左側での右端の最大値を見ればよいのでは。
よさそう。0スタートのRMQだからbinary indexed treeが使える。
座標の値が大きいので座標圧縮しないとダメ。
書けた。サンプル合った。えーこれCなの？やけにむずくね……
送信。
D. Palindromes
問題
文字列が与えられる。
これをk個以下に分割して、それぞれが回文になっているようにしたい。
回文にするために変更するアルファベットの個数の最小値を求めよ。
制約条件
k≦500
文字列の長さ≦500
試行錯誤
DPっぽい。
dp[pos][分割の個数]:=コストみたいにすればいいのでは。
オーダー大丈夫かな。
dp[i][j]は、dp[0][j-1]〜dp[i-1][j-1]を見るので、O(n^3)
あと、k〜iを回文にするコストでO(n^2).
これはメモ化すれば全体でO(n^2)しかかからないので、全体でO(n^3).
通りそう。
書いた。
あと経路復元が必要か。書いた。
サンプル合った。送信。
E. Last Chance
問題
文字列が与えられる。
この文字列の連続する部分文字列で、母音の数が子音の数の2倍以下であるようなものを、goodなsubstringという。
goodなsubstringで、長さ最長のものの長さおよび、その長さのgoodなsubstringが現れる回数を求めよ。
制約条件
文字列の長さ≦2*10^5
試行錯誤
んーと、まずa[i]をi文字目が子音なら-1母音なら+2にする。
で、その累積和s[i]を計算する。
すると、s[i]-s[j]が0以上な区間がgoodなsubstringに対応する。
ということは、iをループでまわして、s[j]がs[i]以上なjで最も右にあるものを見つけられればいい。
んーどうやんのそれ……
Segment Tree使えばできなくもないような。
書いてみる。
つまる。
いやもっと簡単に出来そうな気がしてきた。
えーと、クエリをソートしたらいいんじゃないの？
(s[j],j)をソートした配列を作って、(-s[i],i)をソートした配列を作って、
-s[i]は小さいほうから見て行って、s[j]-s[i]が0以上の間jを小さくしていって、jの最大値を覚えておけばいい。
尺取りだ。
書いた。実行終わらない。
しゃくとりでjを動かすの忘れてる。
修正。動いた。
送信。
System Test
全部通った。
