第三回ドワンゴからの挑戦状(dwacon)参加記
予選
Aやるだけ,B問題に手間取った.B問題に手間取ったときはもうだめかと思ったが,C問題D問題が得意な感じの問題だったので助かった.E問題の部分点確定で18卒パワーを使って予選通過が決まると思ったでEの部分点を取りに行った.方針は比較的早く立ったが,苦手な感じのDPで部分点を確定させるのに手間取ってしまった.
結局32位に食い込むことができ,非18卒が上に11人以上居れば通過が確定.後日予選通過メールが届いた.
本戦
前日
オープンコンテストの告知で公開された500-1100-1200(25)-1300という配点を見て凍りつく.Acで525ptsとった後は座るだけになることが見える.変な貪欲が想定解法の500ptsだと最悪0完もあり得るなと絶望するなどしていた.
本戦開始前
集合時刻の4時間前に宿泊先のホテルを出て,部屋は清掃中の時間だし行くあて無いなーとか言いつつ歌舞伎座周辺をぶらぶら.
15時頃にドワンゴのオフィスに上がる.
集合時刻が15時というドワンゴ的かつ人道的な時間.さすがドワンゴ.
受付が終わった後,控え室でTシャツを着たりニコ生用のアンケートを記入するなどする.Tシャツにタグがついていたのだけれど,はさみを持っていなかったので噛み切ろうと試みるも失敗.思いっきり引っ張ってみたらタグの糸が切れてタグを外すことができた.
準急さんやtozangezanさんが,「自己紹介書けないんだけど」と言いながら競プロerのいつものノリで会話をしていた.
コンテスト
A問題を500点と思って舐めてかかったら痛い目を見た.30分経ってもA問題の方針が見えない.辛い.正しい式にできるかどうかの判定は式が破綻した部分を数える感じで判定できることが分かったが,式の計算結果の最大化の方法が全くわからない.DPできる感じに見えなかったので必死になって貪欲を考える.
A解けないことが有り得ると思い,先にCの部分点を確保しに行く.Cの部分点は自明に二重ループ回すだけだった.35分ちょっとで25ptsを確定させる.
再びA.頭を冷やして考える.段々とDPが見えてくるが状態の持ち方がわからない.スタックの状態どうやって持つのとか言っていた.このあたりでは貪欲の可能性は完全に捨てていたが状態の持ち方が見えない.
続A.さらに冷静になって考える.O(|S|^3 * K^2)の区間DPがようやく見える.区間DPだと気付いた後の遷移のさせ方は単純なので迷わなかった.実装量はDPにしては多いと思ったが,そんなにバグる要素は無かったので落ち着いて実装.しかし答えを出力する部分で謎のbool値を出力する痛恨のミスを犯し10分ほど溶かす.死.82分ちょっとでAC.これ500ptsとは思えない.
C問題は考察しやすそうだったが,残り時間であの手の問題の実装をするのは無理だと判断し,順位表を見てBに着手する.問題設定からして「これ平方分割だよな〜」という感じの問題.いい感じの平方分割を思いついたと思ったが,実装を進めているとMLEしてしまうことに気づき無事死亡.MLE防ぐにはTLEする方法しか見えないしこれなんなんだーって言っていたらコンテストが終わった.
Acで19位.DDCCの順位も19位だったのでこの数には何かと縁がある模様.
解説
A問題の解説でchokudaiさんが「ここに居る人はこんなのサクッと通しましたよね〜」と18卒パワーで通った弱小コーダーを煽る.つらい.
B問題ついに逃げ続けてきたMo's Algorithmと向き合う日が来たのかと思った.ちゃんと勉強しようね.うん.
C問題は「なるほどね」って感じだった.コンテストが終わって実装したい感じの問題ではない.
D問題は読んで無いので解説もよくわからなかったが面白そうな雰囲気を感じたので後で解いておこうと思います.
表彰式
yutaka1999さんの名前が間違えられたのがハイライト
懇親会
タダ酒とタダ飯にありつく.人の金で飲み食いするのは楽しかった.
kobaさんやkimiyukiさんとお話しする.競プロな人とお話し.もるさんとお話ししたり,江添さんとお話ししたり,どわんごな人とお話し.
余興のぷよぷよ大会でchokudaiさんが優勝する.完全にプロ.ぷよぷよ大会の後 chokudaiさんを捕まえて,「A問題本当にあれ500ptsですか?」と聞いたところ「典型典型〜」とのこと.
あとケーキ
テレビちゃんが厚い。ブラウン管だったのか。 #dwacon pic.twitter.com/9LTagyFbrw
— kusanoさん@がんばらない (@kusano_k) 2017年1月14日
帰路
おひらきになったあと,ホテルまで戻る電車ではかみぺさんと一緒だった.Mo's algorithmのお話しとか「SRMのd1m埋めは効くぞ」という話しをしてもらう.「今日のA問題あれ500ptsじゃなくて800ptsぐらいあると思うんですけど」と言ったところ「800ptsも無くて多分600ptsぐらい.典型と言えば典型だし.」という意見をもらう.僕がDP苦手なだけだった.
その後,かみぺさんとお別れしホテルに戻りドワコン終了.
感想
コンテストは辛かったが,社内見学と懇親会は楽しかった.タダ飯はうまい.ドワコンのレベル的に自分が本戦に来れるとは思っていなかったので,本戦に出れたこと自体嬉しかった.