Codeforces Round #395 (Div. 2) - D言語で競プロ

参加しました
ABの２完で終わりました
Dashboard - Codeforces Round #395 (Div. 2) - Codeforces

A. Taymyr is calling you

問題概要

DujikovのところにIlia-alpinist(?)からn分毎に電話がかかってくる
そしてDujikovのところにアーティストがm分毎にやってきて立ち話をする
ある時間からz分後までその状態が続くとする
電話を取るときに家にアーティストがいないようにするには、何人のアーティストを殺せばよいか？
ただし電話も立ち話もちょうど１分で終わるものとする

制約

1 <= n, m, z <= 10^4

感想

相変わらず英語の読解力が無くてコンテスト中は何となく例を見て察して解いた、ほんとは良くないと思うけれど……
問題自体はシンプルで、「nとmの最小公倍数lcm(n, m)の倍数が1~zまでの間にいくつあるか？」ということを本質的に問われている。
というわけでコードは次のようになる、コーナーケースも特に無し、計算量はO(1)

from math import gcd

def solve():
    n, m, z = map(int, input().split())
    lcm = n * m // gcd(n, m)

    ans = z // lcm

    print(ans)

if __name__ == '__main__':
    solve()

地味にgcdを使うとき、少し悩むことがあってどこからimportするかという問題がある。
python3.5以上だとfrom mathでよいのだが、python3.4以下になるとこれはREになってしまう。
Codeforcesは3.5.2なのでこれでよいのだが、例えばAtcoderは未だに3.4なので上のコードはREになる。

python3.4の場合は

from fractions import gcd

とすればちゃんとgcdがインポートできる。

まあ3.5でもfractionsからインポートできるので、常にfractionsからインポートすればいいじゃんって感じですが公式的にはfractionsからインポートするのは非推奨っぽいので……
Atcoder以外にもAOJとかHackerRankは3.4だったと思います。

B. Timofey and cubes

Problem - B - Codeforces

問題概要

配列a = [a_1, a_2, ..., a_n]がある
この配列に対して以下の操作をi = 1 ~ (n + 1)//2まで繰り返す

i番目からn - i + 1番目までの要素を全て逆順にする

これを繰り返して出来た配列をb = [b_1, ... , b_n]とする
この配列bが与えられたとき、元の配列aを復元せよ

制約

1 <= n <= 2 * 10^5

感想

最初完全に読み違いしてて「i番目とn - i + 1番目の要素だけをスワップする」のかと思い込んでて例がなぜああなるのかということに無駄に頭を悩ませてしまいました。
例の注釈をよく読むとちゃんと全部ひっくり返してるから気づくだろうって感じですが、端しか見てなく……
ともあれ問題をちゃんと理解できれば、0-originに直して考えると
「配列の偶数番目は奇数回スワップされる、奇数番目は偶数回スワップされる」
ということに気づきます。
なので元に戻すとき「偶数番目だけ後ろの要素とスワップして、奇数番目はそのままにしておく」とすれば元の配列aが復元できます。
計算量はO(n)ですね。

def solve():
    n = int(input())
    As = [int(i) for i in input().split()]
    mid = (n + 1) // 2

    for i in range(mid):
        if i % 2 == 0:
            As[i], As[n - 1 - i] = As[n - 1 - i], As[i]
        else:
            pass

    print(*As)
    pass
    
if __name__ == '__main__':
    solve()

C. Timofey and a tree

Problem - C - Codeforces

問題概要

n個の頂点がある木があって、各頂点には色c_iがつけられている。
ある１つの頂点を取り除いたときに、各部分木について全ての頂点が同じ色になるかどうかを知りたい。
そのような頂点が存在するかどうか、また存在するならばその頂点を１つ出力せよ。

制約

2 <= n <= 10^5
1 <= c_i <= 10^5

f:id:nanae1914:20170205070422j:plain:w400

感想

素朴にやろうとするとO(n^2)かかるのでこれは制約上無理だと思って、ちょっと解法も思いつかなかったので飛ばしました。
それで無謀にもE問題を解こうとして無理だったので終わりました。

それで解説を見たんですが、かなりシンプルに解けるようです。
まず各辺の両端の色が全て同じだったと仮定すると、これはつまり木全体の各頂点が同じ色なのでどこを取り除いても条件を満たすことができます。
なので以下、少なくとも一つは両端の色が異なる辺が存在するとします。
すると、まずこの辺の両端の点以外の点を取り除くっていうことをやってみることを考えると、どこかの部分木にこの辺の両端の点が含まれますから条件を満たすことはできません。
つまり、条件を満たす可能性のある点はこの辺の両端の点のいずれかということになります。なのでこの２つの点を取り除いてみて、各部分木について全ての頂点が同じ色になっているかどうかだけ調べればよいということになります。
どちらか一方の点が条件を満たすならその点を出力すればよいし、どちらも条件を満たさないのだったら答えはNOになります。
このアルゴリズムだと、両端の色が異なる辺を見つける時間がO(n - 1)
そしてある頂点を取り除いたときに、各部分木について全ての頂点が同じ色になっているかを調べるのにO(n)、これを最大２回やります
なので全体としての計算量はO(n)ということになります

解説を参考に書いたコードがこちら
部分木の頂点が全て同じ色かどうかを調べる関数を再帰で書いてますが、あんまりうまく書けてないような気がします

def same_col(vx, u, adj, col):
    res = True
    for child in adj[vx]:
        if child == u:
            continue
        if col[child] != col[vx]:
            return False
        else:
            res = res and same_col(child, vx, adj, col)

    return res

def solve():
    n = int(input())
    adj = [[] for i in range(n)]
    edges = [] * n

    for i in range(n - 1):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u - 1, v - 1
        edges.append([u, v])
        adj[u].append(v)
        adj[v].append(u)

    col = [int(i) for i in input().split()]

    for u, v in edges:
        if col[u] != col[v]:
            break

    for vx in adj[u]:
        if not same_col(vx, u, adj, col):
            break
    else:
        print('YES')
        print(u + 1)
        return None

    for vx in adj[v]:
        if not same_col(vx, v, adj, col):
            break
    else:
        print('YES')
        print(v + 1)
        return None

    print('NO')

if __name__ == '__main__':
    solve()

E. Timofey and remoduling

Problem - E - Codeforces

問題概要

互いに異なる整数{a_1, a_2, ..., a_n}が与えられる。各a_iは0 <= a_i < m を満たす。
これらの整数を初項x, 交差d の長さnの等差数列の各項のmod mを取った数列
x % m, (x + d) % m, (x + 2d) % m, ..., (x + (n - 1)d) % m
で表すことができるか？　できるならばそのx, dを求めよ

制約

2 <= m <= 10^9 + 7, m:prime
1 <= n <= 10^5

感想

C, Dが解けるわけないのにEが解けるわけないとは確かに思うんですがでも解けそうだなって思ってチャレンジしてました。
やっぱり解けなかったんですけど。
考え方としては与えられたa_iを昇順ソートして隣り合う項の差a[i+1] - a[i]を記録して、それが１種類、または２種類だけなら作れる、３種類以上あったら作れないだろうって考えだったんですがダメでした。
例ぐらいのパターンだとこの方法で行けるんですが、case8でひっかかっててこれじゃあダメみたいですね。未だに何がダメかいまいち分かってないですが……
とりあえず書いたコードはこんな感じです

def solve():
    m, n = map(int, input().split())
    As = [int(i) for i in input().split()]

    if n == 1:
        print(As[0], 1)
        return None
    else:
        As.sort()

        gaps = []
        x = As[0]

        for i in range(n):
            if i == n - 1:
                gap = (As[0] - As[i]) % m
            else:
                gap = As[i + 1] - As[i]

            gaps.append(gap)

        cnt = Counter(gaps)

        if len(cnt) > 2:
            print(-1)
            return None
        elif n == 2:
            x = As[0]
            d = (As[1] - As[0]) % m
            print(x, d)
            return None
        elif len(cnt) == 2:
            d = cnt.most_common(1)[0][0]

            for i in range(n):
                if gaps[i] != d:
                    if i == n - 1:
                        s = 0
                    else:
                        s = i + 1

            x = As[s]

            print(x, d)
        else:
            x = As[0]
            d = As[1] - As[0]
            print(x, d)

if __name__ == '__main__':
    solve()