ABC351備忘録【C～D】

C - Merge the balls

問題

考えたこと

実際に$2^x$を格納して探索していくとTLEやMLEになってしまいます。よって、指数部分だけを考え、条件3については$2^x + 2^x = 2^{(x+1)}$となる性質を使います。ほかの条件は素直に実装すればOKです。

ACコード

c.py

n = int(input())
A = list(map(int, input().split()))

ans = []

for i in range(n):
    ans.append(A[i])
    while True:
        if len(ans) <= 1:
            break
        elif ans[-1] != ans[-2]:
            break
        else:
            ans.pop()
            ans.append(ans.pop() + 1)

print(len(ans))

D - Grid and Magnet

問題

考えたこと

流れとしてはABC349のD問題と同じように、与えられた文字列を自分が探索しやすいようにグラフ化し、探索という方針です。ただし、以下の二点に注意しつつ有向グラフを作成します。

• 磁石自身と磁石が隣り合うところからスタートできない
• 各頂点の番号が$i*w + j$と表される

また、図を眺めてみると以下の点に気が付きます。

• 磁石が隣りにない頂点同士の自由度は等しい
  • 行き来できるので自由度を共有する
• 頂点6は二つの頂点から行先として指定されている
  • BFSでは訪問済みの点をチェックしておくが、チェック方法を工夫しておく必要がある

以上の気づきから、訪問済みの点は再訪問する必要ない、訪問済みの頂点のチェック方法として以前訪問した頂点の情報を格納する、という方法をとることとしました。

ACコード

d.py

from collections import defaultdict, deque

h, w = map(int, input().split())
s = [input() for _ in range(h)]
g = defaultdict(set)
dij = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# グラフの作成
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        u = i * w + j
        mag = False
        # 注目している頂点の四方向に磁石があるならばスキップ
        for di, dj in dij:
            nex_i, nex_j = i + di, j + dj
            if not (0 <= nex_i < h and 0 <= nex_j < w):
                continue
            if s[nex_i][nex_j] == "#":
                mag = True
        if mag:
            continue
        # 注目している頂点の四方向に磁石がないならば辺を張る
        for di, dj in dij:
            nex_i, nex_j = i + di, j + dj
            if not (0 <= nex_i < h and 0 <= nex_j < w):
                continue
            v = nex_i * w + nex_j
            g[u].add(v)

vis = [-1 for _ in range(h * w)]
ans = 0

for i in range(h):
    for j in range(w):
        # st: 始点となる点
        st = i * w + j
        if s[i][j] == "#" or vis[st] != -1:
            continue
        que = deque([st])
        free = 0  # 自由度
        # BFS
        while que:
            pos = que.pop()
            if vis[pos] == st:
                continue
            vis[pos] = st  # 訪問先として現在探索している頂点を格納する
            free += 1
            for to in g[pos]:
                que.appendleft(to)
        ans = max(ans, free)

print(ans)