A bolt out of the blue

競プロ、その他勉強したことなど

AtCoder Beginner Contest 109 参加ログ

AtCoder

ABC109に参加しました

AtCoder Beginner Contest 109 | AtCoder

  実力：緑色 / 現R: 945

40分遅れて参加。

今回は久々に全完できた。 いつもよりも簡単だったんじゃないだろうか？

少なくとも計算量の点で困るところはなかった。  

A - ABC333

FizzBuzzと同程度の難易度。 落ち着いてやれば問題ない。

ちなみに僕はYesをyesと出力してしまって1 WAでした、、、、

問題文をよく読んだ方がいい。

B - Shiritori

Nが小さいので、一つ一つ見ていけば良いが、同じ単語があったかどうかもチェックする必要がある。

状態を管理するのは面倒なのと、余計なクエリが発生するので、重複チェックを先にやってしまうといい。

サンプルコード

n = int(input())
w = []
for _ in range(n):
    w.append(input())

judge = len(w) == len(set(w))

for pre, post in zip(w[:-1], w[1:]):
    judge &= pre[-1] == post[0]

if judge:
    print('Yes')
else:
    print('No')

C - Skip

問題文の解釈

何回でも Dだけ移動しても良いのだから、 D の倍数だけ X から離れた座標はどこにでも到達できる。

f:id:hazuhi:20180909123638j:plain

つまり図の中で、小さく線を引いた部分が、座標 X から訪れることのできる座標になる。

図の中で、座標 x, y は、座標 X から差分 D の積み重ねで到達できる。

座標 z には到達できない。

考察

もし座標 X から全ての座標 x_i に到達できるということは、

座標 x_i から座標 X にも移れるということだ。

これはつまり、任意の座標から他の任意の座標に移れるということでもある。

よって X も含めて全ての座標は等価だと考えることができる。

この全ての座標の集合を、 \{\ p_i: \ p_j ＜ p_k \ (where. \ j ＜ k )\} とすると、

一番左の座標 p_0 から、その右隣の座標 p_1 に移ることができる必要十分条件は、

p_1 - p_0 \equiv \ 0 \ mod \ D

になる。

計算

最も左の座標から、順に右隣の座標に移って行って、最も右の座標まで進むことができれば、全ての座標に到達することができる。

よって、 p_{i+1} - p_i の最大公約数を求めれば、 D の最大値を求めたことになる。

サンプルコード

atcoderのpythonは3.4なので、mathライブラリにはまだgcdがない。

これは結構忘れがちなので、気をつける。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def gcd_(list):
    result = list[0]
    for el in list[1:]:
        result = gcd(result, el)
    return result


n, x = LI()
X = LI()

X.append(x)
X.sort()

X_ = [post - pre for pre, post in zip(X[:-1], X[1:])]

print(gcd_(X_))

D - Make Them Even

所感

題意をみたすようなデータを生成する問題。 出力形式には十分注意する必要がある。

たかだか 500 \times 500 個のセルしかないので、全部調べる時間がある。

あとは、奇数を右下に掃き出していけば良いことに気がつけば、実装力の問題になると思う。

問題文の解釈

偶数になるセルを最大化する必要がある。

これを逆に考えると、奇数になるセルを最小化する問題と同じだ。

盤面をミクロに捉えてみよう。

隣接する二つのセルを考えると、この二つのセルの関係は、00, 01, 10, 11の４種類しかない。

ここで、0は偶数、1は奇数を表す。

重要なのは、11の時、片方のコインを移動して両方偶数にできることだ。

つまり、奇数のセルが集まっていれば、それを端から消していくことができる。

奇数のセルを掃き出していく

a_{11}, a_{12} のセルに着目して、コインの移動を考えてみる。

  1. 00の時：何もしない
  2. 01の時：何もしない
  3. 10の時： a_{11} から a_{12} へ１枚コインを移動することで、01になる
  4. 11の時： a_{11} から a_{12} へ１枚コインを移動することで、00になる

2, 3のように、奇数のセルを右にずらしていくか、1, 4のように両方偶数にすることができる。

この操作を、次に図のように左から右へ、上から下へ行っていけば、奇数を右下に掃き出すことができる。

f:id:hazuhi:20180909150743j:plain:w300

エッジケース

あるセルのコインの数が0枚の時、そこからコインを移動することはできない。 ただ、0は偶数なので、ここからコインを移動することはない。 よって無視できる。

サンプルコード

個々の掃き出しの計算は、xorでできるので、a[i+1][-1] ^= 1のような計算が出てくる。

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]


h, w = LI()
a = []
for _ in range(h):
    a.append([x%2 for x in LI()])

operations = []
for i in range(h):
    for j in range(w-1):
        if not a[i][j]:
            continue
        else:
            a[i][j+1] ^= 1
            operations.append(' '.join(map(str, [i+1, j+1, i+1, j+2])))

for i in range(h-1):
    if not a[i][-1]:
        continue
    else:
        a[i+1][-1] ^= 1
        operations.append(' '.join(map(str, [i+1, w, i+2, w])))

print(len(operations))
for row in operations:
    print(row)

結果 

R945 => R985 (Up)

もっと早く参加してれば、、、、、