【競技プログラミング】HUPC2023にオンサイト参加してみた!【参加記】

大志を抱け! 霧しゃまです。
去る2023年5月4日、中の人(Kirishima)が北海道大学競技プログラミングサークル(HCPC)の主催による有志コンテスト、HUPC2023にオンサイト参加してきました。
様々な学びがあったので、記事として紹介していきたいと思います。今後オンサイトコンテストに参加される方々の参考になれば幸いです。

忙しい人向けのまとめ

  • 楽しかったです! 運営、チームメイトのみなさまありがとうございます!

  • AOJを普段やらない人は、仕様の違いを知っておきましょう!

  • チーム戦は難しいけど、積極性が大事かも?

HUPC2023とは

いくつかの大学の競プロサークルでは、毎年有志コンテストを開催することが慣例となっているようです。東京大学のUTPC、京都大学のKUPC、東北大学のTUPCなどがあります。
HUPCもそのような、大学の競プロサークルによる有志コンテストです。そして、AtCoderなどで開催されている普段のコンテストと大きく2つの点で異なります。

  • オンサイト会場が設けられる

  • チームでの参加が認められる

今回はこのオンサイト会場で、コンテストに参加してきました。もちろん、ジャッジシステムはインターネットで一般に公開されているので、参加自体はどこからでもできます。
チームでの参加は、普段のコンテストではなかなかできないこと(ルール上認められていないため)です。オンサイト会場でなくてもTwitterなどでチームを組んで参加はできますが、オンサイト会場であれば、その場で適当にチームを組んでくれるので、「チームメイトが見つからずソロになってしまった」などということはありません。

HUPC2023のオンサイト会場は、北海道大学でした(主催が北大なので自明に見えますが、そうでもないようです)。今回たまたま近くにオンサイト会場が来たので、Kirishimaは様子見のつもりで参加を決めたというわけです。
本当は5月4日から6日までの3日間のスケジュールですが、諸般の事情により、初日の5月4日のみ参加しました。3日間でそれぞれ1セットずつコンテストが行われているようです。

持ち物について

まずは持ち物です。とりあえずコンテストに参加するためには、

  • PC(電源コードやマウスなどの周辺機器も含む)

  • 考察用紙(会場でも準備があります)と筆記用具

  • 飲み物など

このくらいあれば困りませんでした。会場によってはWi-fiが使えない場合もあるようですが、今回は大学側のWi-fiが利用できました。
あとは、普通に出かけるときのように、必要に応じてスマホのバッテリーなどを持ち込むと良いかもしれません。

AOJについて

AOJ(Aizu Online Judge)とは、会津大学が提供するオンラインジャッジシステムのことです。AtCoderとほとんど同じです。HUPC2023は、AOJを利用していました。
『プログラミングコンテスト攻略のためのアルゴリズムとデータ構造』(通称、螺旋本)はAOJ上のカリキュラムに基づく本なので、これでAOJをやったことがある方もいるかもしれません。やったことがあれば、AOJの使い方や仕様もとりあえず把握できていると思います。
しかし、普段AtCoderしかやっていなくて、まったくAOJに触れたことのない人が「AtCoderと同じ」だと思ってAOJをやると、いくつか躓くポイントがあります。大きく、次のようなところです。

  • 言語の選択

  • 提出の操作方法

  • ジャッジ結果の表示

  • コードテストがない

まず、言語です。これが最大の落とし穴だと思うのですが、AOJで"C++"とだけ書いてあるものは、古いバージョンです。具体的にどのバージョンかはわかりませんが、AtCoderで現在使われている"C++17"よりは古いバージョンです。これによって、"CE(コンパイルエラー)"を起こしてしまう可能性があります。
AOJでは言語選択で"C++17"が選べるので、C++を使う人は、しっかりこれを選びましょう。

提出の操作方法も、"Workspace"画面のUIが若干わかりにくいのもあって、慣れていないと誤った提出をしてしまいがちです。

AOJの提出画面の様子

コード貼り付け欄の上に、問題選択欄(左)と言語選択欄(右)があります。特に、"Workspace"画面を開いたとき、問題選択欄のデフォルト値がA問題になっているので気をつけましょう。間違ってA問題に提出してしまう事故が何度か起きています。
個別の問題ページの最下部にある"SUBMIT"ボタンからこの画面に来ると、問題選択欄に見ていた問題が入るようになっているので、これを使うのが確実です。

問題ページの最下部に提出ボタンがあります

次にジャッジ結果の表示ですが、AtCoderと1つだけ違うところがあります。

  • AC:正解

  • CE:コンパイルエラー

  • RE:ランタイムエラー

  • TLE:実行制限時間超過

  • MLE:メモリ制限超過

  • OLE:出力制限超過

  • WA:不正解

  • PE:Presentation Error(出力形式違反による不正解)

"PE"はAtCoderだと"WA"にまとめられていますが、AOJでは区別されて表示されます。具体的には、出力されている値は正しいけれど、問題文で指定されていない余計な空白や、改行などがあって、ジャッジの基準に適合しなかったときにこの結果になります。
ということで、"PE"は知らないと混乱する原因になりますが、意味を理解していれば、出力部分の誤りに絞って確認すればよいことがわかります。

なお、重要な時間制限とメモリ制限は、問題ページの上のほうに非常に小さい文字で書いてあります(問題一覧ページのほうが確認しやすいかもしれません)。しっかり確認しましょう。メモリ制限がKB単位で書いてあるので、単位の変換を頭の中でできるとなおよいです。
例えば今回の262144KBは256MBです。AtCoderの最近の問題は1024MBが常なので、やや厳しめです(実際、メモリを意識する必要のある問題もあったとか)。

また、AtCoderでは提出が全体としてAC以外だったときに、何個のテストケースが"WA"や"TLE"などになっているのかを確認することができます。しかし、AOJではこれができません。例えば22個のケースがあって、5個目で"WA"になったら、6個目以降のケースについては実行されないので、結果がわからないのです。
ACが取れない問題に対して、AtCoderでは複数の提出結果を見比べてヒントを得る手法が使えますが、AOJではやりにくいです。

5個目のケースで"WA"になった表示の例

最後にコードテストについてですが、AOJでは用意されていないようなので、手元で環境構築をするか、AtCoderのコードテストなどを開いておくと良いでしょう。

チーム戦の立ち回りについて

今回、オンサイト会場ではAtCoderのレート順にチーム分けがされました。Kirishimaは水色なりたてだったので、下から3番目くらいでした。要するに、行ってみたら青色以上の人ばかりの魔境だったというわけです。諸々の調整が入って、下から4人(本来は3人まで)でチームを組むことになりました。チーム"KNMM"です。AtCoderのHighestの平均で言うと1000くらいだと思います。
2022年3月にあったTUPC2022でも2完しかできなかったので、今回も相当厳しい戦いになることを覚悟していましたが、案の定、ほとんど歯が立たない問題ばかりでした。
一応、「AからCの3問は比較的簡単」と告知されていましたが、実際にはAがかなり難しめ(法則に気づけば簡単だが、気づくまでが難しいタイプ)の問題でした。

チームでは最初、とりあえずABC3完に集中するという方針でした。C問題がセグメント木ですぐに殴れたので、0完は回避です。その後は比較的解けそうなBを2人で進めながら、残り2人でAなどほかの問題を見ていく立ち回りでしたが、Aの法則性を見つけられずに時間を取られました。
途中からはKやIのほうが多く解かれていたのでそちらも見ていましたが、結果的にこれらは無理でした。
ゲーム問題であるKは、「初手の選び方がすべて」という点までは到達しましたが、その選び方の基準を見出せませんでした。
木の問題であるIは、すべての頂点について答えを求めるというところから、全方位木DPに落とし込めないかを検討しましたが、模範解答は全く異なるもの(愚直と行列累乗の使い分け)でした。
最終的に惜しいところまで行ったのはF問題です。オイラーのトーシェント関数(自分以下の正整数のうち、自分と互いに素なものの個数を返す関数)に関する問題で、適切な前処理をすると木の2頂点間の最短距離クエリの問題に帰着されるというものでした。
最後の1時間で、KirishimaがこのF問題をやってみることになり、とりあえずグラフにしたりUnion-Findで連結性を調べたりするなどして、どうにか木の問題に帰着させるところまでは行きました。しかし、最後のステップで使うLCAの使い方を間違えて、WAとなったところで時間切れとなりました(間もなく修正し、ACに至りました)。

とにかく問題数が13問と多いですが、そのどれもがかなりの難易度でした(AtCoderだと体感でBCは緑色くらい、他は水色~赤色以上と思われるものまで幅広くありました)。その中からどうにか食らいつけそうな問題を探すのが主な作業でした。
しかしながら、最終的にBCの2完はできていたので、チームとしては良い結果になったのではないかと思います。ナイスファイトでした。むしろ問題セットにいくらか慈悲があって助かりました。オンサイトで0完になってしまったらあまりにも悲しいので……。

ここからは反省会です。問題に対してチーム全員の実力が足りないという前提で、どのような立ち回りの工夫ができるかを少し考えてみます。
全員の実力がそこそこ足りている場合や、1人だけ強い場合などは、また違う最適化の方法があると思います。

  • 各問題、全員で簡単にでも目を通したほうが良い

  • 自分にできると思ったことは、とりあえずやってみる

  • 解けない問題が多くても焦らない、特に誤読には気を付ける

作問側が認識する難易度と、初見で問題を解く参加者側にとっての難易度に差が出ることは往々にしてあるので、とりあえずすべての問題を見て、概要を把握しておく(誰も問題を理解できないなら、「理解できない」という情報を得ておく)くらいはしても良いと思います。
もしかするとチームの誰かが「これはできる」となってくれるかもしれませんが、こういったチャンスも問題を開かなければ生まれません。
「できる」とまでは行かなくても、何か気づいたこと、思ったことなどがあれば、積極的に共有することも大事です。問題を解くための考察には一般に複数のステップがあるので、その1つや2つでも埋めることができれば、チームメイトの助けになる可能性があります。ブレーンストーミングくらいの感覚で、とにかく何かキーワードを出してみるでも良いでしょう。
一方で、問題の内容や制約の把握は丁寧にやるのが良いでしょう。誰かが誤読をして、それに基づく誤った認識がチームに共有されてしまうと、軌道修正に大きなコストが掛かります。複数人で問題に目を通すことで、そうしたリスクを軽減することに繋がります。
考察を誤るのは実力上仕方のない部分なので、それは良いですが、単純な凡ミスはなるべく減らしたいものです。

ちなみに、タイムキーパーは居ても良いですが、明示的にリーダーを決める必要はないと思います。極端に実力の差があるのでなければ、あくまで対等にやるほうが、お互いの満足感につながると思います。

一番大事なのは、最後まで諦めずに頑張ることです。そのためには、チーム内で励ましあい、士気を維持する必要があります。
実力が足りていないので、厳しい場面が当然多くあります。考察が振出しに戻ったり、バグが取れなかったり、思わぬミスをすることもあるでしょう。しかし、結局は「お祭り」ですので、楽しんだもの勝ちです。どのみち、目の前の問題を解くことしか、考えるべきことはないのです。早く解くとか、ペナを出さないとか、順位を上げることを考えるのは実力を十分につけてからでも遅くはありません。そのくらいの心構えでゆるくやるのが良いと思います。

余談

最後に個人的な感想をいくつか書いて終わりにします。
全体としては楽しかったと思いますが、3日連続で参加できたとしても、3日すべて参加するのはいろいろ厳しいものがあると思いました。
まずは体力です。まあ疲れます。参加した翌日は筋肉痛になりました。どちらかと言うと、PCを持っていくのが大変です。しかもメインPCを持ち運んでいるので、いくらかリスクもあるわけです。比較的軽いサブPCを用意したくなりました。
自宅では外付けモニタもあって、各種参考書も揃っているので、本当に個人として高いパフォーマンスを出そうと考えるなら、自宅から参加するのが一番です。それでもやっぱり、チーム戦でしか得られない楽しさがあるので、機会があればまた参加したいと思います。
ただそのときには、もう少し強くなっていたいです。チームの中で、自分がレートの高い立場になるか低い立場になるかはわかりませんが、どちらにしても、個人として多くの問題を解く実力があるに越したことはありません。チーム全体としての立ち回りの幅を広げることができるからです。
あと、コンテスト後の懇親会も、次は参加してみたいと思います。強い人の話を聞いてみたいです。話の内容は理解できなくても、キーワードを覚えておくだけで、そのうち勉強の取っ掛かりになる可能性があるからです。
そう言えば、note(ここ)やTwitterでは「霧しゃま」表記ですが、AtCoderなど中の人として出るときは「Kirishima」表記をしています。同一人物です。念のため。

おわりに

運営のみなさま、当日チームでご一緒したみなさま、本当にありがとうございました。
機会があればまたお会いしましょう!
以上、霧しゃまでした!

この記事が気に入ったらサポートをしてみませんか?