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))

            

        
      