AtCoder Beginner Contest 109

AtCoder Beginner Contest 109

解説放送: AtCoder Beginner Contest 109 解説放送 - YouTube

C - Skip

• $N$ 個の都市が一直線に並ぶ
• 各都市の座標は $x_1,x_2,...,x_N$ で与えられる
• あなたは座標 $X$ にいる
• ある正整数 $D$ を決め、$D$ だけ左右の好きな方に移動することを、好きなだけ繰り返せる
• 全ての都市を訪れることの出来る $D$ の最大値を求めよ

略

複数の数の最大公約数の問題。

Xから各都市までの距離（の絶対値）が $d_1,d_2,...,d_N$ とすると、これらの数の最大公約数が、取り得る最大の $D$ となる。

なお、Pythonには2数の最大公約数を求める gcd() が math モジュールにあるが、Python ver.3.4 までは fractions モジュールに存在していた。AtCoderでハマりがちな注意点として、AtCoderのPythonはまだ3.4なので、インポートの際には from fractions import gcd としなければならない。

複数の数の最大公約数は、3数 A,B,C とあったら gcd(gcd(A,B),C) と順番に2数の結果を求めていけばよい。

from fractions import gcd

n, s = map(int, input().split())
xxx = [abs(s - y) for y in map(int, input().split())]
d = xxx[0]
for x in xxx[1:]:
    d = gcd(d, x)
print(d)

なんか本番では別の偽解法で通ってしまった。

D - Make Them Even

• $H \times W$ の盤面がある
• マス$(i,j)$ にはコインが $a_{ij}$ 枚置かれている
• 以下の一連の操作を、0回以上、盤面のマス数($H \times W$)回まで行える
  1. マスを選び、そこに置かれたコインを1枚だけ取る
  2. 上下左右に隣接する好きなマスを選んで、1枚置く
• 1.の手順では、同じマスを2回以上選ぶことは出来ない
• 出来るだけ多くのマスのコイン枚数を偶数（0枚含む）にしたい
• それを達成できるような操作方法を構築せよ

マスを全て通り一筆書き出来るようなルートをなぞり、

• コインが奇数枚なら、コインを取り、ルート上の次のマスに置く

ことを繰り返すとよい。

通った後は必ず偶数枚になるため、そのマス数は最大となる。最後のマスだけ奇数枚になる場合があるが、これは全体の枚数が奇数でどうしたって1マスは奇数枚が出来てしまう場合に限られる。

ルートは何でも良いので、九十九折りのように進むのが楽。

配列の隣接した2要素を順に回すのは、for x1, x2 in zip(a, a[1:]) が手軽。速度やメモリは若干効率悪い。

h, w = map(int, input().split())
relation = []
for i in range(h):
    if i % 2 == 0:
        relation.extend((i, j) for j in range(w))
    else:
        relation.extend((i, j) for j in range(w - 1, -1, -1))
field = [list(map(int, input().split())) for _ in range(h)]

buf = []
for (i1, j1), (i2, j2) in zip(relation, relation[1:]):
    if field[i1][j1] % 2 == 1:
        field[i1][j1] -= 1
        field[i2][j2] += 1
        buf.append((i1 + 1, j1 + 1, i2 + 1, j2 + 1))

print(len(buf))
print('\n'.join(' '.join(map(str, line)) for line in buf))