全国統一プログラミング王決定戦本戦 参加記
全国統一プログラミング王決定戦本戦に参加してきました。僕がどんな感じだったか書き残しておきます。
昼食
ゲン担ぎで"カツ"を食べました。そういえば某アニメでも決勝直前にみんなカツ食べてましたね。
昼食情報です pic.twitter.com/UYoBA4Pz0d
— NOSS@日経本戦 (@noss46) February 17, 2019
会場
会場は東京ドームホテルの地下1F「天空」でした。
— NOSS@日経本戦 (@noss46) February 17, 2019
会場はこんな感じ!電源も1人につき1つあるよ! pic.twitter.com/3RJqpxwDB8
— chokudai(高橋 直大)🍆🍡 (@chokudai) February 17, 2019
一人あたりの計算用紙の量がすごい pic.twitter.com/j0y5UlfOat
— chokudai(高橋 直大)🍆🍡 (@chokudai) February 17, 2019
全員に無地のレポート用紙一冊を配る。さすが全国統一の決勝はすごい...
受付を済ませてお話をしているとコンテストの時間になったので急いでPCの準備を整えてコンテストに臨みました。
コンテスト
A - Abundant Resources (200)
長さNの数列Aがあります。1以上N以下のkについて長さkの区間和の最大値を求めてください。
- 1 ≦ N ≦ 3000
- 1 ≦ Ai ≦ 109
累積和の前処理をO(N)で行うことで区間和をO(1)で求められます。あとは各kについてN-k+1回ループを回して全探索すればよいので全体計算量はO(N2)です。
B - Big Integers (200)
制約をよく見ると、A,B<K なのでA,BはK進数の各桁の値を表していることがわかります。つまりK進数の大小比較をすることになるのでN,Mが異なるならその大小、同じなら上位桁から見ていくようにします。
C - Come Together (300)
H行W列の各マスに駒が置いてあります。このうち(Ri,Ci)にあるK個の駒を取り除きます。1回の操作で1つの駒を上下左右の1マス隣に移動できるとき、すべての駒を1つのマスに集めるのに必要な最小操作回数を求めよ。
- 1 ≦ H,W ≦ 105
まず、マンハッタン距離の定義から移動をx方向とy方向に分離できます。x方向のみを一致させることを考えるとi列目にある駒の個数をAiとしてすべてをj列目に集めるためには
A0 * j + A1 * (j-1) + ... + Aj-1 * 1 + 0 + Aj+1 * 1 + ... + AW-2 * (W-2-j) + AW-1 * (W-1-j)
の操作が必要になります。ここでよく見ると一次関数を2つ合わせたの形をしていることに気づきました。累積和を2回とると一次関数になるのでこれを順方向と逆方向の2つ作っておくとj列目を境に左右をそれぞれO(1)で求められるようになります。よってjをN回ループしてその最小値を求められます。y方向についても同様に求められるのでx方向とy方向の最小値の和が答えになります。
D - Deforestation (500)
N本の竹があります。時刻0ですべての竹の長さは0です。時刻が1経過するごとに長さは1増えます。M回の操作を行います。i番目の操作は時刻 Tiに行われ、この操作では番号がLi以上Ri以下の竹をすべて伐採します。 高さxの竹を伐採するとき、x点を得ます。 また、伐採された竹は高さが0になりますが、その竹はこれ以降も伸び続けます。
M回の操作で得る得点の総和を求めてください。
- 1 ≦ N,M ≦ 2*105
- 1 ≦ Ti ≦ 109
- 1 ≦ Li ≦ Ri ≦ N
操作の内容はRAQとRUQだとわかったものの遅延評価セグ木をライブラリにもっていないのでネットから探すことになりました。ちょうどRAQとRUQを両方実装されているものが見つからなかったので自分でこの2つを融合させることになりました... さすがにセグ木に追加機能を書けるほどデータ構造の素養も無いので比較的デバッグしやすい平方分割で実装しました。しかし実装ミスも多く4WAと100分間をかけてなんとかACしました。
E -Erasure (700)
制約からみてDPが使えそうだなと思い、dp[i] = iまでをすべて消す通り のように置いて考えていました。ただ遷移がうまくいかなくて結局サンプル1しか通らず椅子を温めました。
結果とコメント
結果はABCDの4完で173位でした。
Cは駒の位置の中央値が最小値になるのでそっちの考察が生えていればもう少し楽だったかなと思います。Dは盆栽をしよう。もう少しEに時間をかけたかったという気持ちです。実力と言えば実力という結果だったと思います。
トークショー & エキシビジョンマッチ
競技プログラミングをするとどんな能力を養えるのかの話やこれからどうすればいいのかという話まで聞けてとても楽しく参考なりました。PFNすごいなあ…
決勝上位3名によるエキシビジョンマッチがそれぞれのコーディング状況がモニターにライブされるというすごい新鮮な企画でした。超爆速でコードが生やされているのをみてこれが日本最速コーダーか...と驚きをこえて笑いしか出ませんでした。見ている僕の時間感覚のほうが壊れました。とても面白かったのでまた企画してほしいなと思います。
懇親会
会場に500人もいるとなるとひとを探すのも一苦労ですね。幸運にも知り合いの方やお話したかった人と会うことができたので良かったです。曰く料理のクオリティーはオンサイトでもトップクラスだそうです。(さすが日経コンテスト…) とてもおいしくいただきました。あともっと知り合い増やしたいという気持ちになりました。(皆さんよろしくおねがいします)
感想
お話をしていると色んな大学で最近競プロサークルができたり、あるいは今作ろうと頑張っているという話を度々聞いて競プロ盛り上がってるなあと感じました。だからこそここまで盛大なコンテストを開催することができたんだなと思います。ちょくだいさんが「今日がターニングポイントになる」とおっしゃっていましたがそういう場に本戦参加者として立ち会えたことを嬉しく思います。来年も開催されるならまた勝ち抜けるようにこれから一層精進をがんばります。