NOSSの雑記

主に競プロでやったことを書きます。

ACPC2019 参加記

参加記 AOJ

9/18-9/20に行われた会津大学競技プログラミング合宿2019に参加してきました。

Day1

会津に向かうバスの中でgoodbatonさん、idsigmaさん、ninja7さんに出会う。
会津駅からgoodbatonさんがタクシーを予約していたので4人で相乗りさせてもらい会津大学に到着！

集合時間まで時間があったので一緒に学食を食べに行く。ソースカツ丼をいただきました。

コンテスト前にツバサさんやyamadさんとお久ぶりですね?(2日ぶり)みたいな話をする。JAG合宿からACPCに来ているひと多すぎる。

お菓子置き場にいくとキュウリが置いてあって困惑した。

コンテスト

チーム ACPC_UKUNICHIBで参加。
メンバーはNOSS, c7c7, Hyado

AをHyadoさん、Bをc7c7さん、CをNOSSが読む。

A,B,Cは特に問題なくAC

Eを読むと貪欲っぽさを感じるが優先順位がよくわからない。DPだと選ぶ順番によって解が変わるので不可能だなあ。わからないので一旦断念。

c7c7さんがDを読んでいたので概要を聞くと橋の耐久度が小さい順にまわるのが良さそう、という話になる。考察を詰められたのでc7c7さんに実装をお願いするとAC！

この間にHyadoさんがEの考察を進めていてくれて、R+Tの降順に選択すれば最適だと示してくれる。それならDPができるので、個数制限なしナップサックの要領で解ける！僕がE書いてAC！

Fは不可能そうなのでGを考察する。無限に場合分けが発生しつらくなっていたらコンテストが終了した。

結果はABCDEの5完でした。

コンテスト後

ホテルの部屋に荷物を置いて富士の湯の温泉に行く。富士の湯とてもオススメです。

Day2

コンテスト

チーム ACPC_renkon99yenで参加。由来はチラシに載っていた商品。
メンバーは TAB, drogskol, NOSS

Bを読むが問題を誤解をしWAを吐く。この間にTABさんがA,Cを通す。CはオンサイトFAでした(すごい)。
TABさんにBを読んでもらうと一瞬で正しい解法がもらえてすべてを理解する。BをAC。

この間にdrogskolさんがDからMの問題を読んでもらっていたので概要を教えてもらう。

Hが解けそうな気がしたのでHをもらう。 Hは余事象を包除原理的に求めるだろうということが分かったので式を組み立ててみるが、サンプルが合わない。

Hを考察している間にdrogskolさんがM,TABさんIを通す。

かなりの時間悩んだ結果、「K種類の文字からちょうどK種類の文字を使った長さNの文字列の個数」以外は包除がうまく取れないことが感じられて、これをもとに式を立て直すとサンプルが合い始める。N,Mが大きすぎて計算途中でオーバーフローしている部分があったのでそれをチームメンバーに直してもらいAC。

次に通せそうなのがE,GあたりっぽいのでGを考察してみる。
1つのポケットのGrundy数に注目すると遷移が高々2であることからGrundy数は3未満であることが分かる。dragskolさんに実験コードを書いてもらうと明らかに値が半分になるたびに性質が変わる周期性がみれるので、場合分けで値が求まらないか実験をする。

TABさんがLが解けたそうなのでこの間に実装をお願いする。途中で強連結成分分解が必要になったそうなのでライブラリを提供する。

Gの実験から場合分けを書くが、if文だらけの嫌なコードになってしまい苦しくなる。サンプルがあったので提出するもWA。 場合分け漏れ...

終了時間がせまり、TABさんが一生懸命Lのデバッグをしているのを祈るように見る...と、終了1分前でLがAC！TABさんすごい

結果はABCHILMの7完でした。

懇親会

早稲田勢+goodbatonさん+mtsdさんの卓に座る。全員成人済なのにお酒を飲む人が数人しかおらず未成年卓並みに治安が安定していた(?) (ある卓ではAtCoderレートが高い順から好きなだけ料理を取れるということが行われていたらしい)

学生RTA勢の話や早稲田の先輩の話を聞いたり、会津の人から作問の話を聞いたりした。

早稲田勢が温泉に行った後mtsdさんとgoodbatonさんからアルゴリズムの解説を受けた。アルゴリズムの話なのになんであんなに面白かったのか思い出せない(?)

楽しい懇親会を開いてくださったfixstarsさんありがとうございます！

Day3

コンテスト

チーム ACPC_ROISAIで参加。由来はchokudaiさんが労災の話をしていたので。
メンバーは NOSS, Endered ,suta

sutaさんがA, EnderedさんがB, 僕がD,Cを読む。

Bは実装がやばめの問題らしいのでEnderedさんを応援する。
sutaさんがAをACしたので、そのままCの概要を伝える。

Dの桁DPが固まったのでBの合間に実装する。添え字をバグらせつつもサンプルが合うので提出するとAC！
Dを実装している間にCの解法が生えたのでsutaさんに伝える。そのまま実装をお願いしてE,Fを読み始める。

Cのサンプルがあったので投げてもらうと...WA。Bもバグに苦しんでいて大変そう。

ついにBが通る。Enderedさんありがとう。

sutaさんがCで解が0になる場合に正しく動作しないことを発見する。修正するとAC！

みんなでEを考察する。なんとかセグ木に乗りそうな形に落とし込めたので実装する。自明なバグを修正しつつも手製のサンプルケースが通らずコンテスト終了。

結果はABCDの4完でした。

感想

いろんな人々と交流ができて非常に楽しい合宿でした。

コンテストはレート黄色枠として参加しましたが実力不足を感じて「次こそはもっと問題を解いてやるぞ」という気持ちが強くなりました。

また来年も参加できるといいなあ。