AGC039-A Connection and Disconnection
概要
100文字までの文字列SをK(1 <= K <= 10^9)回繰り返した文字列(アルファベット小文字のみ)をTとする。Tに隣接した文字が現れないようにするには、何文字置き換える必要がある？
ACするまで
1. つながってる文字は2, 4, 6文字目だけ消せばよさそう（大嘘）
2. 一種類しかないやつはめんどくさそうだなぁ(10分経過後に気づく)
3. 先頭と後尾が同じものは、Tの中でK-1回現れる。これのほかに先頭が1回分、後尾が1回分出てくる。あと、偶数文字目だけ消すじゃなくて、連続してる文字の数KでK/2を切り捨てした分だけ消すと考えたほうがよさそう。(ここまで80分経過して幾多のWAを重ねる)(は？)
4. 先頭と後尾が同じのもの、違うもの、そもそも1種類の文字しかないものの3通りで場合分けして通す。
考察
ACするまでの4番そのものである。
ちなみに、差分をうまく取ることで簡潔な別解がある。
本番通した解法
そもそも同じ
S.size() * T / 2を出力すればよい。
先頭と後尾は違う
Sの中身を見て、連続してる文字列の長さがtならば、t * K / 2を答えに足せばよい。先頭と後尾でつながることはないので、シンプル
先頭と後尾が同じ
Tの中では、次のように分けられる。
- Sの先頭でつながってるもの
- Sの後尾でつながってるもの
- Sの先頭と後尾をつなげたもの * (K - 1)個
それぞれ丁寧に数え上げればよい。
別解
本番の解法と似てるように、つながってる文字列を
- (1周目の文字列の頭にかかる回数) "aaabbca"なら、"aaa"に相当する1回 -> A
- (K周目の文字列のしっぽにかかる回数) "aaabbca"なら、"a"に相当する0回 -> B
- (2つの文字列の首尾がくっついてる部分にかかる回数) "aaabbca"なら、"aaabbcaaaabbca"の"aaaa"に相当する2回 -> C
- (首尾ではない文字列の部分での1周期あたりの操作回数) "aaabbca"なら、"bb"に相当する1回 -> D
f(S)を文字列Sにおける操作回数と定めると、次の式が成り立つ
f(S) = A + B + D
f(S + S) = A + B + C + D * 2 (Sを二つ連結したものを渡してる)
よって、
f(S + S) - f(S) = C + D
となるのである。
ここで、
f(SをK回続けた文字列) = A + B + C * (K - 1) + D * K
= f(S) + (K - 1) * f(S + S)
との等式が成り立つ。(これ、コンテスト本番に思いつくのか？)
よって、この式に従って計算すればよい。
ここで、注意が必要なのは、同じ文字のみによって構成されてる場合である。その場合、AとBとCは厳密に区別できないので、この式から外れる。この場合だけ、事前に場合分けをすればよい。
一言
ICPCのやるだけをいっぱいやります。
