AtCoder ABC109参戦記

今回はD問題が400点と通常の配点に戻り、前回、前々回と比べだいぶ易化しました。そのおかげもあり2回目の4完でした。嬉しい。以下C,D問題のコードと感想(?)です。

C問題 (Skip)

N, X = map(int, input().split())
P = [int(_) for _ in input().split()]
 
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while b:
        a, b = b, a%b
    return a
 
D = abs(P[0]-X)
for i in range(N):
    D = gcd(D, abs(P[i]-X))
 
print(D)

求めたい値は与えられた数列からXを引いた数列の最大公約数であることがわかります。一つずつ最大公約数を更新していけば求まりますが、座標が一つしかないケースもあるので初期値の設定に注意する必要があります。

D問題 (Make Them Even)

H, W = map(int, input().split())
A = [[int(_) for _ in input().split()] for _ in range(H)]
N = 0
move = []
for i in range(H):
    for j in range(W):
        if A[i][j] % 2 == 1 and j <= W-2:
            A[i][j+1] += 1
            N += 1
            move.append([i+1, j+1, i+1, j+2])
        elif A[i][j]%2 == 1 and j == W-1 and i!=H-1:
            A[i+1][j] += 1
            N += 1
            move.append([i+1, j+1, i+2, j+1])
 
print(N)
for i in range(N):
    print(move[i][0], move[i][1], move[i][2], move[i][3])

左上のマスから右下に向かって順番に偶奇の判定をしていきます。奇数枚あるマスだった場合、右隣に1つコインを送ります。右端の場合は下に送ります。こうすることで右下以外のマスをすべて偶数にすることができます。最終的に残った右下のマスは、コインの総数の偶奇と一致することになります。この操作を指定されたフォーマットで出力すればいいです。私のコード中では操作回数を操作と別にカウントしていますが、N = len(move)なので本当は数える必要はありません。