AtCoder Grand Contest 039 A（参加＋失敗編）

はじめてのコンテスト参加。ABCだと思ってたけど今週はAGCだったのでこわかった。 結論は０完の爆死（つらい）だったので悔しい・・・

A問題

ある文字列SをK回繰り返してできる文字列Tがあるとき、Tの文字を1文字ずつ変えて（置換して）いって同じ文字同士が隣り合わないようにする最小手順を求める問題 atcoder.jp

所感

\( 1 \leq K \leq 10^9 \)

なので、Tを作るのは諦める。
文字列Sを繰り返したときのTに対する最小置換回数は、文字列Sに対する最小置換回数から計算できそう。
連続させた時に置換回数に影響するのは両端の接続部分のみなので、

• １．Sの各連続２文字の関係
• ２．Sの先頭文字と末尾文字の関係

で場合分けすればOK
１がK回、２がK-1回出現する（２はK回出現＋回数を１引くでもOK）

実際にSの各文字列を書き換える必要はないが、Sの長さが100以下なので書き換えをしても計算量的には問題なし
実際には、１．書き換え無しで解こうとしてWA→２．色々いじってみる→３．途中でわけわからなくなる→４．デバッグ用の出力がほしいので書き換えして出力することに。
書き換えは「ある文字に対して、その両側の文字と異なる文字で上書き」をしたいので、下記のコードで実装した（抜粋）

letters = string.ascii_lowercase　　# a~zの入ったリスト
score = 0　　# 置換回数の初期値

# Sの各連続2文字の関係
for i in range(0, len(S) - 2):　　# i + 2 まで考えるためのrange
  if S[i] == S[i + 1]:　　# 次の文字と同じだったら
    S[i + 1] = letters.strip(S[i]).strip(S[i + 2])[0]　　# 次の文字を前後と異なる文字に置き換え
    score = score + 1　　# 置き換えたので回数を増やす

# 最後の2文字は別個で処理（「次の次の文字」が存在しないため）
if S[-2] == S[-1]:
  S[-1] = letters.strip(S[-2]).strip(S[0])[0]
  score = score + 1
else:
  # Sの先頭文字と末尾文字の関係
  # 最後の2文字が同じ場合は先頭を考慮して置き換えるので、この処理は必要ない
  if S[-1] == S[0]:
    S[-1] = letters.strip(S[-2]).strip(S[0])[0]
    score = score + 1

上記に加え、Tの末尾は置換する必要がないので、Tの末尾が置換されていたら回数を１減らせば良い ところが提出したらRE／WAが出てしまい、下記が考慮から抜け落ちていたことに気づく。

• 1文字のみの入力（当然REになる）
• 連続させたときに置換回数が減るケース（後述）

前者は凡ミスすぎるけどとりあえずifで処理。
後者は以下の例が該当する。

例．aabaを2回繰り返す

各連続2文字では置換箇所は１箇所で、先頭と末尾を見ると置換箇所は１箇所
1箇所 × K + 1箇所 × K - 1 にK = 2を代入して、置換回数は3となるが、
aabaaaba
↓
acbacaba
とできるので実際は2回で良い。
これが例外的になるのは、2個くっつけた結果前半のaabaはacbaになり、後半のaabaはcabaになっていて置き換え方が異なっている点。
そこでSを2個くっつけたものに対して置換回数を数えて最後に合算することにした。
（思えばここで単純に2個くっつけて終わらせたのが誤算・・・？）

#!/usr/bin/env python3
import sys
import string

#### input
S_orig = list(input())
K = int(input())

# 1文字の時の処理
if len(S_orig) == 1:
  if K == 1:
    print(0)
    exit()
  else:
    # TをK文字のSにしてしまう
    S_orig = S_orig * K
    K = 1

# Sを倍にする
S = S_orig * 2

### 前述の計算 ここから ###
letters = string.ascii_lowercase
score = 0
for i in range(0, len(S) - 2):
  if S[i] == S[i + 1]:
    S[i + 1] = letters.strip(S[i]).strip(S[i + 2])[0]
    score = score + 1

if S[-2] == S[-1]:
  S[-1] = letters.strip(S[-2]).strip(S[0])[0]
  score = score + 1
else:
  if S[-1] == S[0]:
    S[-1] = letters.strip(S[-2]).strip(S[0])[0]
    score = score + 1
### ここまで ###

# 2個くっつけた場合、前半と後半で置き換え方が異なりうるので、
# 置換回数を別個に計算する（pre = 前：previous, fol = 後：following）
score_pre, score_fol = 0, 0
for i in range(0, len(S_orig)):
  if S_orig[i] != S[i]:
    score_pre = score_pre + 1

for i in range(0, len(S_orig)):
  if S_orig[i] != S[len(S_orig) + i]:
    score_fol = score_fol + 1

# Kの値に応じて集計
if K == 1:
  total = score_pre
elif K % 2 == 0:
  total = (score_pre + score_fol) * K / 2
else:
  total = (score_pre + score_fol) * (K - 1) / 2 + score_fol
# 最後の文字を置換する必要がないのに置換していたら1回分回数を減らす
if (S_orig[-1] != S[-1]) and (S_orig[-1] != S_orig[-2]) and (S_orig[0] != S_orig[-1]):
  total = total - 1
print(int(total))

ここまで書いて最後の１つのWAが解消できず、失敗
解説放送を見て色々思うところがあったので別途書く予定