AtCoder Beginner Contest 401 D - Logical Filling
問題文は👆を確認してください
導入
atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。
使用しているアルゴリズム
- Greedy（貪欲法）
- 丁寧な条件分け
解法のポイント
この問題は、「o の個数が K 個であり、かつ連続していない」という2つの条件を満たすように ? を o か . に置き換えたすべての文字列の集合 $X$ に対し、**「その位置で確定して o or . と言えるかどうか」**を判定する問題です。
ポイントは以下の通りです：
✅ 前処理で o の左右を . に確定
o の隣に o が来ると条件違反になるため、o の左右にある ? は無条件に . に置き換えます。
✅ 貪欲に ? 中で取りうる最大のo数を調べる
「? が連続している区間」から、最大で何個の o を挿入できるかを調べておきます。これは奇数なら q // 2 + 1、偶数なら q // 2で求まります。
✅ 場合分けで出力を決定
- すでに
oの数が K：→すべての?は.に確定できます。 -
oの最大個数(M)が K：→ 連続"?"区間が奇数個の場合は置き換え可能なので後続処理に回します。 - それ以外：→どの置き方でも成立しない可能性があるので、出力は全て
?になります。
✅ 奇数長の ? 区間のみ o の位置が確定
M == K のとき、奇数長の ? の連続区間は oを最密に並べた形(ex: o.o.o)でしか成立しないため、o と . の配置が一意に決まる。これを使って、出力に反映します。
ACサンプル
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時間はかかりました😭
7 4
???.?.?
期待値: o.o.o.o
出力値: ???.?.?
# 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))