ICPC国内予選参加記

この記事はTCU-CTRL場外乱闘 Advent Calendar 2020のために書きました。

 

ICPC国内予選に参加しました。その時の様子を書きます。今年の国内予選はマキアさん(茶色)、あめふりてる君(緑色)、自分(緑色)で参加しました。

開始まで

今年は流行りのあれによって集まることが難しくなったので、ルールが大幅に変更されました。

・ライブラリのコピペが可能

・使用できる計算機は1人1台まで

・ネットワークへのアクセスはできないが、SNSでチームメンバーと連絡をとるためならOK

つまり、3人がそれぞれ別の問題のコードを書くことが可能になりました。というわけで、マキアさんがA問題、あめふり君がB問題、自分がC問題を担当することになりました。

通話はDiscordを使いました。画面共有はDiscordに付いているものではなく、あめふり君が作った画面キャプチャソフトを使いました。こうすると自分の画面全体を見せながら、他の人の画面を見ることができるようになります。

github.com

題意や解法の共有にはHackMDを使いました。

開始後

本番のシステムにログインしようとしたら、1行だけエラーメッセージらしきものが書かれた画面が出てきました。2,3回試しても変わりません。3人とも同じ状況で何もできないので、マキアさんが審判に電話をかけてくれました。残念ながら、他のチームの人も電話をかけていたのか、繋がることはありませんでした。普段のコンテストなら、Twitterでつぶやいたり他の人のツイートを見ることができるのですが、今回はそれができなかったので少し不安でした。

しばらくリロードを繰り返していたら、16時40分ごろ(本来の開始時刻から10分後)に突然見られるようになりました。A問題は2020を見つけ出す問題、B問題は皆さんがスマートフォンにインストールしたかもしれない、とあるアプリに関する問題でした。

自分が担当するC問題を見たら、約数列挙と同じような方法で解けそうでした。すぐに実装を始めました。

ところが、バグがあって無限ループしているような状態になったり、8を入力すると7(正解は6)が出てきたりしてました。しばらく悩んでいたらあめふり君がB問題を通したので、コードを送って解いてもらいました。

 

あめふり君が解いている間、D問題以降を見ていました。

・D 実装が重そう。全探索しか思いつかない。

・E どこが条件を満たすのか分からない。サンプルすら手作業でも解けない。

・F グラフを書けばどういうことかはわかりそう。

マキアさんとしばらく考えていて、あめふり君から通ったという連絡が来ないので聞いてみたら、一つの入力につき5秒くらいかかっているとのことでした。n<=10^15なのにO(√n)以上の計算量*1アルゴリズムなので仕方ないですね。実行時間の制限がないという国内予選のメリットを活かすことになるとは思いませんでした。

 

最後はFを主に考えていました。あめふり君が色々とグラフを書いてくれたので、それを基に試行錯誤していました。仮説を出してその反例を見つけることをしていたら、時間がきて終わりました。

終了後

f:id:polyester-kpr:20201202230458p:plain

順位表

結果は112位でした。Cにかかる時間が短ければ予選突破だったらしいので、少し悔しかったです。並列処理するようにしたり、(今年限定ですが)3人が各自のパソコンで分担して実行して*2、時間を短縮することもできたはずなのでもったいないです。終わってから言っても仕方ないので、精進して来年頑張ります。

余談
  • 6時過ぎぐらいに突然自分のPCの電源が切れました。原因はよく分かりません。流石学科PCだなと思いました。
  • 回線速度が落ちたのか、途中から他の人の画面を見ているとDiscordにつながらなくなってきました。何か見たいものがあるときは、Slackにスクリーンショットを貼り付けてもらうことで対処しました。
  • 今年限定ですが、B問題はUnion-Findを貼り付けたほうが実装が速かったかもしれません。

 

最後まで読んでいただきありがとうございました。明後日は、ぱらなさんがボイロか動画か就活の話あたりを書いてくださるようです。

*1:厳密には分かりません

*2:競技ルールには記載されてないようですが、もしかしたらだめかもしれません