ABC411の感想戦
ユニークビジョンプログラミングコンテスト2025 夏（AtCoder Beginner Contest 411）に参加しました。今回はA,B,Cの3問を正解。C問題は、フリップする場所の隣を見ることで島の数を推定できることに気がついて、正解できた。
A - Required Length
パスワードの文字列とパスワードに必要な最短の長さが与えられるので、与えられたパスワードが十分な長さがあるか答える問題。
Pythonのlen()は、文字列を与えるとその長さを返す。そこで、これを使って必要なパスワードの長さと大小比較をする。
p = input()
l = int(input())
if len(p) >= l:
print("Yes")
else:
print("No")
B - Distance Table
駅間の距離が与えられるので、スタート駅から順番に次の駅までの累積距離を答える問題。
今回もB問題なので素直にスタート駅から次々と駅間の距離を加算していく。
技術的工夫
駅間距離を出力するとき、各値は空白で区切って出力する。この時文字列であれば" ".join()を使って結合できるが、要素が数値の場合には使用できない。これまでだったら数値を一度文字列に変換して空白で結合していた。" ".join(map(str, VAR))
しかし、print(*VAR)とすると文字列への変換や空白を挟んでの結合をすること無く、空白区切りで数値を出力できる。
n = int(input())
d = list(map(int, input().split()))
for i in range(n):
dist = 0
result = []
for j in d[i:]:
dist += j
result.append(dist)
print(*result)
C - Black Intervals
意訳すると、白と黒のカードが並んでいて、指定位置のカードをフリップする。フリップしたら、黒が連続する（島）の数を答える問題。
フリップする両隣を見れば、島の増減が分かる。例えば、白が並んでいる所で\(○○○ \rightarrow ○●○\)ならば島ができるので\(+1\)。また、黒が並んでいる中で\(●●● \rightarrow ●○●\)ならば島を切断するので\(+1\)。こうして全ての組み合わせを考えると次のようになる。
-
白から黒に変わる場合
- 両側が黒の場合は、島をつなぐので島の数が減る。
- 両側が白の場合は、新しい島を作るので島の数が増える。
- 隣が白と黒の場合は、島が大きくなるので島の数は変わらない。
-
黒から白に変わる場合
- 両側が黒の場合は、島を切断するので島の数が増える。
- 両側が白の場合は、島が消えるので島の数が減る。
- 隣が白と黒の場合は、島が小さくなるだけなので島の数は変わらない。
これを素直にコードに変換した。
ハマりポイントは、カードが1枚の場合。1枚しか無いケースがあるので、その場合の対応を忘れるとRuntime Errorとなる。また両端の場合も個別の対応が必要。
n, q = map(int, input().split())
A = list(map(int, input().split()))
box = [False] * n
count = 0
if n == 1:
face = False
for _ in A:
face = not face
if face:
print(1)
else:
print(0)
else:
for a in A:
i = a - 1
face = not box[i]
box[i] = face
if face:
if i == 0:
if box[i + 1]:
pass
else:
count += 1
elif i == (n - 1):
if box[i - 1]:
pass
else:
count += 1
else:
if box[i - 1] and box[i + 1]:
count -= 1
elif not box[i - 1] and box[i + 1]:
pass
elif box[i - 1] and not box[i + 1]:
pass
elif not box[i - 1] and not box[i + 1]:
count += 1
else:
if i == 0:
if box[i + 1]:
pass
else:
count -= 1
elif i == (n - 1):
if box[i - 1]:
pass
else:
count -= 1
else:
if box[i - 1] and box[i + 1]:
count += 1
elif not box[i - 1] and box[i + 1]:
pass
elif box[i - 1] and not box[i + 1]:
pass
elif not box[i - 1] and not box[i + 1]:
count -= 1
print(count)