ABC420の記録

はじめに

D解けそうな気がしたんだけど……

成績：ABC3完(600)

A

$x$と$y$を足して12で割った余りを出力。余りが0なら12を出力。

A

x,y = map(int,input().split())
num = (x + y)% 12
if num == 0:
    print(12)
else:
    print(num)

ある数を割って余りを取るとその数自身はあまりにならないの、ときどき忘れそうになる。

B

頑張って数える。

B

n,m = map(int,input().split())
vote = []
for _ in range(n):
    vote.append(input())
score = [0 for _ in range(n)]
for i in range(m):
    zero = [] #0の人数
    one = [] #1の人数
    for j in range(n):
        if vote[j][i] == '0':
            zero.append(j)
        else:
            one.append(j)
    if len(zero) == n or len(one) == n:
        for i in range(n):
            score[i] += 1
    elif len(zero) < len(one):
        for x in zero:
            score[x] += 1
    else:
        for y in one:
            score[y] += 1
maxs = max(score)
ans = []
for i in range(n):
    if score[i] == maxs:
        ans.append(i+1)
print(*ans)

やることは単純だがBにしては実装が重くないか？

C

最初の配列の状態で答えを計算しておいて、以降は値が変わったところのみ考える。変更後の$min(A_i,B_i)$-変更前の$min(A_i,B_i)$を計算して答えに加算していけばよい。

C

n,q = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
tmp = 0
for i in range(n):
    tmp += min(A[i],B[i])

for _ in range(q):
    c,x,y = input().split()
    x = int(x)
    y = int(y)
    if c == 'A':
        tmp += min(y,B[x-1])
        tmp -= min(A[x-1],B[x-1])
        A[x-1] = y
    else:
        tmp += min(A[x-1],y)
        tmp -= min(A[x-1],B[x-1])
        B[x-1] = y
    print(tmp)

変更があったところのみ考えれば良い、C問題っぽいC問題。実装が軽いのでBより解きやすかった感すらある。

D

迷路の状態は2つしかないわけで、グリッドを2つ用意して?を踏んだらもう片方のグリッドにワープすればいいのでは？と考えたが実装法が分からず終了。
解説を読むと3次元配列を使って$grid[r][y][x]$($r$は0か1)とすることでグリッドを2層にすることで実装できると書いてあったのでそれで取り組んだ。

D

h,w = map(int,input().split())
grid = [[],[[] for _ in range(h)]]
for _ in range(h):
    z = input()
    grid[0].append(z)


for i in range(h):
    for j in range(w):
        if grid[0][i][j] == 'S':
            startx = j
            starty = i
            grid[1][i].append('S')
        elif grid[0][i][j] == 'G':
            goalx = j
            goaly = i
            grid[1][i].append('G')
        elif grid[0][i][j] == 'o':
            grid[1][i].append('x')
        elif grid[0][i][j] == 'x':
            grid[1][i].append('o')
        else:
            grid[1][i].append(grid[0][i][j])
for i in range(h):
    grid[1][i] = ''.join(grid[1][i])
through = set(['S','.','G','o','?']) #通れるマスの種類
inf = float('inf')

#BFS
from collections import deque

def bfs(start_x, start_y,grid):
    visited = [[[inf]*w for _ in range(h)],[[inf]*w for _ in range(h)]]
    queue = deque()
    queue.append((0,start_x, start_y))
    visited[0][start_y][start_x] = 0

    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 左右上下（x, y）

    while queue:
        r, x, y = queue.popleft()

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < w and 0 <= ny < h and grid[r][y][x] == '?':
                if visited[(r+1)%2][ny][nx] == inf and grid[(r+1)%2][ny][nx] in through:
                    visited[(r+1)%2][ny][nx] = visited[r][y][x] + 1
                    queue.append(((r+1)%2, nx, ny))
            elif 0 <= nx < w and 0 <= ny < h and grid[r][y][x] != '?':
                if visited[r][ny][nx] == inf and grid[r][ny][nx] in through:
                    visited[r][ny][nx] = visited[r][y][x] + 1
                    queue.append((r, nx, ny))
    return visited

visited = bfs(startx, starty,grid)
ans = min(visited[0][goaly][goalx], visited[1][goaly][goalx])
print(-1 if ans == inf else ans)

片方のグリッドで?マスに到達したときは、もう片方のグリッドの隣接するマスをキューに入れるとグリッドを行き来できることになる。?マスは踏んだ瞬間にワープするので、片方のグリッドで?マスを踏んでもそこは踏んだことになっておらず、もう片方のグリッドの?マスを踏んだことになっている……(?)というイメージ。

3次元配列を使うという発想はたどりつけても良かった気がする……思いついたとしてC終わった時点で残り1時間だったので時間内に実装しきれたかは微妙なような気もするが。