ACM-ICPC2018 アジア地区横浜大会 参加記
この記事はUEC Advent Calendar 2018の11日目の記事です。
このタイミングでどうしても書きたかったところをアドベントカレンダー作成者である id:puman03 さんに色々手配していただきました。深謝いたします。
宣伝
いきなり宣伝かよって感じですね。主に学部1~2年生あたりを対象にした内容なので、ぜひ読んでみてください。
情報工学工房
カレンダー経由でこの記事を読む各位の多くは電通大生だと思いますが、電通大に「情報工学工房」という授業があるのをご存知ですか?
この科目は誰でも履修することができる通年2単位の科目で、1類の人には専門科目(選択)、それ以外の人には共通単位として扱われます。
プログラミング等の活動をしてみたいけどキッカケが欲しい人、大学や教員のサポートを受けながら制作活動がしてみたい人、たまたまやりたかったテーマがあって単位がついでに欲しい人とかには向いてると思います。逆に、特にやりたいことが明確でない人や1年間続けられる気がしない人にはあまり向いていないかもしれません。
毎年テーマが変わるので、少しでも興味がある人は4月にあるガイダンスに出席してみてはどうでしょうか。
ICPC2018 アジア地区横浜大会 参加記
ここからは、2018年12月8~10日に行われた ACM-ICPC2018 アジア地区横浜大会 の参加記となります。何も考えずにだらだら書いた雑な感想文なのですごく読みづらいです。ご了承ください。
国内予選の参加記はこちら。
メンバー
前日まで
チーム練習とかをやっておくべきだとは思ったが、結局1回もできなかった。
1日目: リハーサルとチーム紹介
昼前に大学で合流して会場に向かった。横浜は遠かった。
会場に着いてからは、コンテストの注意点等の説明を聞き、その後リハーサルを行った。
A問題とB問題は何事もなく解くことができたがC問題とD問題は解くことができなかった。
チーム紹介では、ばぐ君がこの日に電通大が100周年を迎えたことを英語で喋ってくれた。
2日目: コンテスト当日
朝5時半に起きて7時に駅で合流し、会場に向かった。とにかく眠かった。
9時半からコンテストが始まった。
ばぐ君にコーディングの準備をしてもらいつつA問題を見てもらうことにし、その間に私がB問題、はと君がC問題を読むことにした。
ばぐ君にAの実装を任せたが、本人が問題の内容や言語の挙動を勘違いしていた。正しく解ける方針を伝えたところ、苦戦しながらもなんとかAC。ここまでで33分。
B問題に取り掛かろうとしたが、すぐ思いつく単純な実装を試してもらったところ制限時間を超えてしまったため、後回しにした。
C問題は単純なシミュレーションをすれば自明に解けるが、こちらも制限時間を超えそうだった。少しした後にはと氏がいい感じの解法を思いついてくれたので、それを私が単純な計算式に置き換え、ばぐ氏に伝えて実装してもらった。1時間4分の時点でAC。
ここでB問題に戻ることにした。ばぐ氏が適当な枝刈りを提案したので、試しに実装してもらったところACした。ここまでで1時間51分。
ばぐ氏にD問題を、はと氏にG問題*4をお願いし、私はE問題を読むことにした。
まずG問題について、転倒数が関わってそうという考察が出たので、適当な方針を伝えて実装してもらったが、サンプル入力に対して正しい出力をせず、方針が正しくないことが判明した。
次にD問題に着手しようとした。ばぐ君がグラフを用いたアイデアを思いついたので、私が構造を定義して実装したが、サンプル入力が通らなかった。適当なアルゴリズムを考えたので、それに起因するものだと推測してバグ探しを始めたが、アルゴリズムではなく最初のアイデアが本質的に正しくなかったことに最後の最後まで気づかず、無駄に時間を使ってしまった。
途中でH問題を見たはと君が内容のシンプルさに気づき、試しに触ってみることになった。適当な全順序を見つければ4彩色できるのでは?と思い雑な実装を試そうとしてみる。ばぐ君にコーディングを丸投げし、適当な出力を吐くプログラムを投げてみたら当然のようにWA。次にグラフの形状の制約を利用した実装を試してみたがこれもWA。そりゃそうだ。
そうこうしてるうちに14時半になり、コンテストが終わってしまった。
結果
3問解いて60チーム中39位でした。最低限の目標としていた3問はなんとか解くことができた。
しかし、G問題を難しく考えすぎたせいで解けなかった点は悔しかった。
3日目: 企業見学
3社ほど企業見学させていただいた。まだ就活を始めていない私もそろそろなんとかしないといけないなあと感じた。