ICPCにっき 2018国内予選
久々の更新
1週間経って、正式順位も出たし、書こうかなと
自分はチームWArabimochiで出場して12位(通過順位11位)でアジア地区予選へ出場が決まりました。
チームWArabimochi
* ねこさん:つよいひと
* はとさん:超絶優秀な人
* ばぐ:自分(バグ埋め担当)
JAG
問題はこちら
はとさんが用事の為ねこさんと二人で参加
A
if文で2通りなのは自明だったけどソースコードで入力を受け取るとこまで書いてもにょりかける
大丈夫か自分とか自問自答しながらねこさんと話してるうちにif文が完成してAC
B
なんだこいつと一瞬空目したけど入力の形見たらそういうことねと理解して書く
問題の条件通りに書いたところif文が汚くなったが、あとから別チームの人に入力列Aの最後に1を追加すると条件1,2がまとめられると聞いてひっくり返る
C
パーサー書きたくないなぁ…と思っていたらねこさんが書くということで交代
D、E、Fにざっと目を通すがE、Fの内容を覚えきれなかった
というかDのsample outputを見て頭がこんがらがってるうちにねこさんAC
D
多倍長が必要かなぁと思ってうんざりしていたら、ねこさんから上の桁から順に確定できそうと聞いて思考がすっきりしてくる
この辺のきっかけを得るにはどうしたらいいのだろう
最初の1桁の確定は比較的簡単だったが2桁目の確定で少し間違う
が、さほどかからないうちに条件分岐を整理してたらとりあえず桁が確定できた
ここでねこさんが2つの数字が確定すると残りがbit列に対応していることに気づく
はいプロとか思いながら実装してab...(a,b:0~9,a!=b & a!=0)のケースは全て終わる
残りはaa...のケースになったところで1個桁を減らして再帰したいと意見が一致するも、かなり実装が長くなっていて、うんざりしかける
が、桁確定のif文の前に変数の値を書き換えてgotoすればいいのでは?と気づきこれでどうでしょと書く
ねこさん「ほんまか?」ばぐ「いけると思うんですよ」
というわけでコンパイルを通してみると大体合ってそうになる
最初の一桁が抜けていたのでもにょりかけるもねこさんの指摘通りgotoをずらすとサンプル全部通ってしまう
二人「ほんまかあ?」と言いながらテストケースを通すとサクッと出力が終わっていよいよ面白い顔になりながらSubmit→AC
二人で2~3分ばかし大爆笑する
クソコードを日々生産している自分のクソコード芸が変なところで役に立った模様
E
最初見たとき???という気持ちだったんだが二部グラフと言われてあっ…となり実装を書く
スタイリッシュに(ただ書きなれているだけ)グラフとDFS実装し貪欲彩色を完成させて最後もにょりかけて出力のとこで交代
10分余りで実装が終わり、何事もなくAC
二人でE先にやればよかった…と少し反省する
その後
Fが全く見えなかったのでGを見る
すぐにO(M)解が見えて実装したがサンプルの出力が終わらない
もう一度入力制約を見ると
O(M)無理じゃんってなって残り10分だったので撤退
結果が20位(ゲスト除き15位)だったので希望半分ほんまか?半分という気持ちになる
前夜
大学で卒研のことでひとしきり悩んでからバイトへ
バイト先に搬入されていた自販機でレッドブルを購入し自宅の冷蔵庫にストック
西友でわらび餅とBLACKBLACKを購入
cpprefjpからコンテナのメンバ関数を忘れないようにと印刷して就寝
当日本番前
朝
丸々8時間寝て8:00起床 素晴らしい目覚め+風呂で軽く寝汗を流す
朝ごはんを食べてから、持ち物を確認し11:30大学へ出発
すぐにラボの冷蔵庫にわらび餅とレッドブルとBLACKBLACKを冷やしてからトレーニングルームで体を起こす
昼飯にカツサンドを購入し食して、リハーサルを1問通してラボへ戻る
昼~開催前
ひとしきりやることが終わって14:30に会場の計算機室へ
なんかリハーサルがリセットされたと聞いて3問通してみようとする
1行読み込みを長いこと触っていなかったのでgetline(cin,str)
を完全に忘れていて焦りに焦る
とりあえずstringstreamのparseと併せてサンプルコードを印刷しておく(完全に焦っている)
ギリギリで3問通したところで4問目が2015のD問題だなぁとか眺めてたらリハーサル時間が終了
国内予選中
今回は学内から6チーム参加ということで計算機室のプリンター割り当てを決める
うちは2部印刷するプリンターを引くことになった
とりあえずブラウザと時計をにらめっこして試合開始
A
すぐにmkdir a b c d e f g h
みたいなのしてブラウザに目を向けるとすぐに2人から平均値以下という声と入力が整数という声が聞こえてすぐにemacsで入力開始
ガリガリ入力を書いてるうちにただ足してあとから割るだけと気づいてそのまま書き進めてコンパイル通してすぐにサンプルを通すと合ったのでそのままsubmitしたらAC 気づいたらFAが取れていたので順位表を見てきょどる
B~C
Bの入力を受け取ったところで冷える
とりあえず読んでいる2人に代わってもらうことにしてねこさんに交代
入力を受け取るところまで書いていることを伝えてCを読む
すぐにCは最悪O(b)で通そうという結論になりながらどうするか考える
はとさんが尺取りを考えたがやっぱりO(b)で辛そうとなる
自分は左端を決めると条件を満たす部分列の有無がO(1)であることが分かったが左端の分布が離散的なので二分探索できないとわかり悲しくなる
そうこうしているうちにねこさんがBをAC
Cもねこさんが前後の解法をはやしていたのでコードを説明聞きながら書いてたら出来上がってAC
D~F
もにょってしまい入力受け取りコード生成機になってねこさんに交代
ねこさんが枝刈り全探索を再帰で書くことにしているのを見届けて後ろの問題を読むことにする
EはIEEE754だなぁと思いつつ微妙に違うし、と悲しい気持ちになってFを読む
Fは幾何にしか見えなかったのででかい三角形取って小さくしていく貪欲でいいんじゃないかと考える
G,Hは人間業で解ける問題に見えなかった
Dでねこさんが詰まりかけていたがすぐにはとさんのフォローが入りAC
よく見たら再帰関数の呼び出しが関数名が抜けて引数を返していた -Wall
オプションつけるかどうか、開始前にデバッグに付ければいいかなくらいの気持ちで同意してたけど付けたほうが無難かもしれないと思った
Eもねこさんが解法を生やしていてうそんとか思っていたらねこさんが「なにこれ!?」と声を上げる
ちらっとターミナルを見たら「浮動小数点例外」と出ていてバグ埋め界のtouristの面目躍如とばかりに「ゼロ除算じゃないですか?」と当てずっぽうに言ったところ思い当たる節があったらしくすぐにねこさんが修正してsubmit ACしたところで突破しそうだねという空気になって一瞬気が抜ける
Fは幾何慣れしていないせいで実装が厳しすぎた
ライブラリを印刷していたがよく分からんライブラリを持つものじゃないなぁと思っているうちにタイムアップ
最後に去年同様HにWA Submitして気持ちよくなるも、HにWAしてるチームが別に居たので「全部やればよかったー!」と叫ぶ
大会後
終わってみるとなんか12位で焦る
あとFAの結果企業賞が2つもらえるような空気でうれしくなる
お酒を3時まで飲み明かし帰宅
途中顔が赤黒いとか言われていたが顔色もまたバグっているので致し方なし
わらび餅はおいしく食べるはずだったのだが、まさかの切られていないわらび餅だったことが発覚
頑張って切ってきなこかけたがきなこが結構飛んだ(申し訳ない…)
感想(反省)
幾何はもう少し詰めないと話にならないという気持ちなのでAOJのLibrary of Geometryから埋めようかしら…(遠い目)
Fが難しいはそれはそうとして
あとAtcoder青が近いのでアジアまでには青にします(真顔)
大学の生協食堂のテレビにFA取った時の順位表の写真が上がるかもしれないって噂を聞いて戦慄してる