hogecoder

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

HUPC 2019 参加記

勉強会参加記 作問

HUPC 開催の経緯

これまで自分が RUPC や ACPC などの他大学の競技プログラミング合宿に参加してきて、自分も合宿を主催して他大学の (特に北海道の) 競技プログラマと楽しみたいという思いがあって、開催することにしました。やると決めたからにはたくさん頑張ろうということで、実際いろいろ頑張りました。

実際に日程を決めるときはちょっとだけ難航しました。というのもすでに他の合宿やコンテストの予定が入っていたり、冬は交通機関の乱れが心配であったりと、なかなかいい日程がありませんでした。せめて 3 連休にできたらいいよねということで、7 月の 3 連休を取ることにしました *1

運営としてやったこと

4 月

まず先述の通り、開催するということと具体的な日程を決定しました。また当時 Twitter アカウントがなく広報するにあたって不便だったので、サークルの Twitter アカウントを作ることにしました。

Day1 は北大勢で作問することになっていたのですが、Day2 は有志で作問してくれる方を募集しなければならなかったので、募集しました。最終的に自分含め 5 人で作問してくれることになり、非常に心強かったです。作問してくれた 4 人 (drken, idsigma, tempura0224, tubuann) の皆さん、ありがとうございました。

5 月

会場の予約をしました。当初学内の教室などで開催できたら良いなと思っていたのですが、弊学はケチなので休日に教室を学生に貸し出していなかったので、外部の貸室を利用することにしました。後でまた書きますが、スポンサーのフィックスターズ様が会場費をサポートしてくださったので、大変助かりました。

会場が決定したので定員や懇親会会場を決定することができて、ATND を公開したり懇親会会場を仮予約したりしました *2。

この時期にフィックスターズ様と連絡を取り、スポンサーとしての参加交渉を行いました。快諾してくださりありがとうございました。

6 月

会場は下見ができたので、プロジェクターの動作確認 *3 やネットワークの確認をしたりしました。

作問作業が本格化して、この解法は落としたいとかを考えて制約を変えたりなどの試行錯誤をしました。

7 月

ATND の登録を締め切って懇親会の人数を確定させました。あと懇親会後に AGC が入ったので時間をずらす必要があって、そのへんをお店に再度連絡しました。

直前になってお菓子や飲み物、ウエットティッシュなど必要なものを購入しました。この辺で仕事を分散しはじめていて、名札を rsk0315 君に作ってもらったり、買い出しをみんなでしたりしました。協力してくれてありがとう。

あとは受付表を作ったり会計をしたり問題文を印刷したりなど細かいことをいろいろやりました。

合宿当日の流れ

Day0

てんぷらくんが家に泊まりにきました。一緒にジンギスカンを食べました。

Day2 どれくらい解かれるかな〜、あんま解かれへんやろ〜、みたいな話をしてた気がする。

Day1

いろいろ荷物を運びながら会場に向かいました。あまりにも荷物が多かったのでてんぷらくんにお菓子と飲み物を持たせてしまってもうしわけない

会場とコンビニが近かったので飲み物を買い足したりとか、色々準備をしていたら受付の時間になって、続々と参加者が到着してきました。

最初に自己紹介とスポンサーセッションがあり、その後チーム分けをしてコンテストです。

北大セットでは A と G の Writer と F の原案魔改造、G の問題文、C・D・E・G のデータセット、全問題の Tester を担当しました。G は前々から出そうと思っていたテクだったので出せてよかったです。後で Twitter みたら参考にした論文の著者から言及されていてびっくりしました。

その後は懇親会でした。写真撮影を店員にお願いしたのですが、わざわざ扉を取り外して撮影してくれてサービス力を感じました。

Day2

コンテスト時間が早いので早起きします。ねむい

チーム分けをして、Day2 コンテスト開始です。序盤から ushitapunichiakun が爆速で問題を通していて荒らしか？とか言ってました (失礼)

Day1 より全体的に少し難しめかな、と想定したセットでしたが、最終的にオンサイト 1 位が 6 完でオンラインで全完が 2 チームあったので、かなりいい難易度バランスだったのかなと思いました。

ちなみに自分が Writer をした問題はセットのバランスの都合上なくなりました。Tester は全問題やりましたが、忙しすぎて AC 確認くらいしかできなくてすみませんでした・・・ (後半は他のスタッフに頼りっぱなしでした)

夕食はすしをたくさんたべました。

総括

おそらく前例のない、北海道での大学主催合宿を思い切ってやってみました。もちろん不安でした。人が十分に集まるかどうかもわからないし、最悪北大のオフ会みたいになるかもしれないと思っていました。

しかし終わってみれば総勢 35 人が参加してくださり、北大以外の北海道勢や道外の競技プログラマも多く参加してくれました。本当にありがとうございます。

準備は大変でしたが合宿当日はすごく楽しくて、あっという間に終わってしまいました。いろんな人に楽しかったと言ってもらえて嬉しかったです。

また問題セットも概ね好評という印象で、とても良かったです。同時に 2 つのセットを運営するのはかなり大変でしたが最終的になんとかなってよかったです。

来年には社会人になるので来年以降に合宿が開催されるかはわかりませんが、もし開催されてスケジュール的に行けそうならぜひ参加したいと思います。

さいごに、北海道でも競プロ合宿が開けることが証明できてよかったです。実際に合宿に来てくれた皆さん、オンラインで問題を解いてくれたみなさん、Day2 の問題セットを用意してくれた皆さん、スポンサーになってくださったフィックスターズ様、運営してくれた北大勢、その他合宿に関わってくれた方々に感謝して参加記のむすびといたします。

*1:これでも ICPC 国内予選が被りかけたので、そこは反省点です

*2:その時点では参加人数が確定していないので、適当にこれくらい来るかなあと見積もった人数で予約しました

*3:動作確認したんですが、当日は動かなかった・・・

ACM-ICPC 国内予選 2019

ICPC 大会参加記

ICPC の国内予選に参加しました。今年も four-t として rsk0315, TAB, tsutaj のチームで出ました。

f:id:tsutaj:20190713015212p:plain

弊学からは 7 チーム出て、全チーム 3 完でした。昨年に引き続き今年も 2 チーム通過している見込みで、ひとまずは安心です。しかしもう少しがんばりたかったなあというのもあります・・・。

コンテスト

早解き芸人を担当しているので開始直後に A を読みます。というのは嘘で、問題文を見ずに include とか main とかを書いていて、印刷された問題文が来ないのをいいことに「問題概要読んで伝えて！」と rsk0315 君に頼みます。言われたとおりに実装したので結局一度も問題文を読まないまま書いてサンプルが合ってそのまま AC しました。チームプレーですね。

B は rsk0315 君が、C は TAB 君が考察と実装をしていたので、任せて D を読みます。dp[i 番目のカウンタまで見て][直前のカウンタの操作から j 回分借りてくる] := 操作回数最小 みたいな方針が立ちますが、まずサンプルが合いません。グダグダしてたら B と C が通っていました。

よく考えると D のサンプルを手で試し間違えていたので少し考察すると、とりあえずこうかなぁみたいなのが生えるので書くとサンプルが合いました。しかしテストケースは通りません。

ここからは実質何も出来ませんでした。j 回分借りてくるのは M 未満ではなく 2M 未満で考えたほうがいいのかなと思いつつ、それでも合わず。悔しかったです。

反省

序盤は特に反省することはありません。しいて言えば A の FA を 17 秒差で逃しました。

後ろの問題を時間かけてでもいいから通すくらいの実力が欲しくて、解説を見ずに粘り強く考えて通すみたいな練習をすべきなんですかね・・・ギリギリ通せるか通せないかくらいの問題をたくさんやりたいです。

何はともあれ次の大会に駒を進めることは出来たので、アジア地区までにもう少しがんばりたいと思います。

JAG 模擬国内予選 2019

ICPC チーム練

JAG の模擬国内予選 に参加しました。チーム結成 3 年目にしてようやく、初の全員揃っての参戦でした。

模擬予選の様子

自分は A の担当になっているので開始直後から読む。いけそう。一応オーバーフローとか入出力ミスとかそのへんに気をつけながら実装して AC。

B は rsk0315 君が、C は TAB 君が担当していた。C をチラ見していたけど自分がたくさん助けられそうな問題ではなさそうなのと、TAB 君なら解けそうなのとあって、一旦任せて D を読む。

D は編集距離とかなり似ている、というか Rotate がなければそのまんま。頑張れば解けそうなのでしばらく考える。しばらくすると B が AC されていたので rsk0315 君と解法を相談してみたところ、最初に考えたことが完全に嘘なことがわかる (これ早めに気づけたの結構良かった。危ない) Rotate は区間を任意にもってきてやるわけじゃなくて先頭から末尾へしかできません！

そんなこんなで色々考えたところ、最初考えていたものよりも楽そうなことが分かる。とりあえず気持ちを実装するもサンプルが微妙に合わない。ここでやっと、削除は Rotate 前にやって追加は Rotate 後にやるとお得なことがわかって、編集距離の遷移時のコストを変えないといけないなぁとなる。

rsk0315 君と TAB 君が相談してたら C の解法が生えたらしいので、バグっている D のソースコードを共有してもらいながら C を書いてもらう。rsk0315 君が実装している間に TAB 君に D の実装を説明しながらバグを探してみる。

説明してたらコストをミスってるのがすぐわかって、直すとサンプルが合う。出したら通る。やったね。

まだコンテスト時間が半分近く残っていたのでもう一問解きたいとなる。E を見たけど見た感じ不可能にしか見えないし一旦飛ばす。F は構文解析 (つらいらしい) で、G は幾何で、H は数え上げらしい。

H を考えてみた。三乗が許されるのであれば DP と重複組み合わせで行けるが、当然不可能なのでなんとか削減できないかずっと考えてた (でもわからなかった)

rsk0315 君と TAB 君で G を詰めていて、書けそうらしいので書いてもらう。ちょいちょい直していくとサンプルは合うも、出すと Wrong Answer になった。検出すべきものができていなさそうな挙動をしていたのでバグとかアルゴリズムの間違いとか色々考えたけどここで時間切れになった。

反省

前半に関しては担当の割り振りはあれが最適だとは思うし、チームメイトのおかげで D の考察や実装で過度に時間を消費しなくてよかった。

問題はその後で、まず E を TAB 君と相談した記憶がなく、相談する前に捨てモードにいったのが本当にもったいない。ちゃんと相談すべき。しかも模擬予選前日にこれを解くために必要なライブラリをわざわざ整備していたので割とショックだった (本番のときは本当に何もわからなかったのでしょうがないんですが・・・)

あと自分が G の問題文を読むのが遅すぎて G のデバッグのときに題意があやふやで申し訳なかった。手が止まってしまっているときにちゃんと読むべき。

さいごに

何かと反省は多いですが、本番もがんばりたいですね。いい結果にしたいです。