hogecoder

tsutaj 競技プログラミングの記録

ACPC 2019 参加記

勉強会参加記

会津大学競技プログラミング合宿 2019 に参加しました。昨年に引き続き、2 年連続 2 回目の参加でした。

Day0

JAG 夏合宿 (参加記へのリンク) の後だし、休むか・・・と思っていたはずなんですが、昼からひたすらボドゲカフェでボードゲームをし、やよい軒で優勝し、泊まるために適当に寄ったネカフェがオープン席しか空いておらずオープン席で浅い睡眠を取る始末。休むどころか体力を消費していませんか？？？

Day1

早朝に東京から会津へ向かうバスで移動。なんだかんだだいぶ疲れていたのでひたすら寝た。

時間ギリギリすぎてタクシーを使って大学に来たら風船を持った会津勢に遭遇。tubuann さんに会場まで案内された (ありがとう)

自己紹介とスポンサーセッションを終えて、コンテストへ。チームメイトが決まっていなさそうだったりあんさんに声をかけて組んでもらうことになった直後に、tubuann さんが組みたいと言ってくれたのでその 3 人でチームを組むことになった。

チーム名は acpc_tubutsutatkb です。由来は内緒です。

競技プログラミングをしてレートが低い順に前から問題を開いて解く戦略にした。自分は A を読んで、解ける問題だったので通す。FA は逃した。ゆるせね〜

B はいつの間にか通っていて、C は SCC を貼るといけるとりあんさんに言われたので自分が実装して通した。

C を書いている間にりあんさんが D を、tubuann さんが E を詰めていた。自分が代わる代わる解法の相談に参加していた。りあんさんが D を通していたり tubuann さんがソートでうまく行くことを証明して通していたのでこの辺はほとんど何もしていません (すみません・・・)

F はとりあえずそれはそうみたいな解法が生えて、tubuann さんが書いたが TLE した。しかもこれは制限時間 +0.2s くらいの TLE だったのでなんとかなりそうな見た目だった。闇みたいな高速化を色々試したが惜しくも通らず残念。

G はフローだろうなぁという話をりあんさんとしていて、考察してはコーナーを見つけを繰り返していたらコンテストが終わっていた。悲しいなぁ・・・

夕食はステーキ宮でした。

ホテルに帰ったらロビーにボドゲ勢がいた。ビール飲みながら観戦してた。

Day2

この日は事前にチームを組んでいて、idsigma さんと olphe さんと出た。

なぜか自分が C 問題の担当になったので読む。数学ですが・・・角度の計算どうするんだ、となったけど冷静になると atan2 という関数がありましたね。olphe さんに少し確認を取りつつ AC した。割と速い方だとは思うんだけど FA は逃していた。ゆるせね〜

M がめちゃくちゃ通されていたので見る。そんなに簡単でもなくない？と思いつつも二項係数っぽいので式を書くとできそうな気持ちになる。olphe さんに渡して AC

H, I あたりが解けそうだけどすぐにはわからない。しばらく考えたら解けたのでどっちも書いて通した ( ModInt を二回連続で貼った)。このへんは結構仕事できてよかった

自分が H, I あたりをやっている間に idsigma さんと olphe さんが G を詰めてくれて、出したら一発で通った。ありがたい

ここからはしばらく停滞したものの、「もうこれで一回提出して情報を得ても良くない？」ということで E を投げたら通って草。さらに L のバグも直って一発 AC。書いた idsigma さんが偉すぎる。

その後は F を解こうとして自分の CHT を olphe さんに渡して一緒にコードを書くもサンプル +α くらいしか通らなくてコンテスト終了。これが解けていればオンサイト優勝だっただけに悔しいな、ありえね〜

解説が終わると懇親会がはじまりました。

いくらかおもしろいことがおこったようですが自分は記憶がないのでわかりません (は？)

真面目に書くと写真撮影の前に机などをどかすところまでは覚えていて、その後は・・・という感じです。気をつけましょう。

Day3

なんだかんだ朝 5 時半くらいに普通に起きて、いろいろ身支度をして会津大学に向かう。

朝会ったら「元気そうで安心しました」みたいなことを何度も言われましたが、当の本人は何も覚えていないため、普通に反省をしました。

この日はジャッジ側だったのでセットについて簡単に感想戦をします。

北大セットについて

まず HUPC 2019 (参加記へのリンク) の影響で問題ストックが割と減っていて、なおかつ新しく生やしている時間も無いし、正直かなり困っていました。そこで過去に出ていた原案をかき集めたら意外となんとかなりそうだったのでそのまま問題を決めました。こういう経緯もあって、原案が 1 年前だったとか、そういう問題が半分くらいあります。

自分は A, D, G の Writer をしたのと、F の高速化 (制約を上げた)、全問題の Tester をしました。それぞれ簡単に触れておきます。

A 問題

元々は別の問題が assign されてましたが 1 ヶ月前くらいに ABC で全く同じ問題が出てしまって使えなくなりました。そこで自分が A 問題枠を 3 問くらい適当に生やしてその中から決めることにしたのですが、これはそのひとつです。それ以外は特にいうことないです。

B 問題

問題文担当がつらそうでした。要求されるのはほぼほぼ実装力です。

C 問題

例のケースは Writer が突然思いついたもので、追加したら Tester 全員の解法が落ちてウケました。注意力がないとペナが生えるので注意力は大事なんですが、今回に関しては一発 AC が誰もいなかったのでペナルティの意味がなくなりました。

D 問題

総和を求める桁 DP ってあまり見ないかも、と思って作りました。もっと解かれるかとも思っていましたが、最終的にはいい感じの AC 率に収まったようです。

E 問題

開催 3 日前くらいに既出を指摘したんですが、どう考えてももう少し早く言うべきで (JAG 関係で余裕なかったから許してほしい・・・)、どうにもならないのでそのまま出しました。抽象化の練習にご活用ください。

F 問題

最初の計算量は O(|S| \log |T| + |T|^{2}) くらいだったんですが、速くできたので出しました。EF 続けてギャグみたいになってすみません。

G 問題

1 年前に生やした問題で、解法を書きたくない + テストケース作りたくない + 問題文書きたくない が原因で放置されてました。ストックの枯渇により泣きながら出しました。コンテスト中に二乗解法が通された。ありえね〜ゆるさね〜 (話を聞いたところほぼほぼ AC 解法だったので、まぁよかったのですが)。甲子園をテレビで見ながら Tester 解を書いた記憶があります。どうでもいいね。

全完が残り 10 分前後に出て、なおかつ 1〜2 チームくらいしか全完されない、をひとつの指標にセットを作っているつもりなのですが、概ねうまくいってよかったです。参加してくれた皆さんありがとうございました。

おわったあとは学食に行きました。

総括

酒は飲んでも飲まれるな

今年もコンテスタント側・ジャッジ側両方参加できてよかったです！今回の自分たちのセットがなんらかの勉強になってくれれば幸いです。来年から社会人なので次行けるかどうかはわかりませんが、またどこかのオンサイトでお会いしましょう〜