いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

ICPC模擬国内予選2017参加記

2017/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group

本番に出るチームで参加しました
結果は4完でした
チーム名はsparsely_populated_regions(限界集落)(575)
チームメンバーの開始直前のツイートです



時系列で書いた方が面白いかもしれないのでそのように
内容は忘備録程度なのでいつも通り雑に書きます

二人がライブラリを印刷していたが、自分はまだ全域木とかしか無いしそのような実装は時間がかかりすぎて任せるしかないので、基本的だけど書き方に自信がない物だけ用意しようと思った
印刷場所が遠いので手書きにした


事前に私がA,ゆらふな氏がB,やざてん氏がCと決めていたのでまずA問題を読んだ
みんな読み終わった段階で私だけ理解できてなかったのでもう一回読んだらすぐ解法が浮かんだ

A:問題がn個与えられる、それぞれの難易度が1~mで与えられる
各難易度から1問ずつ出題し、合計でm問出題する
しかし各問題には推薦度が決められておりそれが最大になるようにする
配列でmaxを持っておしまい
だったけど添え字をミスったのでサンプルが通らなかった
二人が声をかけてくれてゆらふな氏が指摘してくれてAC

ゆらふな氏が読んでたBのヘルプに入る
問題文の解釈がややこしくて二人で相談しているうちにやざてん氏がCを通してくれていた
後で問題の概要を聞いたけどどうも混乱しそうだった

やざてん氏の手が空いたのでゆらふな氏にDを頼んでBをやざてん氏に読んでもらった
先に問題の概要を説明しようとしたが、問題を理解してないのに説明しても意味がないと後で思ったしその時本人が止めてくれた
この隙にBのサンプルを図示しようとした
読んでもらったらすぐ実装できそうとのことで実装を頼んで、図示が終わり次第Dを読み始めた

Dもまた問題文がややこしいけどなんとなくわかったなぁと思っていたらゆらふな氏がサンプルの動作を実際に説明してくれたのでわかりやすかった
なんとなく二分探索しそうだなぁと思ってたらゆらふな氏が同じことを言っていた
クリアできないケースについては整理でき説明できたのでよかった
しかし本当に二分探索でいいと言い切れず、二人がDPを使ってはどうかと言い始めたあたりで話について行くのがやっとだったので離れて別の問題を読むことにした

Eを開いたら数学っぽくて今まで解いたことのないジャンルだと感じたので読まずに飛ばした

Fはマトリョーシカ風に立方体を入れ子にしてなるべく一番外の立方体の体積の合計を小さくする問題だった
条件は直感的でわかりやすいし伝えやすい、後は何か具体的なアルゴリズムを知っていれば解ける系なんじゃないかと感じたのでやざてん氏に相談したら解けそうとの事で考察を任せ、サンプルを図示し始めた
二人とも多分Dから離れゆらふな氏はEの考察をしていたと思う
この図示が難しくて妙に時間がかかったがミスするよりはいいと思った

図示の合間にやざてん氏がFで使うらしいライブラリの写経を少し手伝った
キーボードがHHKBかmacbookのJISを用意していたがHHKBの十字キーがわからずmacbookを使って書いていた
緊張してミスタイプが多かったので確認してすごく遅い写経になってしまった

やざてん氏の考察が終わったので写経を代わってもらって終わり次第実装に入ってもらった
私は図示の続きと確認をして納得がいったので後半の問題で優しそうなのがないか探していた
f:id:ratetion:20170702232910j:plain

やざてん氏がバグを吐いていたのでヘルプに入った
バグが起こってそうな部分を雰囲気だけで伝えてみたが、どんな実装なのかあんまりわからなかったので下手なことをいうより考えてもらった方がいいと思ったので端的に伝えて答え合わせとかの準備をしていた
答え合わせが多少スムーズになったので悪くはなかったと思った
時間かけてバグを取ってAC、ここで4完、残り30分弱だったと思う

ゆらふな氏がEが解けるとの事で使うライブラリの写経を投げてきたのでどこを写すか整理してやざてん氏に投げていた
写経速くてやべえと思った、やべえ
写経が終わったらゆらふな氏が実装に入ってくれたので写経部分のミスをひたすら探すお仕事をした
2個ほど見つけられたのでまあやることがあってよかったなぁと思った
実装間に合わずタイムアップ
ABCFの4完でした

自分はほとんどキーボードに触れず考察と図示サポートをしていたので、問題や解法をうまく伝える能力がもっと必要だなと感じた
また添え字ミスとか露骨なミスを減らさないといけないなぁと思った

3日連続でSRM,ARC,模擬国内と出たので充実した3日間だった
おわり