もふふろぐ

ACM-ICPC 2018 Asia Yokohama Regional 参加記

12月8日から3日間開催されたACM-ICPC 2018 Asia Yokohama Regionalに参加しました。

チームMohuhu Universityとして予選を通過したため今回の地区大会に出場することができました。 チームは私とShinya Kato、tomaからなります。 結果はA, B, C, Gの4完で26位になりました。

前日

ICPCに必須な学生証やコードスニペット集、もふふ(サメのぬいぐるみ)などを鞄に入れ就寝します。 会場が東京近郊であったこと、宿泊先の備品が充実していたことから、荷物はとても軽くなりました。 ラップトップも持ち歩いていたものの、一度も使用しませんでした。

1日目

起床

早起きです。 横浜駅で途中下車し、ポケモンセンターヨコハマに立ち寄りました。 土曜日だったので大混雑。

駅の地下にある麻婆豆腐店で麻辣麻婆豆腐麺(850円 税込)を食べました。

会場の入り口で同じぬいぐるみを持つTIkeさんに遭遇したので写真を撮りました。

プラクティス

会場の横浜産貿ホールに入りプラクティスコンテストに参加しました。 本番で使用する環境とチームの戦略を再確認しました。 今年の環境にはCLionが導入されており、デフォルトで便利な補完機能を利用できることから、チームで使用するエディタをこれに統一しました。

チームごとに30秒の自己紹介が行われた後、解散となりました。

夕食

夜にTIkeさん主催の宴に参加する予定ですが、早めに解放されたため、先に関内駅前まで歩きホテルにチェックインしました。 2人部屋にしては狭く、去年のつくばとの地価の差を感じました。

宴は中華街の食べ放題店(2,480円 税抜)で開かれました。 餃子がとてもおいしかったです。

21時頃に部屋に戻ると真っ暗で、シンヤカトーが熟睡していました。

他のチームの様子

2日目

朝食にコンビニのパンを食べました。

コンテスト

5時間(9:30 - 14:30)で11問を解くコンテストです。

開始直後まず私が環境構築を行いました。 その間、シンヤカトーはA問題を、tomaはB問題を読みます。 環境構築として行ったのは主に次の4つです。

  • CapsLockキーをCtrlキーに設定する。
  • オプション付きのg++のaliasを~/.bashrcに記述する。
  • サンプル入出力ファイルをwgetする。
  • CLionの初回設定を終えプロジェクトを作成する。
# CapsLockキーをCtrlキーに変える。
dconf write /org/gnome/desktop/input-sources/xkb-options "['ctrl:nocaps']"

# CapsLockキーをもとに戻す。
dconf reset /org/gnome/desktop/input-sources/xkb-options
# ジャッジサーバのコマンドに準じたオプションを追加する。
alias g++='g++ -std=c++11 -Wall -Wextra -Wshadow -g'
alias a='./a.out'

A Digits Are Not Just Characters

0:18 (+0)

file10file3のような文字列が与えられるので、数字が連続している部分を1文字と解釈した上で、文字列の大小を比較する問題。 シンヤカトーがAC。

C Emergency Evacuation

0:36 (+1)

バスの乗客全員が非常口から降車するまでのステップ数を求める問題。 環境構築を終えてから読んだところ、tomaが読むB問題より簡単そうだったため先にコーディングしました。 大きな入力を配列から溢れさせて1WA。 すぐに修正して提出しました。

B Arithmetic Progressions

2:11 (+3)

入力された集合に含まれる整数で構成できる最長の等差数列の長さを考える問題。 問題を読んだtomaがそのまま実装するもWAやTLEが出たため、シンヤカトーと交代しました。 しかしそれでもTLE。 N = 5000の制約に対してO(N^2 logN)の解法を考えて安心していたのですが、想定解法はO(N^2)だったそうです。 幸いB問題かC問題が難しいことは想定内だったので、慌てることなく考えられました。

G What Goes Up Must Come Down

2:37 (+0)

数列を山形(最大の要素から前は昇順、後は降順)に並び替えるためのスワップ数(隣り合う要素を交換する回数)を求める問題。 B問題から離れたtomaが問題を読んで考察していたものを、シンヤカトーが完璧に詰めて実装してくれました。

他の問題

4完した後はシンヤカトーとtomaがそれぞれD, K問題の沼にはまり、新たなACを生むことができませんでした。 その間私は、2人の考察を聞いたりペアプログラミングしたりしながら、残りの問題を読んでいました。 この後半の自分の行動には反省点が多く、例えば全員でどちらか1問に集中したり、2人に他の問題を一通り伝えたりすればよかったと後悔しています。

まだ復習を終えていませんが、良い問題が揃っていたと思いました。

懇親会

おいしいご飯が出ました。

会場にはスポンサー企業のブースが並びます。 ドワンゴのブースではハイパーロボット(ボードゲーム)をプレイでき、チップを獲得するかわりにニコニコテレビちゃんのぬいぐるみをいただくことができました。

懇親会中にチームマスコットの交流が行われていましたが、弊チームのもふふは荷物ごと預けられてしまっていたため撮影できませんでした。 かなしい。

3日目

東京に戻り、企業見学に参加しました。

Indeed Japan

IndeedのTokyoオフィスを見学しました。 事業内容への興味が小さかったため、あまり意識したことのない企業でしたが、おしゃれな空間がありながら奇抜でなく丁度よいオフィスに憧れを抱きました。

昼には今半のすき焼き弁当をいただきました。

bitFlyer

企業見学の予定にはbitFlyerが含まれていましたが、金融関連のデータを扱っているという都合で、オフィス内を見学することができませんでした。

MUJIN

ロボットアームを扱う企業なので工場のような場所を想像していましたが、モダンで綺麗なオフィスでした。 質疑に答えてくださった社員さんはロボットを弄るのが大好きだそうなので、そうでない私がここで働くことは無理だろうと感じました。

まとめ

1日目の入場前にはポケモンセンターヨコハマへ、3日目のMUJIN見学後にはポケモンセンタースカイツリータウンへ行きました。 長い間売り切れが続いていたポケモンカードゲーム強化拡張パック「迅雷スパーク」が大量に入荷していたため、鑑賞用に数パック購入しました。 ポケモンカードゲームを始めてみたいと感じるものの、TCGのハードルは高いのです。

ICPCを通して競技プログラミングの意欲を得たものの、今後は研究に専念しなければなりません。 人生はつらいものです。