こんばんは。nari(rickytheta)です。
ICPC2017国内予選にninjaribatonで参加しました。結果は12位(学内1位)でした。予選通過やりました。
関連記事
同じ東工大から出た先輩の2チームが先に参加記を上げています。東工大の状況についてはこちらが詳しいです。
kurukuru-sushi : ACM-ICPC 2017国内予選 参加記 - うにゅーん、って感じだ
IQ 1 : ICPC2017 国内予選 - ちゃっくのメモ帳
なんか散々な扱いですね……
よすぽ先輩(WF1回経験)が来年まで力を溜めるということで今年は参加していません。平和だ……
戦歴
2015 : Arrows16で参加、4完25位(学内3位)、予選落ち(nariがC++を書き慣れていなかったため1問解き損ねた)
2016 : FCCPO.js.hs.dで参加、5完19位(学内3位)、予選落ち(全員でEを誤読する珍事件が発生)
ということで、予選落ちを2回経験して、今回初通過になります。通過嬉しい……
おふとんから出ました pic.twitter.com/7k04MKE9XZ
— なり (@_n_ari) 2017年7月14日
一昨年・去年ともにドワンゴ賞を受賞しているため、ニコニコテレビちゃんがスタックされています。
チーム
ninja : 16のB2のtraP。忍者
nari(rickytheta) : 15のB3のtraP。戦犯歴が多い
baton : 17のB1のtraP。神
というtraPから15/16/17を1人ずつ引っ張ってきたチームになります。
チーム名のninjaribatonですが、ninja / ri / batonという区切りになっています。僕はriを担当しています。
予選前
ティッピーがいました。かわいい。
kurukuru-tippy pic.twitter.com/7gqWIcsQci
— りあん (@rian_tkb) 2017年7月14日
あと予選前の確認事項・点呼の時でチームIQ 1が呼ばれた時にchakkuさんがちょうどいいタイミングで入室したのが面白かったです。
予選の様子
時系列で並べます。
基本的には、AとBをninja、CとDをbatonに任せ、A→C→B→Dの順番で解いている間に、nariがEFGHを読んで考察する、という戦略を取っています。
11:26 A問題をAC(ninja)。
20:33 C問題をAC(baton)。
33:23 B問題をAC(ninja)。
53:04 D問題をAC(baton)。
ここから、EFGHを並列して攻略していきます。
E問題はたかだか15文字の文を全探索すればよさそうで、どう全探索するかがポイントになりそうだと思っていました。ここでDPかな？と思ってしまったのが多分失敗です……
F問題はなんかすごい複雑なことをしているけどbitごとに見ていくと性質がありそう？と思っていて、詰めれば解けなくはなさそうかな〜〜〜？と思っていました。があまり真面目に考えられなかったのでbatonに投げました。
G問題はグリッドマップです。batonに「nariが得意そう」と投げられたのですが、見た感じだと左端についてはできるだけ左側を歩くようにすればいいのでは？という気分になり、実際そうだと思っていました。
H問題は、かなり探索範囲が少なさそうなので、幾何さえなんとかなれば全探索で余裕そうです。
とりあえず、nariがE問題を実装してみます。残念ながらここから終盤まで方針をDPに絞ってしまって無駄に実装量が増えたり無駄に計算量が増えたりしてしまって、サンプルですらWAとTLEを大量に出します。
一方のFですが、batonにお願いしたところ結構細かいところをミスりやすい方針らしく、こちらもかなりバグを出していました。
このあたりでEとFを交互に実装・デバッグする、みたいなことをしていました。Gですが、ninjaと話したところ壁から1マスのところを歩くようにすればいいという話を聞きました。なるほど。
これを聞いたにも関わらず、座標的に左に行くほうが優先のdijkstraを書いてしまい1WAを出します。なんでや。
Fもバグっているらしい。うーんつらい。この時点で残り1時間ぐらいでマジで焦っていました。
Gに戻って、壁に沿って歩くプログラムに修正。方針としては、左端の壁からDFSして、壁に隣接した8マスの通れるマスを「壁沿いのマス」として、ここを通るようにして左上から左下に行って、「壁沿いのマス」を壁にして、90°回転、を繰り返す感じ。壁のDFSを8方向ではなく4方向にしていたため1WAを出し、2:39:25にG問題AC(nari)。
一方のFもバグが詰め終わり、提出。1WA。
なんかn=1の時に処理がまずいらしいので、これを直して、もう一度提出。
……が、ブラウザバックをしたためか、1WA追加した上に「2連続同じソースコードで提出しないと正解にならないよ」と言われる始末。どういうことなの……
ちなみにテストケースは2に進んでいたため、1は正解していたらしい。どういうことなの…………
まぁあってそうなので、2と3を提出して、2:52:03にF問題AC(baton)。
ラスト、E問題ですが、全探索の方針をようやくDPから変え、単項が高々4つしか出ないことを利用した全探索を急いで書きます。が、実装ミスが連発して時間切れ。悲しい……
予選後
何はともあれ予選通過です！やったぜ。
東工大チームでEを通したチームはいませんでした。やっぱり難しい……
余談ですが、実はこの日はコンパイラ構成という講義の課題の締切で、ICPC直前までLL(1)と戯れていました。なのでパースは余裕だったんですけどね……
予選が終わって数分でとりあえずサンプルが通るプログラムはできました。惜しかった……
東工大からは他にもkurukuru-sushiとIQ 1が予選通過のようです。新選抜ルール、優しい
企業賞は調べた感じだとTeamMeiがドワンゴ賞、IQ 1がグーグル賞を取っていそうです。
終わった後は大学近くの味庵で打ち上げをしました。味庵にはICPC後にしか行かないので味庵といえばICPCという謎の関連が頭のなかにあります。
美味しかったです。最後スープとサラダをサービスされた気がして、とても良い打ち上げでした。
ところでちょくだいさんが順位表眺める放送をニコ生でやってたらしいので、タイムシフトでも見ようかな、と思っていたら、
ちょくだいさんの生放送見ようと思ったのに！！！！！！！！(悲しい)(寝ます) pic.twitter.com/EoR4akvjbo
— なり (@_n_ari) 2017年7月14日
タイムシフト対応してませんでした。誰か録画してないかな……
感想
アジア地区予選は12月なので、それまで頑張って練習したいですね……
今回はbatonとnariが独立してFとGを思考してしまったのですが、それがどちらも泥沼に落ちてしまった最悪のパターンだったので、そこをどうにかできればもうちょいACが増やせそうです。
何はともあれ、初通過なので素直に嬉しいです。もっと順位を上げてWF圏内目指せるように精進します。
ところでrianさんの講習会が一段落したので、何か新しい講習会シリーズをしようかなと考えています。今後ともよろしくお願いします。
