NOSSの雑記

主に競プロでやったことを書きます。

全国統一プログラミング王決定戦本戦 参加記

全国統一プログラミング王決定戦本戦に参加してきました。僕がどんな感じだったか書き残しておきます。

昼食

ゲン担ぎで"カツ"を食べました。そういえば某アニメでも決勝直前にみんなカツ食べてましたね。

会場

会場は東京ドームホテルの地下1F「天空」でした。

【公式】東京ドームホテル

全員に無地のレポート用紙一冊を配る。さすが全国統一の決勝はすごい...

受付を済ませてお話をしているとコンテストの時間になったので急いでPCの準備を整えてコンテストに臨みました。

コンテスト

全国統一プログラミング王決定戦本戦 - AtCoder

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人もいるとなるとひとを探すのも一苦労ですね。幸運にも知り合いの方やお話したかった人と会うことができたので良かったです。曰く料理のクオリティーはオンサイトでもトップクラスだそうです。(さすが日経コンテスト…) とてもおいしくいただきました。あともっと知り合い増やしたいという気持ちになりました。(皆さんよろしくおねがいします)

感想

お話をしていると色んな大学で最近競プロサークルができたり、あるいは今作ろうと頑張っているという話を度々聞いて競プロ盛り上がってるなあと感じました。だからこそここまで盛大なコンテストを開催することができたんだなと思います。ちょくだいさんが「今日がターニングポイントになる」とおっしゃっていましたがそういう場に本戦参加者として立ち会えたことを嬉しく思います。来年も開催されるならまた勝ち抜けるようにこれから一層精進をがんばります。

日本経済新聞社AtCoder、協賛の皆様。このようなコンテストを開催してくださりありがとうございました。