Codeforces Round #408 (Div. 2)

codeforces

久しぶりのブログ更新です
ほんとはyahooのみんプロとか、GCJとか、そういう優先度の高そうなものを投稿すべきかもしれませんがとりあえず昨日やったcodeforcesについて書きます

A.o
B.xo
C.x

http://codeforces.com/contest/796

公式解説
http://codeforces.com/blog/entry/51527

Bはケアレスミスで1WA
Cはpretestはpassしたものの、本テストでWAを出して落ちました

今回は解けた人が少ない問題が解けて青レートになれるかと少し期待したのですが残念ながらそう簡単には行きませんでしたね

とはいえCは全く太刀打ちできなかったわけでは無く、惜しいところまで行ってたので個人的には割と良かったかなあと思っています


A. Buying A House

0 < a[i] <= k を満たす家iとmの距離を測って、小さければ更新、という総当たりをやるだけですね

import sys

def solve():
    n, m, k = map(int, input().split())
    m = m - 1
    a = [int(i) for i in input().split()]

    min_d = 1<<30

    for i in range(n):
        if 0 < a[i] <= k:
            min_d = min(min_d, abs(m - i))

    ans = min_d * 10
    print(ans)

if __name__ == '__main__':
    solve()

B. Find The Bone

これも愚直にシミュレートしていって、穴のある位置についたらそこでその番号を出力して終了
最後まで完遂できたら、終了位置を出力

っていうだけなのですが、1-originを0-originに変換するのを忘れてWAを食らいました
example.2をやると間違っていることが確認できたはずですがちゃんと出力を見てませんでした
「出力が合ってるかちゃんと確認してない」って割とよくあるミスなんですがこれで50点引かれるのはもったいないですね……

テストを自動化してればこういうことも無いんですがこれくらいだと自動テストにかける手間がめんどくさかったりするので仕方ないですが、ちゃんと出力の整合性は確認しなきゃダメですね

後、気を付けるべきことと言えば入力行が多いのでreadline()を使うということですね
今回はちゃんとやってますが結構見落としがちなところなので

import sys

def solve():
    n, m, k = map(int, sys.stdin.readline().split())
    h = [int(i) - 1 for i in sys.stdin.readline().split()]

    is_hole = [False] * n
    for hi in h:
        is_hole[hi] = True

    pos = 0

    if is_hole[pos]:
        print(pos + 1)
        return

    for i in range(k):
        u, v = map(int, sys.stdin.readline().split())
        u, v = u-1, v-1

        if u != pos and v != pos:
            continue

        if u != pos:
            pos = u
        elif v != pos:
            pos = v

        if is_hole[pos]:
            print(pos + 1)
            return

    print(pos + 1)

if __name__ == '__main__':
    solve()

C. Bank Hacking

今回の目玉？です

木の問題ですね、こどふぉでは割と頻繁に（？）木の問題が出る気がします
逆にAtcoderではあんまり見ない気がします（あくまで私が解いたり見たりしている範囲で）

問題を読むと何やらややこしそうな感じで条件をまとめると

  • 「最初にハックする銀行は、ハッカーの強さ以下の銀行で無ければならない」
  • 「2回目以降にハックする銀行は、既にハックした銀行に隣接する銀行で無ければならない」
  • 「ある銀行がハックされると、その銀行と隣り合う銀行の強さが+1される」
  • 「ハックされた銀行とハックされてない銀行が隣接するとき、そのハックされてない銀行と隣接する銀行の強さも+1される」

という感じですね
このときに全ての銀行をハックするために必要なハッカーの強さの最小値を求めよということです

まずは例を見たりグラフを実際に描いたりしていると「最大値を最初にハックするのがよさそうだな」と思います
ハックすればするほど、銀行の強さが増加していくので最大値の銀行を最初にハックするっていうのは確かによさそうです

次にこの問題は木の問題なので、何かしら木の構造を活かす問題のはずです
最初にハックする銀行を選ぶと、その点を根とした根付き木の形で書けるので、それを描いてみて「木の構造が活かせないかなー、再帰が上手く使えないかなー」とか考えます
根付き木の形で書いてみると割と状況が鮮明に見えてきて
「根は+0、その根に隣接する点は+1、それ以外は+2される」
というところまで分かります
一箇所ハックすると、そこでその点についてる各部分木が分断されるのでこれ以降のハックは他の部分木に影響を与えないからです

ここまで落とし込めると直感レベルで考えた「最大値の銀行を最初にハックするとよさそう」が理論的にも補強されそうです
最大値以外を根にすると最大値が+1されたり、+2されたりするので必要な強さがより大きくなってしまいそうだからです

しかし、最大値が複数ある場合が「どれを選べばいいか」が難しそうなので最大値が1つだけか、2個以上あるかで場合分けをします

まず最大値が1つに定まる場合は簡単でその最大値をまず根にします
それと隣接する点は+1されるだけなので、最大値を超えることはありません
問題は隣接しない点でここは+2されますから、もしそこに最大値 - 1の点があれば、ここの強さは最大値 + 1になってしまい、最低でもその強さだけ必要になるということが分かります

次に最大値が2個以上ある場合です、これが厄介です
まずどの最大値を根に持ってきても他の最大値があるので、答えは最低でも最大値 + 1になりますし、逆に+2より大きくなることは無いので最大でも最大値 + 2です
どんなときに答えが最大値 + 1でおさまるんでしょうか？
これはちょっと考えると「全ての最大値を持つ点が深さ1までに全部属するようにできるとき」だと分かります
逆にどの最大値を根にしてもそのようにできないとき、最大値 + 1におさめるのは無理だと分かります
だから、最大値が2個以上あるときは

"最大値を持つ点"全てを根にしてみて、その木の深さ1までに最大値を持つ点を全て含められるなら最大値 + 1
そうでなければ最大値 + 2

を答えとする、とすればよさそう……に思えました

実際はここが間違っていて「最大値を持つ点」だけではダメでした
この場合本質は「最大値を根に持ってくること」ではなく、「全ての最大値を持つ点を深さ1までに収められるか」
ということだったので「最大値以外の点」についてもそれを根とした木を考える必要がありました

正直解法には結構自信があったのでシステムテストで落ちたときは「ほんとに？」という気分でしたがテスト待ちのときにこどふぉの記事を漁っていると間違いに気づかせてくれるテストケースが書いてありました

このミスはどうやったら防げたんでしょうか。
「最大値を根に持ってくるのが一番良い」と疑わなかったことでしょうか。
確かにそうですが、最大値が1個だけのときはこれは確かに正しいんですよね。
それで2個以上のときも、その考えを引きづってしまっていたということですね。
あと手元で作ったテストケースが弱かったということもありますね。

そもそも
「ある頂点を根としたとき、その頂点は+0, それと隣接する点は+1, それ以外は+2」
というかなり強い知見が得られたところで一旦リセットして考えるべきだったかもしれません。
この知見から答えは高々最大値 or 最大値 + 1 or 最大値 + 2のどれかになることが分かります。
最小値を求めるのだから
「どのようなとき、答えを最大値にできるか？」
「最大値より大きくなってしまうケースの場合、どのようなときに最大値 + 1にできるか？」
と順に考えていけば「最大値を根とするのが一番いい」という直感に頼らず済んだかもしれません

実際コンテスト中はもっと思考が雑然としている感じなので中々「こうしたらよかったかな」と思うことを
実践したりすることは困難だと思いますが……難しいですね

身のあるような無いようなとりとめも無い話をグダグダ書いてるのはやっぱり悔しかったからでしょうね

import sys

def solve():
    n = int(sys.stdin.readline().rstrip())
    a = [int(i) for i in sys.stdin.readline().split()]
    Adj = [[] for i in range(n)]

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

    max_v = max(a)
    num_m = sum(ai == max_v for ai in a)

    if num_m == 1:
        ans = max_v
        max_n = a.index(max_v)

        rinsetu = set(Adj[max_n])
        rinsetu.add(max_n)

        for u in range(n):
            if u in rinsetu:
                continue
            if a[u] == max_v - 1:
                ans = max_v + 1
                break
    else:
        for u in range(n):
            cnt = 0

            if a[u] == max_v:
                cnt += 1

            for v in Adj[u]:
                if a[v] == max_v:
                    cnt += 1

            if cnt == num_m:
                ans = max_v + 1
                break
        else:
            ans = max_v + 2

    print(ans)

if __name__ == '__main__':
    solve()