ABC411 備忘録


今回はPythonでABC411をA~Dまで解くことができたので、備忘録を纏めました。

## コンテスト概要
ユニークビジョンプログラミングコンテスト2025 夏（AtCoder Beginner Contest 411）

https://atcoder.jp/contests/abc411

開催日:2025年6月21日 21:00-22:40


---

## [A - Required Length](https://atcoder.jp/contests/abc411/tasks/abc411_a)

### 方針
パスワードの長さ判定（文字列操作の基本）
文字列 `P` の長さを `len(P)` で取得し、それが `L` 以上であるかを判定するだけの問題になります。

```python
P = input()
L = int(input())

if len(P) >= L:
    print("Yes")
else:
    print("No") 
```
---

## [B - Distance Table]((https://atcoder.jp/contests/abc411/tasks/abc411_b))

### 方針

この問題は「区間和」を求める問題に等しく、累積和と二重ループがわかっていれば解ける問題です。

- 距離リスト D を使って、各駅の位置（累積距離）を `pos` 配列に保存。
- `pos[j] - pos[i]` で、駅 i と 駅 j の間の距離を計算できる。
- すべての i, j の組をループで求めればOK。

```python
N = int(input())
D = list(map(int, input().split()))

pos = [0] * N
for i in range(1, N):
    pos[i] = pos[i-1] + D[i-1]

for i in range(N - 1):
    row = []
    for j in range(i + 1, N):
        row.append(str(pos[j] - pos[i]))
    print(" ".join(row))
```
---

## [C - Black Intervals]((https://atcoder.jp/contests/abc411/tasks/abc411_c))

黒く塗られたマスの連続区間数（動的管理問題）

- 長さ N のマス列（初期状態はすべて白）
- Q 回のクエリで、指定されたマス（1-indexed）を反転（白↔黒）
- 各クエリ後に、「黒く塗られたマスの**連続区間**の個数」を出力

### 方針

各クエリで塗り状態を変更しながら、「**隣接マスの状態**」を参照して連続区間の増減を管理します。
- `colors[a] == 0`（白→黒）に変える場合：
  - 左右とも白：**新しい区間 → +1**
  - 左右とも黒：**区間を統合 → -1**
  - 片方だけ黒：変化なし
- `colors[a] == 1`（黒→白）に変える場合：
  - 左右とも白：**1つの区間が消える → -1**
  - 左右とも黒：**1つの区間が2つに分裂 → +1**
  - 片方だけ黒：変化なし

```python
import sys

sys.setrecursionlimit(1 << 25)

N, Q = map(int,input().split())
A = list(map(int,input().split()))

colors = [0] * (N + 2)  # 0: 白, 1: 黒（番兵付き）
black_segments = 0
res = []

for a in A:
    if colors[a] == 0:
        colors[a] = 1
        if colors[a - 1] == 0 and colors[a + 1] == 0:
            black_segments += 1
        elif colors[a - 1] == 1 and colors[a + 1] == 1:
            black_segments -= 1
    else:
        colors[a] = 0
        if colors[a - 1] == 0 and colors[a + 1] == 0:
            black_segments -= 1
        elif colors[a - 1] == 1 and colors[a + 1] == 1:
            black_segments += 1

    res.append(black_segments)

print('\n'.join(map(str, res)))

```

## [D - Conflict 2]((https://atcoder.jp/contests/abc411/tasks/abc411_d))


- サーバー + N台のPCがある（合計 N+1個の文字列）。すべて最初は空文字列。
- Q個のクエリに従って、PCやサーバーの文字列を操作していく。

### クエリの種類

1. `1 p`：PC p の文字列を **サーバーの文字列に置き換え**
2. `2 p s`：PC p の文字列の末尾に文字列 s を **追加**
3. `3 p`：**サーバーの文字列を PC p の文字列に置き換え**


### 方針

この問題は、「全クエリを文字列として持つ」と **TLE or MLE** になります。  
→ そこで、**ノード（参照型）で履歴を辿れるようにする設計**でACになりました。

### ✅ 工夫した点
- 各文字列の変更履歴を **ノードの親子関係として記録**：
  - 各ノードは `(親ノードID, 追加された文字列)` を持つ。
- 実際の文字列を構築するのは **最後にサーバーから1本の経路を逆に辿って構築**すればよい。

```python
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 25)

N, Q = map(int, input().split())

# ノードは (親のインデックス, 追加文字列)
nodes = [(-1, '')]  # 初期空ノード

# 各PCが参照するノードID
pc = [0] * N
server = 0

for _ in range(Q):
    q = input().split()
    t = int(q[0])

    if t == 1:
        p = int(q[1]) - 1
        pc[p] = server

    elif t == 2:
        p = int(q[1]) - 1
        s = q[2]
        nodes.append((pc[p], s))  # 新しいノードを追加
        pc[p] = len(nodes) - 1

    else:  # t == 3
        p = int(q[1]) - 1
        server = pc[p]

# サーバーのノードから再構築
result = []
node_id = server
while node_id != -1:
    parent, s = nodes[node_id]
    result.append(s)
    node_id = parent

# 後ろから構築されているので逆順に出力
print(''.join(reversed(result)))
```

## 結果
ABCD 4完
順位	2805th / 10749
パフォーマンス	975
レーティング	69 → 238 (+169) 

## 感想
コンテスト中にTLEを連発していたため、クエリにおける対処が課題。
A~D問題を安定して解けるようになりつつ、E問題も解けるように精進していきます！