略
複数の数の最大公約数の問題。
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)
なんか本番では別の偽解法で通ってしまった。
マスを全て通り一筆書き出来るようなルートをなぞり、
ことを繰り返すとよい。
通った後は必ず偶数枚になるため、そのマス数は最大となる。最後のマスだけ奇数枚になる場合があるが、これは全体の枚数が奇数でどうしたって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))