AtCoder Grand Contest 037
出ました。ABはやめの2完で黄色パフォ。久し振りにレートが伸びました(うれしい)
A - Dividing a String
問題：文字列ｓの分割で隣りあう２つが一致しないような最大の分割数を求めよ
考察：
とりあえず貪欲にわければよいです
1つ前と一致する場合1文字追加します
2文字と1文字の文字列しかできず、2文字のものは連続しません。なぜなら2文字の文字列の次は1文字で良いからです。
ここでaaaaaのとき、a aa a aとなって条件を満たしません
最後のaをカウントしなければ、1文字ずつずらしてaaaを作るなどして解決できます。
2文字だけならaaとすればよいですし、途中に別の文字があればそこから前は関係ないです。
誤読して時間溶けたんですけど、一応10分強で通せてよかったです。
B - RGB Balls
問題：3N個のRGB色の玉をN人にわける。1人がそれぞれ1色ずつ持つようにして、全体のコストはそれぞれの人の玉のindexについてmax_idx-min_idxの和になる。最小化する配り方は何通りか
考察：
追い越しが起こるとロスします。
前から見て順次かけていくことを考えます。
いま2色だけ考えて、Rを配るとき、Gしか持ってない人がいればその人に配ります。
逆もしかりです。
3色に戻しましょう。見ている色と別の2色を持っている人がいればその人に、1色だけ他の色を持っている人がいればその人に配ります。
最適の証明ですが、Rを別の人、例えば玉を持ってない人に渡すとします。
そのうち、別のRを今渡すべきだった人に渡す時が来ます
GBR…G…B…R
<=>
この区間だけ2重にとっていて、Rのマッチング先を入れ替えることで減らせるため、上の操作の最適性が示せます。
厳密ではないですが、こんな感じで余りが1色のときにも対応できます。
かなり良いペースで考察して通せました。
800適正はなかったかもしれないですけど、コンテスト中に通せたのは(多分)初なので嬉しいです。
C - Numbers on a Circle
問題：N個の整数が環状に並んでいる。ある整数を選んで両端の和を足すという操作を最小回数行い、bと一致させろ。
考察：何から手をつけるか全くわかなかったです。
解説：
bを減らしてaにすることと同値です。ここは典型パートらしいので覚えたい…
ある最大の整数を減らすとき、限界まで減らすかaに一致するまで減らします。
このときaと一致せず減らしすぎたり、減らせない場合不可能です
なぜならこの操作を中途半端にしても、両端より大きい限り両端に操作は行えません。
なのでそのうちこの整数に操作を行う必要があり、中途半端にする意味がありません。
結構計算量厳しく見えるんですけど、間に合います。
計算量解析がむずい
aに一致しない場合、両端のどちらかより小さくなる必要があります。
そうでなければ-1です。
両端のどちらかより小さくなる時、だいたい1/2です。
したがって1つの整数で操作する回数はlogbi。
全体でNlogBiです。そのほかに、最大の整数を持ってくるのにlogNかかります。
D - Sorting a Grid
問題：N*M行列を、行ごと、列ごと、行ごとに3回自由に入れ替えてソートせよ
考察：
逆に考えると（これをCでもやりなさーい）、3回目のソートでそろえるために、2回目のソートではi行目にはi=x/mとなるようにします。
そのために1回目のソートで、i列目はx/mが1~nの順列になるようにしたいです。
二部マッチングを使いうまく求めればよいです。
実装が全くわからなかったので蟻本などでフローを勉強してから出直してこようと思います。
E - Reversing and Concatenating
問題：文字列ｓにｋ回操作を加えて辞書順最小にせよ
操作：s+rev(s)の|s|文字の連続する部分文字列をsとする
考察：
後ろ側から見たときの辞書順最小にしたいです
ss=s+rev(s)のとき
ss==rev(ss)です
なのでssの中で辞書順最小を求めます
k回愚直にやると間に合いません。
log|s|回以上あれば、aなど辞書順最小のアルファベットのみにできそうです。
したがって高々13回程度の操作か、全てaなどで埋めるので間に合います
いや、これ間に合うのやっぱり非直感ですね。
全列挙してソートしました。
C++はやいなー
感想
DEの考察がだいぶ伸びるも通せませんでした。
悔しいですね。でもまだまだ競プロ戦えるっていう希望を見つけた気がします。
Cは反省点なんですけど、答え見ても理解に時間かかったあたり地力足りてないと思いました。インシ終わったことですし、ガンガン問題埋めていこうと思います。
