abc187

NISHIO Hirokazu [Translate]
ABC187
AtCoder Beginner Contest 187 - AtCoder

全問正解でした。EをTLEしてるのに気づかずFに進んで、Fの提出時に気づいて焦ったけど、FはあっさりACしたのでEを修正するのに専念できました。

やった、青になった。ABCでは大して伸びなくなっててARC待ちだと思ってたから嬉しい誤算！年始から幸先いいね！

C - 1-SAT
肯定の項と否定の項をそれぞれ集めて、肯定にも否定にも含まれてるものがあればそれを出力すれば良い
探すところが線形だと間に合わないのでハッシュテーブルを使った
pythondef main():
    posi = set()
    nega = set()
    N = int(input())
    for _i in range(N):
        s = input().strip().decode('ascii')
        if s[0] == "!":
            nega.add(s[1:])
        else:
            posi.add(s)
    
    for s in posi:
        if s in nega:
            print(s)
            return
    print("satisfiable")
Tweet
26進法だと解釈した人がいた(ソース失念)
:>>> (26 ** 11) - 1
3670344486987775
>>> (3670344486987775).bit_length()
52
不安に思ったが、64ビット整数ならセーフか

D - Choose Me
演説しないとき、相手陣営にAi、したとき、こちら陣営にAi+Bi
つまり何もしない状態で得票の差は\sum A_i
これを負にしたい
ひとつ演説すると2 * Ai + Bi減る
→この値でソートして大きい方から取り、負になったら終了
得する順に選ぶ貪欲法
pythondef main():
    N = int(input())
    sumA = 0
    diff = []
    for _i in range(N):
        a, b = map(int, input().split())
        sumA += a
        diff.append(2 * a + b)

    diff.sort()
    ret = 0
    while sumA >= 0:
        ret += 1
        d = diff.pop()
        sumA -= d
    print(ret)
Twitter
有権者の多い順に取ってしまうミスをした人が多いっぽい
反例: src 
>(高橋:青木)がそれぞれ [(9:1), (1:8), (1:3)] 


E - Through Path
考えたこと
素朴に実装するとクエリのたびに半分くらいの頂点の値が更新される
2 * 10^5頂点、2 * 10^5クエリなのでこれだと間に合わない
グラフが木なので根つき木に変換
クエリの片方は「ある頂点以下の子孫頂点にまとめて加算」だと気づいた
途中は差分で持っておいて、最後に和を計算するアプローチができそう
もう片方も2箇所を逆向き更新すればできる
RangeAddは二つのPointAddの発想だ
実装してサンプルコードで試す
bがaの親である場合とその逆の場合があるので4通りの場合わけ
提出してTLEなのに気づかずにFに進んでしまった
最後に和を取る部分を再帰呼び出しからループに変換してAC
pythondef main():
    from collections import defaultdict
    N = int(input())
    edges = defaultdict(list)
    AS = []
    BS = []
    for _i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        AS.append(a)
        BS.append(b)
        edges[a].append(b)
        edges[b].append(a)

    root = 0
    children, parents = graph_to_tree(N, edges, root)
    veterx_diff = [0] * N

    Q = int(input())
    for _q in range(Q):
        t, e, x = map(int, input().split())
        e -= 1
        a = AS[e]
        b = BS[e]
        if t == 1:
            if parents[a] == b:
                veterx_diff[a] += x
            else:
                veterx_diff[root] += x
                veterx_diff[b] -= x
        else:
            if parents[a] == b:
                veterx_diff[root] += x
                veterx_diff[a] -= x
            else:
                veterx_diff[b] += x

    finish = [0] * N

    stack = [(root, 0)]
    while stack:
        v, x = stack.pop()
        x += veterx_diff[v]
        finish[v] += x
        for c in children[v]:
            stack.append((c, x))

    print(*finish, sep="\n")

F - Close Group
考えたこと
完全グラフの個数？
複数の完全グラフに所属する頂点をどうすべきか自明でない
N <= 18, 2^18 == 262144, M <= 153, 2^N * Mは4 * 10^7くらい
頂点数18の制約
2^Mは無理
まず素朴に実装して観察しよう
実装
どこかの完全グラフに所属できるなら所属することを優先して探索し、既知の解とイコールになったら良い解にはならないから探索をやめるアプローチ
素朴に実装してサンプルが通ったので、どの程度TLEになるか確認のために提出したらACした
PyPyで再帰呼び出しで実装していて92msecなので余裕
pythondef main():
    N, M = map(int, input().split())
    edges = set()
    for _i in range(M):
        edges.add(tuple(map(int, input().split())))

    ccs = [[1]]  # Connected Components
    ret = 18

    def visit(pos):
        nonlocal ret
        if pos == N + 1:
            if len(ccs) < ret:
                ret = len(ccs)
            return
        if len(ccs) >= ret:
            return

        for cc in ccs:
            if all((v, pos) in edges for v in cc):
                # can join the cc
                cc.append(pos)
                visit(pos + 1)
                cc.pop()

        # create new cc
        ccs.append([pos])
        visit(pos + 1)
        ccs.pop()

    visit(2)
    print(ret)
公式解説
O(3^N)になる
部分集合の部分集合の数の和が3^Nなのと同じ原理ね
部分集合それぞれについて、その部分集合についてのminを取ってるから
Tweet
"F問題は、EDPC Uとほとんど同じ問題" src
DP U
"対偶を取って補グラフを考えると彩色数になった" src
ABC187のFは遅いと評判のPyPyの再帰呼び出しで枝刈り全探索してあっさりACしたのでたまたま落とすテストケースがないだけなのか、これで十分なのか気になるなぁ。今のところ落とすケースを僕は思い付かないが。
今気づいたけどPython内で最速じゃん
ロクに高速化もしてない(完全グラフになるかどうかの判定で辺の有無を辺のリストを線形になめて調べてるレベル)なのに最速なの意味がわかんない
Python最速の実装についてもう少し言語化を試みてみる。まず頂点1を一つの連結成分とする。頂点2について「既存の連結成分に参加できるかどうか」をチェックする。連結成分の数を最小化したい、参加できるなら+0、できないなら+1なのでできる方を先に探索する。
深さ優先探索で全部の頂点を連結成分にわけて、解の下限Lを得る。探索を進める過程で連結成分の個数は非減少なので、以降の探索では連結成分の数がLに達したらそこより先により良い解がないので探索を打ち切って良い。
やってることはこれだけ。入力が完全グラフの時は各頂点につき「連結成分に入れる、入れない」の二択で、入れる方を優先して探索するのですんなり「全部ひとつにする」にたどり着く。入力に辺がない時は、各頂点について選択肢がないのでこちらもすんなり探索が終わる。
一見やばそうなのが完全二部グラフの時で、1〜9がバラバラの連結成分になった後、10を入れる選択肢が9個になる。枝刈りせずに探索すると9!になるわけだが、深さ優先探索で一旦たどり着いたら、残りは全部打ち切られるので18回くらいの探索で終わる。これは解の下限を把握してることによる。
なお 9! = 362880 なので 3 ** 18 = 387420489 に比べたら1000倍小さい
辺の有無を線形探索して最速なの気持ち悪かったので、ちゃんとO(1)で辺の有無がわかるようにした: 76ms
辺の有無判定をコスト1として、確率pでランダムに辺を張ったグラフのコストを出力する実験をしてみた
Pが0や1の時は153回、pが0.6〜0.8ぐらいで10万を超えてくる
この範囲で1000回試して最もコストが高かったのは0.8 2252973
10000回で7838954
:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
間違えて自己辺も生成しちゃってるけどこの問題を解く上では影響がないので無視してOK
前半を1で埋めて1万件調べるとコスト11750699のものが見つかった
:[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
32590993
:[0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]