memo46

競プロの精進記録その他。

ACPC 2021 参加記

伝えよう　運営への感謝の気持ち

Day1

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day1

suta、Chrisとチームcbio_labで参加した 余談ですが、この3人は同じ研究室で、この日は研究室から参加しました

A：僕が担当した。誤読して1ペナしたけどsubmission見たら無限人WAを出していて察した。問題文をグッと睨むと誤読していたので直してAC

B：sutaが「なるべく少ない個数で全体のORを作りたい」と言っていて、高速ゼータ変換を考えていたけどうまく定式化できなかった。 or_convolutionってこうやって使うんですね...　作れるかどうか <-> 作り方が1通り以上で、高々log(max(A_i))回の畳み込みで出来るの確かに upsolveで319でも通しました

C：やばそうだったので飛ばした

D：読んでない

E：Chrisが粘着していて、僕も概要聞いたけど解ける気がしなかったのでskip

F：一番粘着した。でも解けなかった。こういうの本当に無理...　めっちゃいい問題で涙......

G：dp[頂点 i まで見た][行きの最後の頂点][帰りの最後の頂点]で3乗で解けるなあと思っていて、よく考えると行きと帰りの最後に訪れる頂点の片方は必ず i になるから2乗で出来そう、といったらsutaが細部を詰めて実装してくれた　良問

H：全く見ていなかったがコンテストが終わった後に見たら単純な桁DPで涙　桁DPは実装がやばいって言われがちだけど、この実装を真似ると簡潔に実装できます

opt-cp.com

I：見てない

感想

めちゃくちゃ冷えた。典型だけどちゃんと考えないと解けない良問が多くて、農工大はすごい

Day2

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day2

kiyoshi0205, Hiramonとチームmo_ri_fantasyで参加した。

A：Hiramonがやってくれた。少しデバッグを手伝った

B：普通に解けなかった（大反省）今もバグっています（は？）

C：Bを一旦飛ばしてCを見たら自明だったので幾何ライブラリを貼ってすぐ書いてAC。全体2位だったらしい。doubleでやると誤差で死ぬらしいけど、運がよかったのでACできました・・・

D：問題名が答えです　最近類題を解いていたのでCの後にすぐ書いてAC

E：クエリ毎に包除したいけど間に合うわけね～→kiyoshiに投げよ・・・　ところで、distinctだと素数は高々7個までしか取れないのでクエリ毎に包除しても間に合うらしいです 悲しい

F：やばそうと思ったけど二度見したらにぶたんだった。kiyoshiがEを書いたあとに僕が書いてAC

G：kiyoshiが解いてくれた。実装に苦しんでいたようだが終盤にAC

H：kiyoshiが初手で解けたと主張していたけど1hバグっていたので一旦放置することになった。結局最後までAC出ず

I：同じ人が含まれるサークル同士に辺を貼ると最大独立集合問題に帰着。この制約で半分全列挙で解けることは昔ECRバチャでやりました

J, K：見てない

感想

今日のセットは典型詰め合わせセットって感じだった、楽しかった | 会 | 津 | 大 | 学 | はすごい

Day3

https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day3

Day1のチームにserpent君が加わって、4人で参加

A：serpent君がやってくれた

B：Chrisがやってくれた

C：僕が担当だったけど全然解けなくて焦った。Bを終えたChrisと相談して解けた気持ちになり僕が実装→AC

D：sutaがなんかエスパーして解いてた

E：こういうのはどうせ鳩ノ巣→そうでした　間に合うか怪しいDPを書いたけど配列を使い回すと爆速になったらしい

F：Chrisとsutaが一生粘着していたけど苦しそうだった

G：こういうのはどうせ知識→KUPC2012Kがヒット→頂点属性で解けるのかこれ・・・

ここでしばらく困っていたけど、よく考えたら距離3の箇所は同時に取れる(C - 3 Steps の考察を使う)ので二部グラフかどうか判定すると、二部グラフじゃないなら完全グラフになるのでXOR基底を取ると解けて、二部グラフなら完全二部グラフになるので困りました...

数列Cから偶数個・奇数個取ったときのxorのmaxが求められなくて困っていたけど、Twitterで教えてもらった方法が天才で感動した

感想

どの問題も見た目は難しいけどちゃんと解きほぐすと解ける感じですごい　良問の既出チェックって難しいんだなぁ... 北大はすごい

全体の感想

Day1～3までフル参加で楽しめました。 運営の皆様、お疲れさまでした & ありがとうございました！