ABC187

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

https://gyazo.com/eab26e86c59d96c42f2f735705d61531

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

https://gyazo.com/8422dc9634d556b4a3f836342ce7133f

https://gyazo.com/752614ec90e766bb6abb49f28fa2dfdf

肯定の項と否定の項をそれぞれ集めて、肯定にも否定にも含まれてるものがあればそれを出力すれば良い

探すところが線形だと間に合わないのでハッシュテーブルを使った

code:python

def main():

posi = set()

nega = set()

N = int(input())

for _i in range(N):

s = input().strip().decode('ascii')

else:

posi.add(s)

for s in posi:

if s in nega:

print(s)

return

print("satisfiable")

Tweet

26進法だと解釈した人がいた(ソース失念)

code::

>> (26 ** 11) - 1

3670344486987775

>> (3670344486987775).bit_length()

52

不安に思ったが、64ビット整数ならセーフか

https://gyazo.com/c04eb163ab65fe9a2655d14d2a4becc7

演説しないとき、相手陣営にAi、したとき、こちら陣営にAi+Bi

これを負にしたい

ひとつ演説すると2 * Ai + Bi減る

→この値でソートして大きい方から取り、負になったら終了

code:python

def 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

有権者の多い順に取ってしまうミスをした人が多いっぽい

https://gyazo.com/143ba6f9b2afebb4b79a2b4f6ba8faeb

考えたこと

素朴に実装するとクエリのたびに半分くらいの頂点の値が更新される

2 * 10^5頂点、2 * 10^5クエリなのでこれだと間に合わない

クエリの片方は「ある頂点以下の子孫頂点にまとめて加算」だと気づいた

途中は差分で持っておいて、最後に和を計算するアプローチができそう

もう片方も2箇所を逆向き更新すればできる

https://gyazo.com/0cafc8e96777af5b8bb542646f17aa2c

実装してサンプルコードで試す

bがaの親である場合とその逆の場合があるので4通りの場合わけ

提出してTLEなのに気づかずにFに進んでしまった

最後に和を取る部分を再帰呼び出しからループに変換してAC

code:python

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

root = 0

children, parents = graph_to_tree(N, edges, root)

Q = int(input())

for _q in range(Q):

t, e, x = map(int, input().split())

e -= 1

if t == 1:

else:

else:

else:

while stack:

v, x = stack.pop()

stack.append((c, x))

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

https://gyazo.com/d4bea7af88ebfdf425299335ae05b889

考えたこと

完全グラフの個数？

複数の完全グラフに所属する頂点をどうすべきか自明でない

N <= 18, 2^18 == 262144, M <= 153, 2^N * Mは4 * 10^7くらい

2^Mは無理

まず素朴に実装して観察しよう

実装

どこかの完全グラフに所属できるなら所属することを優先して探索し、既知の解とイコールになったら良い解にはならないから探索をやめるアプローチ

素朴に実装してサンプルが通ったので、どの程度TLEになるか確認のために提出したらACした

PyPyで再帰呼び出しで実装していて92msecなので余裕

code:python

def main():

N, M = map(int, input().split())

edges = set()

for _i in range(M):

edges.add(tuple(map(int, input().split())))

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

visit(pos + 1)

ccs.pop()

visit(2)

print(ret)

公式解説

O(3^N)になる

部分集合それぞれについて、その部分集合についてのminを取ってるから

Tweet

ABC187のFは遅いと評判のPyPyの再帰呼び出しで枝刈り全探索してあっさりACしたのでたまたま落とすテストケースがないだけなのか、これで十分なのか気になるなぁ。今のところ落とすケースを僕は思い付かないが。

今気づいたけどPython内で最速じゃん

https://gyazo.com/a9cd5fa4c24664885f7ee963d90e3789

ロクに高速化もしてない(完全グラフになるかどうかの判定で辺の有無を辺のリストを線形になめて調べてるレベル)なのに最速なの意味がわかんない

Python最速の実装についてもう少し言語化を試みてみる。まず頂点1を一つの連結成分とする。頂点2について「既存の連結成分に参加できるかどうか」をチェックする。連結成分の数を最小化したい、参加できるなら+0、できないなら+1なのでできる方を先に探索する。

深さ優先探索で全部の頂点を連結成分にわけて、解の下限Lを得る。探索を進める過程で連結成分の個数は非減少なので、以降の探索では連結成分の数がLに達したらそこより先により良い解がないので探索を打ち切って良い。

やってることはこれだけ。入力が完全グラフの時は各頂点につき「連結成分に入れる、入れない」の二択で、入れる方を優先して探索するのですんなり「全部ひとつにする」にたどり着く。入力に辺がない時は、各頂点について選択肢がないのでこちらもすんなり探索が終わる。

一見やばそうなのが完全二部グラフの時で、1〜9がバラバラの連結成分になった後、10を入れる選択肢が9個になる。枝刈りせずに探索すると9!になるわけだが、深さ優先探索で一旦たどり着いたら、残りは全部打ち切られるので18回くらいの探索で終わる。これは解の下限を把握してることによる。

なお 9! = 362880 なので 3 ** 18 = 387420489 に比べたら1000倍小さい

辺の有無判定をコスト1として、確率pでランダムに辺を張ったグラフのコストを出力する実験をしてみた

Pが0や1の時は153回、pが0.6〜0.8ぐらいで10万を超えてくる

この範囲で1000回試して最もコストが高かったのは0.8 2252973

10000回で7838954

code::

間違えて自己辺も生成しちゃってるけどこの問題を解く上では影響がないので無視してOK

前半を1で埋めて1万件調べるとコスト11750699のものが見つかった

code::

32590993

code::