THEモアイのブログ

140字じゃ足りないことを

コドフェス2016参加記

プロもすなる参加記というものを、参加したので僕も書いてみようと思います。

 

とりあえず実力を書いた方が話が見やすそうなので実力等を適当に。

競プロ歴:1年半ぐらい(ICPC2015~)

数学科の修士2年(就職するのでラストでした)

本戦前AtCoderレート:1740(500~700が解けるか解けないかぐらい)

去年はサンクスフェスのほうにいました。(4位)

当日まで

予選Bの日に友人と遊ぶことが確定していたので(友人と気持ち良く遊ぶために)予選Aで頑張った結果、D問題が難しかった恩恵により3問早解きで通過。通過して満足してしまったので特に本戦に向けた特別な練習はせず。

太鼓の達人はワンチャンを感じていたので一昨年友情ぽっぷ、去年さいたまと来ていたから旧9あたりをたまにやっていました。

当日

時間を調べたら新橋が意外と近かったので余裕を持って駅に到着。しばらく道に迷って外国人に道を教えてたりしたら会場までの地図を印刷して持ってきている人を見たので話しかけてAC。会場到着後、本戦始まるまではルールとか読んでぼーっとすることに。パーカー1600点って今の実力じゃあ厳しいなぁとか思ってた。

そしたら唯一本戦に通った後輩が来て適当な会話。Chokudaiさんも来て(?)適当な会話。既出の問題だったらAtCoder Ploblemsから探して解説に飛ぼうとか思って開いていたので、問題をあまり埋めていないのがバレてしまった。一応ABCは割と埋めていたので、それを見せるなどしました。

本戦

BのFAを狙う。無考察でホイしてAを読む。1分ぐらい画像でsnuke(敬称略)を探す。H6にあった!って思って読み進めたらそういう問題じゃなかった。あとBのWAが発覚。このあたりで急ぐのをやめる。AをAC(7:04)。

BをAC(10:03)。解説スライドとは微妙に違うやりかただった。N=1なら1を出力、そうでないならN<=i(i+1)/2となる最小のiを出力したらN-iについて再帰って感じです。

C読む。この時点で「コミュニケーションを取る」が再帰的に定義されていることに気付けず。ただ面倒そうだったのでスルー。

600点だったら貪欲かもしれないけど700点だったら貪欲じゃないんだろうなーとか勝手に思いながらD読む。そう思ってしまっていたのでスルー。だろう運転は良くないですね。

E読む。二分探索決め打ち。決め打ちした後適当でも部分点ぐらいもらえないかなーって感じで適当に再帰書いたらサンプル合わず。

1000点とか解いたことないんだよなぁとか思いながらFを読む。N=Mなら自明。N>Mも自明。N<Mが問題だなぁまで行く。真面目な考察を開始。

日にちが余っているので、町の開拓か、既に行った町で遊ぶかの2択だと思ったのでDPを書き始める。並列して二項係数で書けるっぽさも感じていたので、両方ちょっと書いてみる。そしたら遊ぶ時に町1に戻ると変なことが起きることに気付く。例えばN=7,M=8だったら1から2>3>4>1>5>6>7>みたいに進むと最後1じゃなくて2,3,4に行っても完成するんですね。それに気付いてしまったので、あとはdp[行った町][日数][題意を満たしている部分]について、遊ぶ・進める・セーブの3通りの遷移という要するに解説スライドをしてACしました。(92:27)

1000点問題が解けてめっちゃ嬉しかった。(93分頃?)でもABFでは1400点なのでパーカー圏外。

Cの200点(パーカー)を取りに行きます。先述した通り問題の解釈をミスっている(通訳は1人までだと思っている)ので、bool[1000][1000]に書き込んで頑張ってもサンプル1で合わず(チェック前に提出してWA)。サンプル手でやったらサンプル間違ってる疑惑が勝手に浮上。下の文章的に何か数字が落ちてるのかなぁって感じでclar投げたら(135:21)僕が問題を誤解していることが非常にわかりやすいように返答していただけた(137:47)ため、正しい理解を得る。(指摘が無いのはプロはこのレベルならサンプルチェックしないからだろうとか思ったりしていたけどそんなことなかった。)

C部分点(パーカー)ゲット。(141:03)ここで終わった気になって、一気に疲れが来る。

C問題の正しい理解を得ているのでCをAC(153:09)。

Eは決め打ち以降全探索書いてるつもりなのにサンプル3が合わなくてG,H,I,J,Kを読むなどする。特に何もなくおしまい。

ABFC4完1800点153:09の119位でした。

1日目の残り

tourist 近畿日本 touristという川柳を浮かぶもつぶやくに至らず。

太鼓の達人を最速で1回やる。

課題曲:残酷な天使のテーゼ(むずかしい)

無反応でコンボ切れた低スコアだったので、明日やることに。

いつから携帯電波使用OKか分からず、とりあえず使用しないことに。

解説見に行ったらちょうどD問題だったので聞く。聞いて分かった気になるのが好き/chokudaiさん解説に久しぶりさを感じた/家で解説放送に音をつけないためすぐ放送を閉じちゃうのですが、今なら音ありで聞ける...みたいな理由から結局Jまで全部聞いた。

余ってた硬くなっているピザを3切れだけ食べてエキシビジョンを見に行く。日本チームのAの提出の早さ、海外や日本のBの乱択提出、IndeedチームのBのACが印象的だった。

リレーの顔合わせ、メンバー決まっていると知らずに適当なチームに混ざって英語出来ないトークをしていたらメンバーが決まっていて、行くべき場所があると教えてもらった。日本語もダメだった。

ホテル絡み

とりあえず駅に着く。道に迷う。グーグルマップを開く。道に迷う。ポケモンGOを開く。グーグルマップを開く。ホテルっぽいのを見つける。横断歩道が無いから迂回。ホテルを見失う。発見。AC。サンクスで夜食を買う。部屋着。

YouTubeで課題曲の譜面を見たり(あまり意味なかったけど課題曲の575に気付いた)夜食の食べ過ぎで眠れなかったりしていた。翌日のため、めざましをセットしてテレビをつけたまま、1:30ぐらいに寝た(ほぼ寝落ち)。

2日目

5:50めざまし気付かず7:30起床。支度が遅いので絶望していたが8時前には出発。とりあえず線路沿いを歩く。グーグルマップを開いて駅と逆方向に進んでいると気付く。駅に着いて、使った出口に合わせて、昨日帰りに必死に記憶した道を通ってAC。(ツイッターによると8:11)

朝食に575を感じてつぶやく。トーナメントの戦略を練る。119位なのでアレだが、ほとんどの人が本戦でD+E部分点のところ、僕はFを解いているので問題セット次第だろうって感じだった。ありうる得点を列挙しておこうと思ったけどやめた。携帯の電波を切ることを思い出したのでTwitterに流した。

トーナメント

A見たふりをしてすぐBに行った。多倍長整数の二分探索が出来ればそこそこの部分点だろうということで、(ちゃんと計算量を考えると600点が取れそうな解法だった)答えが正になる引き算と/2の実装。残念なことに、思いついたのにやらないのはもったいない気がしてしまったのと、島で最初にタイピングを始められるというのも取り組むに至る理由だったかもしれない。

実装終わったら後5分も無かった。順位表を見たら3人しか正の点数を得ていなかったので、点数の確保に切り替え。なぜかA200に行ってしまい、誤読もしてしまい死亡。0点(島4位タイ)だった。多倍長ライブラリの必要性を感じた。B100行けば良かったのもそう。

リレーまで

体力測定。前屈-10、握力40未満、背筋2桁、垂直跳び40台。

昼食は肉のやつ。美味しかったです。

昼食後すぐに太鼓並んだら食後でアレだった。あと課題でも倍速かけて良いことを確認したけど倍速慣れしていなかったので無理だった。1位が可16なことが判明したのでフルコンせずに諦め。課題曲をDP(DoublePlay)して左右合計987kで勝手に1位の方を超えた気になっていました。

リレー

太鼓のやりすぎで疲れが、良くないですね。あと遅く来たのでTシャツはSサイズに。

ICPC2015では戦略担当だったので、準備や戦略の提案等を少ししました。具体的にはコーディングスペースはPC置き場と椅子前コーディングスペースに分けるとか、チーム内のグループ分けの方針を複数提案とかですね。

で、実力順6位の僕は11位の方と組んでA問題に取り組むことに。Text(cat)の提出に備えたり、Aは画面で問題を読むからC担当の方にマウスの操作を頼んだり、最初にコーディングするなら椅子の前にPC用意しましょうとか言って用意してもらったりしました。ちなみにABCDEまで担当を決めた後は流れで自由にという予定になりました。

で、問題OPEN。A見て和分の積だねって共有してすぐコーディングしてもらうことに。F読んで考察開始。AをACしてもらい、最初の仕事が終わったなぁって感じでした。

Fの考察をしていたら、おそらくKを読み終えたUm_nik大先生が舞い降りてFはこうやるんだよーって漸化式を教えてもらったけど英語だったため、a_iが何を表しているのか分からず。2回聞いたら分かった気がしてきたのでOKする。分かった。タイピングスピードが遅いので、コード量が多いと嫌だなぁとか思っていたけどDPで良かった。(実は数学Bをすると2ベキ-2になって2行で書けることを後から聞いた)

で、チーム全体の様子を確認することに。Iの考察が重いらしい。Fが終わっているのでコーディング順番を確認しながらIの考察に参加。円順列が(N-1)!通りだしN>=3ならOKそうとか予想はしたが、FのACまで進捗無し。

しばらくして、2人が同時に第三者を見るのはOKと言うのを発見、共有まで済ませる。その流れで奇数は自明だって教えてもらった。問題は偶数。

と言うわけで考察していたら、プロ組は二部グラフを作って実装が楽な方法を見つけたのだが、僕がA問題で和分の積と共有した彼が超簡単な方法(2nを1と2n-1に分ける)を思いついたのでそれが採用される。残り時間ギリギリでIを頑張ってもらうもタイピング抜けがあって偶数だけWAで9完終了。

最後のほう

複数方向からのレッドブルのにおいがきつかった。

旧おさるさん久しぶりに見た気がする。笑いを取っていて芸人力を感じた。

ほとんど橋に惹かれた。書道も川柳も入賞者は抜けてる(良い意味)気がする。(入賞したことによってそう感じるのかもしれない。)

帰りは後輩とチームのA担当で三角関係が発覚して三人でラーメンAC後帰宅おしまい。

感想

適当に思ったことをダラダラ書いていたら4000文字超えて4時も超えててびっくりした。

はてなブログの機能とか作法(?)とか良く知らないので、次何か書く時にはちょっと機能使いこなせたら良いなぁ。

タメ語と敬語が混ざっててアレそう。

まぁ眠いから許してくださいな。