AtCoder Beginner Contest 109
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枚置く
- 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))
