どうも、ホスフィンです。
会津大学競技プログラミング合宿 2019 (ACPC2019)に参加しました。
(これと全く同じ記事を自分のブログにも書きました)
Day0
毎月買っているコミック百合姫で、楽しみにしていたいくつかの作品が最終回を迎えることになりました。
本当に悲しかったので、毎月百合姫の感想ツイートをしたり、ファンレターを書くことを心に決めました。
昼寝をしたせいで生活リズムが壊れて、ACPC当日の3時過ぎに眠りました。
Day1
朝に愛されているので、朝の6時に起きます。
適当にJRを乗り継いで郡山駅で競プロerと遭遇します。
電車の中では、naanさんとkotatsugame_tさんがTwitterのリプみたいな限界な文体で競プロの話をしてました。(同じボックス席に座っていた女性がイヤホンを付けて辛そうな表情をしていた)
その後、特に何もなく会津大学に着いて、隣で( ˘ω˘ ) ｽﾔｧ…しているこたつがめを見て笑っていると、いつの間にかコンテストが始まる時間になりました。
この日は、ランダムで参加し、チームacpc_mnndrsk でEnderedさんとえびちゃんさんと出ました。
以下コンテスト
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
いつも通りレート順で問題が割り振られる。
まずAを読みますが、日本語が分からずに2WAを生やした。(何？)
問題文の意味が一意ではない気がしたので、enderedさんとえびちゃんさんに介護してもらったりジャッジに質問を投げたりしてAC。
そんなことをしていたらB,Cが通っていた。申し訳ねえ……。
みんなでDを考えるとなんとなくできたっぽい(嘘)
Eもみんなで考えるも、いい感じのDPの状態の持ち方や遷移が思いつかない。
その後は、えびちゃんさんがDの実装をしたり、途中で帰って来たりしていた。
EをEnderedさんと考えていると、「効果時間でソートして長い順に見れば良さそう」と言われるが、これは嘘であると指摘した。
頭を悩ませていると、急にEnderdさんから「演奏時間+効果時間でソートしてみるのはどうですか」と言われ、めちゃくちゃそれっぽいので、一緒に正当性を証明した。(ここはかなりいいムーブだったと思う)
EnderedさんがDPを書いたら通った。
えびちゃんさんがDでWAをたくさん生やしていて、全員で考え直すも、誰も嘘を見破れず時間切れ。
結果は4完
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以上コンテスト
夕ご飯は、yokoと一緒にラーメン二郎に行った。
https://twitter.com/mine691/status/1174298874883670018?s=20
宿泊先の旅館で自分以外の宿泊者の気配がなかったので怯えながら眠りについた。
Day2
うーん、健康的な10時間睡眠！w
朝にチームメイトを募集すると、yokoからリプが来たので、残りの1人をランダムで決めることにした。
ランダムでツバサさんを得て、チームacpc_RamenJiroAizuで出ました。(青水緑のチームだったので少し不安だった)
これからコンテスト
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
yokoがA,私がB,ツバサさんがCを読むことにする。
Bを読む。テンパってぱっと見分からない。yokoがAを通すのでかなり焦る。
ツバサさんがCが解けたと言うので、担当を交代して、ツバサさんがBを読んで、幾何ライブラリを持っている私がCの実装をすることになる。
私が実装を手間取っている間に、ツバサさんがBの考察をして、yokoがBを通す。
1<<17年ぶりに幾何ライブラリを使ったので、使い方を完全に忘却していて、absをnormと書いたりdotをcrossを書いてしまって人生終了。
気づいたら、ツバサさんがIを通す。
ツバサさんに介護してもらいながら、2時間かけてACした。競プロやめろ。
私がバグらせている間に、yokoとツバサさんがMの考察をしていたらしく、私のところに数式が渡されて、「これを式変形してください」と言われる。
「うーん、脳死でwolfwamしよう！」と思ったが、数式を打ち込んでいるうちに二項係数の囁きが聞こえたので、ちょっと考えると一つのシグマとべき乗だけになる。
これは書けそうなので書くとサンプルが通るので、提出するとWAになる。
私のコードを読んだツバサさんがオーバーフローに気づいて、そこを直すと通ってしまう。やめたら？このゲーム
私がコードを書いている間に、yokoとツバサさんがGの考察と実装をしていて、オーバーフローしてWAが出るも無事AC。
yokoはGrundy数を知らなかったのに、その場で教えてもらっただけで解いていてすごい。
すき間時間でツバサさんとやっていたHの考察を進める。包除原理とDPなことしかわからなくて、遷移が上手くいかない。
ツバサさんがいい感じの状態の持ち方と遷移を思いついたので、書いてもらうとACになる。かなり順位が上がった。
残り40分なので、結構解かれているE問題を全員で考える。ここらへんになるとみんな疲れいているので、なかなか考察が進まない。
転倒数っぽいので私のBITを貼って実験したり、提案された嘘を指摘したりしていたら、残り数分になって微妙な雰囲気になる。
頭が回っていなかったのでネットサーフィン(←これなに)をすると、”permutation shift”で検索をかけてしまう。
“On the Permutations Generated by Cyclic Shift”という論文が出てくるので、なんとなく”permutation cyclic shift”と検索すると、この問題が出てきてしまって、提出コードを読んで適当に入力を書き換えると残り1分で通る。なんという†悪魔的行為†
https://twitter.com/mine691/status/1174580017184960512?s=20
自力で通したい気持ちがあったので、とても微妙な気持ちになった……。
結果は8完
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ここまでコンテスト
Day2懇親フェイズ開始(これいる？)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
コンテストで疲れていたので元気がなかったが、食事を摂ると復活する。
お酒を飲める人々が果実酒を頑張って飲んでいたが、いつの間にか新しい瓶が追加されていて、空にするのに苦戦していた。
写真撮影のときに、beetさんとc7c7さんが横になっていて、人々に写真を取られていた。(他の人の参加記を参照するとよい)
未成年が帰ったあとは、わくくんやTABさんと話した。
tsutajさんが、液体(ビール)を服にかけたり自分で頼んだロックのウイスキーを注文したことを忘れて飲んでいて面白かった。
わくくんが日本酒を飲んだら、急に顔が赤くなったので、自分が残りを飲んだ。
全体的に魔境だったが、人の飲酒限界芸は観ていて面白かった。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Day2懇親フェイズ終了
Day3
https://twitter.com/mine691/status/1174813880352038912?s=20
最終もランダムで、チームacpc_matsumoto_riseで、shotさんとninja7さんと出る。
コンテストの始まり始まり～！
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
私がA,shotさんがB,ninja7さんがCを読むことになった。
Aを読むと初修外国語が日本語の外国人でも読める丁寧な日本語で書かれているので、ウィリアム・スミス・クラークに感謝をしながら書くと通る。
Day1とDay2にやらかしたので一安心
Dを先に読むように言われて、Cがコーナーで1WAを出すも通る。
Bの解法をみんなで確認して、嘘を言ってしまうも、メンバーが優秀なので問題なく方針が決まる。(ただし実装は……)
ninja7さんにDの概要と考察を伝えると、桁DPの遷移式を丁寧に考察をしてもらった。
Dの実装を任せてEを読む。
数列の部分和の最大値がO(N)で求められることは知っていて、O(NQ)から落とすパートに入る。
こんなのは明らかにセグ木を使うとよくて、「区間の和は累積和！ｗ」以上の方針は浮かばない。
遅延セグ木とかならできるかな？と思うが、ライブラリを持っていないし使ったことがないので、ネットで調べてこのページを読む。
記事には、セグ木に載せるモノイドまとめという記事のリンクがあり、なんとなく飛んで眺めると、「連続する部分列の和の最大値」という文字の上にこの問題のリンクがある。
読んでみると、E問題の上位互換だった。
そんなことをしていると、Bが通っている。いい感じに順位が上がってきた。
昨日のアレがあるので、チームメイトに伝えるのは憚られたが、Eは既出であることを伝える。
実装することが許されたので、人の提出を引っ張ってきて、よしなにして提出をすると通る。beetさんに感謝！
https://twitter.com/mine691/status/1174896166921572352?s=20
そんなこんなでDも通る。これで5完
残り1時間なので、休憩をしながら考察をするも、いまいちいい方針が立たない。
ninjaさんに、長さkの部分列を全部含んでいるか+Sが分割可能か(そういう部分列で被覆できるか)みたいな必要条件を提案され、十分性の反例が挙げられなかったので取り敢えず書いてもらう。(RHとセグ木でできる)
なんとこれが通ってしまった。更に順位を上げる。
結果は6完
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
コンテスト終わり終わり～！
帰りはyokoとJRで仙台に帰りました。yukicoderがあったので出ました。
実は、ここ1ヶ月はCodeforcesの問題ばかり解いていて、日本語で競プロをするのが久しぶりでした。
来月以降はやりたいことがあって、競プロにどれだけ時間が割けれるか分かりませんが、こういうオンサイトは参加し続けたいですね。