情報妖精の競プロ日記

AtCoderの問題に対する方針を主に書きます

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

全国統一プログラミング王決定戦本戦に参加しました!
全国統一プログラミング王決定戦本戦

ここでは実際に参加した時の感想などを書いていきます。
また、問題の解説は後日上げます。

  • 11:30 開場

現地到着。
正面にホテルが見えているのに右側に曲がり始める方向音痴と化していて、流石に自分で笑ってしまったw
その後会場入りし、設営を開始
11:45には設営が終わったので他の競プロerと話しに移動

  • 12:30 開会式

全員が着席し、試験の注意事項などが話される
なぜか紙の問題用紙が配られて、隣の人と一緒に困惑
その後、今書いてるこのブログなどを準備し、時間になるまで待機
カウントダウンとともに開始

  • 12:45 決勝開始

まずはA問題を読み、累積和上のスライド最小値{\rm O}(N^2)であると確信
実装して提出、12:49にAC(現時点133位)
次にB問題
これ、単に上から比較で終わるので終了
大文字小文字に気を付けて提出、12:56にAC(現時点116位)
12:57 C問題読み始め
まず、そのあるマスが(0, 0)だったとする
そうすると、移動させるマスの合計数は空欄以外のすべてのマスであり、これは数学で{\rm O}(1)で求まる
だがこれだと計算量に問題があるね
ところで、これ移動距離はマンハッタン距離だから縦横独立に求められないか
後はそれの和で出せそう
お、なら答え出るな
まず、縦の位置をyに決め打つと、移動させる距離は\frac{y(y+1)+(H-y-1)(H-y)}{2}から各取り除いたコマとの絶対値の和に等しい
これは予めC_iの小さい順にソートしてあればならし{\rm O}(H)、これを計算すれば解けるね
ちょっと遅くなったけど13:39提出、WA
……オーバーフローか?
問題見直してたらxy逆にするミスを発見、修正して13:54提出でAC(181位)
13:55 D問題読み始め
遅延セグ木の問題にしか見えないので遅延評価セグメント木について - beet's soilを貼りました
自分で作ってなかったのミスです、まぁAC(164位)
14:33 E問題とF問題を同時に読む
F問題について考察開始
まず、そのままならDijkstra法になるが辺が多すぎるのでTLE
そこで、何らかの方法で辺を減らせないか考察
まず、X_i順にソートすると、前の方から後の方へ向かうことができるわけだ
Y_iが無いとするとこれは自由に行き来できることになるが、例えばこの小問題について解くことができるかを考えてみる
すると、金額は大きい方の国が決めているので、大きい方から見ると

  • 直接向かう、かかる金額は自分と同じ
  • 自分より大きい中で最小の国を経由する、かかる金額はその国の金額x2

の2通りしかないことが分かる
ということはこれはX_iを大きい順にみていって、その時の上の条件のうち小さい方を求めていけばいいので{\rm O}(N)で求められることが分かる
この性質をなんとか一般化できないか考えてみよう
まず、まずいのは同じ法則ではいけない場所があるということ
まずx順にソートしておく
この時、各頂点についてDAGでそのようなものを見つけられると便利そう
自分よりX, Yともに大きいもので、まだ繋がってないようなものを経路として持ちたい
もちろんDAGなので辺の数は簡単に抑えられて、この上でならクラスカル法を用いることができる
後はこのDAGの作り方を考える
DAGはx昇順に考えたときy座標に対してsetを使いつつ繋ぐ先が分かって、辺の数が{\rm O}(N)に抑えられたからあとはやるだけ
……とか言ってたら時間になってしまったので終了

  • 15:45 コンテストが終わったので隣の人とFの考察

なんか話がかみ合わないので終了、たぶん私の考察が間違えているのですね
その後はトークショーだが聞き流しつつ更に考察
S, Tを固定しながら考えたら楽かと思ったが、(i, 10^8 - i - 2(-1)^i)みたいな点が与えられると絶望せざるを得ないのでやっぱりクラスカル法か?

  • 16:50 表彰式

やっぱ上位勢強いなー

Chokudai SpeedRun 002じゃん
A問題、開幕トラブルで開始時間ずれてるの大変そう……ってか順位に響かないかそれ
……えー、準急さん速すぎませんか
めっちゃ速いんだが、上位陣になるならあの速解きしろとか言われても困るぞ……
後で問題読んでみたら自明だったので確かにあの速度も納得できるけど、でも速すぎた

  • 17:30 懇談会

えー知らない人が多すぎて話すの難しいですね(?)
分かりやすいようにチルノグッズを揃えて歩いたけど、話したい人に話すのが困難だった
あ、でも直大さんからサインとステッカーもらった!
後はきゅうりさんと話したり、いつもTLで話してる人とリアルで話したりと楽しかった
食事は全然食べられなくて、19:20すぎて人が減ってから早食いチャレンジしました()
ちょっと500人は多すぎなので、次回はコンテスト会場が4倍の大きさか人数が1/4のコンテストで話したいですね~
というか二次会したかったです、次があったら企画するか


ちなみに、最終順位は167位です
ABCDやってFに挑んでるので妥当な結果ですかね