ARC111

ARC111, A, B, Dの3問でした。事前の調整をミスって電話が来てしまうミス(?)

CのREはDのコードを間違えてCに提出したもの。

https://gyazo.com/c806e1bd22db961b5487a6bb0b885268

https://gyazo.com/8e62ccc2503c21825f8e911cd021e199

考えたこと

M^2であまりを取れば良い

ループ検出？M^2のテーブルを作ると10^8だからダメそう

AC

code:python

def main():

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

M2 = M * M

for i in range(60):

doubling.append(

)

ret = 1

for i in range(60):

if N % 2:

ret %= M2

N //= 2

print(ret // M)

https://gyazo.com/0054886e607d84a63a9f6c1e35ea53ce

考えたこと

色がグラフの頂点、カードが辺、辺のどちらかの頂点を塗ることができる、塗る頂点を最大化したい

典型的なグラフの形をいくつか考える

パスでも木でも辺の本数だけ異なる色を選べる

ループなら全部選べる

自己辺がある頂点は必ず塗られる

位数1の頂点は必ず塗っても最適

それ以外は？

決まってない辺を選んで2通り試す？

20万本の辺が全部バラバラであるケースで2^200000でヤバい

自明な上限として辺の数

連結成分に分ける

異なる連結成分は何も影響しないから

連結成分は連結であるのでE>=V-1

E=V-1の時、色はE

それより大きい時、色はV

自己辺ある時は？

気にしなくて大丈夫

普通に辺の数を+1するだけで良い

上記の計算にマッチする

実装

頂点の数と比較して答えを出す

AC

code:python

def main():

N = int(input())

init_unionfind(400000 + 1)

for _i in range(N):

a, b = map(int, input().split())

ra = find_root(a)

rb = find_root(b)

if ra == rb:

else:

unite(a, b)

rc = find_root(a)

from collections import Counter

ccs = Counter(find_root(a) for a in range(1, 400000 + 1))

ret = 0

for cc in ccs:

if E == V - 1:

ret += V - 1

else:

ret += V

print(ret)

コンテスト後Twitter

TLEギリギリらしい

「どうしたらグラフだという発想が出るのか」

なるほど、どうしてだろう

自分のメモを見返したら、特にはっきりした「気づき」を経ることなく、サンプルを絵に描いて理解しようとする流れでグラフになってた

https://gyazo.com/3430ad1cdf4888f904042d9966fc36a2

あえて言葉にするなら、この問題はカードの順番を入れ替えても答えに影響しないし、裏表を変えても影響しないので、与えられた配列の形を維持する必要性がないよね、ということで、もっと柔軟な形で持つ感じ

木かどうかの判定で良い理由の簡潔な証明

連結成分の全域木を考える

全域木以外に辺があるなら、その頂点の片方を塗って、その頂点を根にすれば全部の頂点が塗られる

Cがよくわからないので飛ばしてDへ

https://gyazo.com/077328c4ec18b1260a4a7ecc2347abc2

考えたこと

ある頂点から到達可能な頂点の数が与えられていて、辺を方向づけする

当たり前だけどaからbに辺がある時にca<cbになることはあり得ない

そんな簡単なはずはないと思うが、とりあえずそれで実装してみる

ああ、イコールの場合にどちら向きにするかが自明ではないのか

サンプル1が親切

到達可能頂点数がイコールである頂点の間のグラフが与えられて、それを強連結成分にする

辺を深さ優先探索すれば良い(頂点ではなく)

code:python

def main():

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

from collections import defaultdict

edgelist = []

for _i in range(M):

frm, to = map(int, input().split())

edgelist.append((frm - 1, to - 1))

CS = list(map(int, input().split()))

answer = {}

edges = defaultdict(list)

for v1, v2 in edgelist:

else:

for v1, v2 in edgelist:

if (v1, v2) not in answer:

def visit(e):

(v1, v2) = e

if v3 == v1:

continue

if (v2, v3) in answer:

continue

visit((v2, v3))

visit((v1, v2))

for v1, v2 in edgelist:

https://gyazo.com/234ff93b5a7a9fc5540fb638e59fc11c

全く方針が立たず提出に至らなかった

考えたこと

NlogNくらいになるのかな？

交換して大丈夫なら交換する？

自分が持ってる荷物の本来の持ち主が持っている荷物を自分が持てるなら交換？

解があるのに交換できない事態に…

最も重いものから動かす？

それを持って良い人が限られる

重いものを渡す時に帰ってくるものが重いかもしれない

コンテスト後Twitter

重い荷物から順に、正しい持ち主にわたすようにすればいいね！　渡される側は、正しい荷物になるから重さを気にする必要はなくて、渡す側は軽い荷物と交換になるから、その後も困らない

なるほど「重い順」と「本来の持ち主」の両方か…

考察

どんな貪欲法をやれば良いか気づくにはどうすれば良いか

今回の問題は人間の並び順には意味がないので無視するべきだった

今回の場合の「端」は並び順ではなく荷物の重さ

Twitterを見ていると「最も力の弱い/強い人」というパターンも。

最も重いものを本来の持ち主に動かした時に疲れる心配がないことに気づかなかった

最適であることの証明、下界に一致

E

考えたこと

https://gyazo.com/4f6d08eaac17b40c5ef930413c494468

コンテスト後のTwitter