AtCoder Beginner Contest 401 D - Logical Filling

# [AtCoder Beginner Contest 401 D - Logical Filling](https://atcoder.jp/contests/abc401/tasks/abc401_d)  
問題文は👆を確認してください

# 導入
atcoderで精進してますが、  
どこかにアウトプットしたかったので、qiitaに書くことにしました。  
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。  
また、誰かの参考になると嬉しいです。

# 使用しているアルゴリズム
- Greedy（貪欲法）
- 丁寧な条件分け

# 解法のポイント
この問題は、「o の個数が K 個であり、かつ連続していない」という2つの条件を満たすように `?` を `o` か `.` に置き換えたすべての文字列の集合 $X$ に対し、**「その位置で確定して `o` or `.` と言えるかどうか」**を判定する問題です。

ポイントは以下の通りです：

### ✅ 前処理で `o` の左右を `.` に確定
`o` の隣に `o` が来ると条件違反になるため、`o` の左右にある `?` は無条件に `.` に置き換えます。

### ✅ 貪欲に `?` 中で取りうる最大のo数を調べる
「? が連続している区間」から、最大で何個の `o` を挿入できるかを調べておきます。これは奇数なら `q // 2 + 1`、偶数なら `q // 2`で求まります。

### ✅ 場合分けで出力を決定
1. すでに `o` の数が K：→すべての `?` は `.` に確定できます。
2. `o` の最大個数(M)が K：→ 連続"?"区間が奇数個の場合は置き換え可能なので後続処理に回します。
3. それ以外：→どの置き方でも成立しない可能性があるので、出力は全て `?`になります。

### ✅ 奇数長の `?` 区間のみ `o` の位置が確定
`M == K` のとき、奇数長の `?` の連続区間は oを最密に並べた形(ex: `o.o.o`)でしか成立しないため、`o` と `.` の配置が一意に決まる。これを使って、出力に反映します。

# ACサンプル
```python
N,K = map(int,input().split())

S = list(input())

q = 0 # 連続する"?"の数
M = 0 # "o"の取れる最大数
before = "?" # 前の文字(初期値は"?")

def add_m(q):
  if q % 2 == 0:
    return q //2
  else:
    return q // 2 + 1

for i in range(N):
  if i == N - 1:
    nex = "?"
  else:
    nex = S[i+1]

  if before == "o" and nex != "o":
    S[i] = "."
  
  if S[i] == "?":
    if before == "o" or nex == "o":
      S[i] = "."
  
  if S[i] == "?":
    q += 1
  elif S[i] == "o":
    o += 1
    M += 1
  
  if q > 0 and (not nex == "?" or i == N - 1):
    M += add_m(q)
    q = 0
  
  before = S[i]

if S.count("o") == K:
  op = "."
elif M == K:
  op = None
else:
  op = "?"

if op:
  print(''.join([op if c == '?' else c for c in S]))
else:
  q = 0
  for i in range(N):
    if not S[i] == "?":
      if q > 0 and q % 2 == 1:
        S[i-q:i] = ["o" if j % 2 == 1 else "." for j in range(1,q+1)]
      q = 0
    else:
      q += 1
  else:
    i += 1
    if q > 0 and q % 2 == 1:
      S[i-q:i] = ["o" if j % 2 == 1 else "." for j in range(1,q+1)]
  
  print("".join(S))
```

# 間違った解法の共有

私は誤って以下のように思い込んでしまい、今日1日中解法を理解できませんでした。。。

>❌："o"の左右に"."を置き換えた後の"?"の数の総和を使えば、Sが取りうる"o"の最大数は一意に算出可能。(S.count("o") + "?"の総和 // 2 + 1)

以下のNGコードは、色々と間違ってるのですが大きな過ちとしては
以下のように入力値が"."のみのケースでは、この理論は破城します。
※このケース見つけるのに4時間はかかりました😭

```txt
7 4
???.?.?
期待値: o.o.o.o
出力値: ???.?.?
```

```python
# NGコード
N,K = map(int,input().split())

S = list(input())

o = 0
dot = 0
q = 0
before = "?"
for i in range(N):
  if i == N - 1:
    nex = "?"
  else:
    nex = S[i+1]
  if S[i] == "?":
    if before == "o" or nex == "o":
      S[i] = "."
  
  if S[i] == ".":
    dot += 1
  elif S[i] == "?":
    q += 1
  else:
    o += 1
  
  before = S[i]

if o == K:
  op = "."
#### ここが問題 ######
elif not q//2 + 1 + o == K:
####################
  op = "?"
else:
  op = None

if op:
  print(''.join([op if c == '?' else c for c in S]))
else:
  q = 0
  for i in range(N):
    if not S[i] == "?":
      if q > 0 and q % 2 == 1:
        S[i-q:i] = ["o" if j % 2 == 1 else "." for j in range(1,q+1)]
        # print(S)
      q = 0
    else:
      q += 1
  else:
    i += 1
    if q > 0 and q % 2 == 1:
      S[i-q:i] = ["o" if j % 2 == 1 else "." for j in range(1,q+1)]
  
  print("".join(S))
```

# リンク
[ACサンプル集(アルゴリズム逆引き)](https://www.notion.so/motonao/1cc8aca4381b80f39713ddb52fa85e8f?v=1cc8aca4381b80519654000c236bb8d6&pvs=4)