COLOCON 2018 本選
作成日：2018.01.21
カテゴリー：競プロ 参戦記録
▼更新履歴
- 2018.02.03
E問題の解説を追加
目次
コンテスト前の計画
配点は$300-400-600-800-1100-1300$である。
基本的に前から解いていくのが良さそうだ。
ただ、詰まったら後ろの問題も見るべきだろう。
コンテスト中
A,Bはすぐに解ける。[A 07:30 AC][B 14:09 AC]
C問題を見てすべきことはすぐに分かったが、計算量を落とす方法が思いつかない。
続いてD,E,F問題を順に見ていく。それぞれ少しずつ考察をする。
F問題についてはとっかかりが見えたが、先が長そうなので後回しにする。
D問題に戻り考察を進めると、適切にソートすれば良さそうであることに気付く。
そのまま解ききる。[D 62:39 AC]
C問題に戻り考察を進める。
しかし三分探索をすると解けそうという嘘考察をしてしまったため、50分近く時間を溶かしてしまう。
とっかかりが見えていたF問題に取り組む。
考察を進めると解けそうになったので実装する。
しかしサンプルが合わない。
デバッグしているうちに時間切れ。
コンテスト後(結果)
3完1500点の32位。レート変動なし。
C問題は典型の形まで持っていったのに解けなかったのは良くない。
F問題は解けそうだったのに解けなかった。
このような問題を解ききれるようになると良いのだが。
各問題の(軽い)解説
- A : ファイティング・タカハシ
- B : 異世界数式
- C : スペースエクスプローラー高橋君
- D : Chaos of the Snuke World
- E : キャプテン・タカハシ
- F : 高橋くんの帰還
A : ファイティング・タカハシ
問題文
$S$を繰り返した時に連続するようになる文字$A$に注意して答えを求める。
すなわち先頭から$A$が$x$個、末尾に$A$が$y$個連続していて、$S$に従って1回だけ操作をした時の答えを$z$とすると、$zN$$+xy(N-1)$が答えとなる。
但し$S$がすべて$A$からなる時がコーナーケースで、答えは$|S|N(|S|N+1)/2$となる。
B : 異世界数式
問題文
括弧も数字もそのまま残すことから、変えるべきは演算子とカンマだけである。
変換後はカンマが現れないが、カンマで区切られた数字が演算子で結ばれることになる。
その演算子は直前の開き括弧の前に現れたものである。
そして元々あった演算子は変換後には消える。
よって変換はstackを用いれば容易に行える。
C : スペースエクスプローラー高橋君
問題文
消費エネルギーの式を展開すると$a_j + j^2$$- 2ij$$+ i^2$となる。
$i$を固定すると、$i$に関する1次式たちの最小値を求める問題になる。
これはConvex Hull Trickやmonotone minimaで解ける形である。
D : Chaos of the Snuke World
問題文
対称性から$A \leq B$として良い。
また石板は$1/2$の確率でひっくり返されることから、初めにどの面を上にするかは関係がない。
どの順序にするのが良いのか考えるために2つの石板$i$,$j$を取り出して考える。
$i$と$j$を入れ替える確率は$1/2$以下にでき、そのような並べ方で$i$の方が先に来るとする。
この時の数の大小関係は小さいものから$A_iB_iA_jB_j$$(0)$,$A_iA_jB_iB_j$$(1/4)$,$A_iA_jB_jB_i$$(1/2)$,$A_jA_iB_iB_j$$(1/2)$である。
但し括弧内はその順で並べた時の入れ替える確率である。
このことから$B$の小さい順、$B$が等しい時は$A$の小さい順に並べるのが最適であるものの一つであることが分かる。
またこのように並べた時の操作の必要回数の期待値は、先頭から順に見ていった時にすでに見た$A$,$B$のうち$A_i$より大きく$B_i$以下であるものの個数の総和を$1/4$倍したものであることも分かる。
これは$O(N \: log \: N)$で計算できるから十分高速である。
E : キャプテン・タカハシ
問題文
数えるべきものについて知るために、ある整数列$\{B\}$が与えられた時にそれが条件を満たすかどうか判定する問題を考える。
グリッドの行や列ごとの状態についての制限があるから、二部グラフを考える。
潜水艦がいるグリッドの行と列を表す頂点間に辺を張っていき、$i$列目を表す頂点の次数は$A_i$、$j$行目を表す頂点の次数は$B_j$となるようなものが存在すれば良い。
これは容量$1$の辺が張られた完全二部グラフに、始点と$i$列目を表す頂点の間に容量$A_i$の辺、終点と$j$行目を表す頂点の間に容量$B_j$の辺を付け加えたグラフの最大流が$\sum A_i$($S$とする)となるかで判定できる。
だから、このグラフの最小カットも$S$でなければならない。
グラフのカットについて考える。
始点や終点を端点にもつ辺をそれぞれ$x$,$y$本切った時、カットにするには列や行を表す頂点同士を結ぶ辺を$(W-x)(H-y)$本切る必要がある。
この時切られた辺の容量の総和は$(W-x)(H-y)$に$A_i$のうち$x$個、$B_j$のうち$y$個選んで足したものとなる。
これが最小カットとなり得るのは、$A_i$,$B_j$を小さいものから順に選んだ時である。
$A_i$,$B_j$が昇順になっているとすると、最小カットについての制約から$(W-x)(H-y)$$+ \sum_{i \leq x} A_i$$+ \sum_{j \leq y} B_j$$\geq S$を満たしていれば良い。
以上で判定問題を解くことができたので、元の問題の数え上げを考える。
判定問題での考察から、$\{B\}$は小さいものから決めていけば良い。
そこで$\{B\}$を小さいものから$a$個決め終わり、$b$まで割り当て、その総和が$c$である状態$[a,b,c]$をもつDPを行うことにする。
先の考察より$c \geq S - (W-x)(H-b)$$- \sum_{i \leq x} A_i$をすべての$x$について満たしていなければならない。
よってこれを満たす範囲で$[a,b,c]$から$[a+n,b+1,c+(b+1)n]$($n$は非負整数)に遷移すれば良い。
$\{B\}$は昇順になっている必要はないから、並び替えの数を考慮するために係数を適切にかける。
状態の数が$O(H^2 W^2)$であり、各状態からの遷移が$O(H)$であるから、このDPの計算量は$O(H^3W^2)$となり十分高速である。
F : 高橋くんの帰還
問題文
まず帽子をかぶらなかった時の魔法エネルギー(以下魔力とする)の変化を考える。
位置を直前に通った扉の番号(一枚も通っていなければ$0$)と定義する。
実際に試してみることで、魔力が$0$となる直近の位置が$x$の時の次の位置は$3x+3$であり、$x$に偶数を足した位置と$x+1$では魔力が増加、それ以外の位置では減少することに気付く。
これにより帽子をかぶらなかった時の最終的な魔力を$O(log \: N)$で計算できる。
次にある位置で帽子をかぶることを考える。
元々魔力が増加する位置でかぶっても結果に変わりはないので、帽子をかぶらなかったとして考えれば良い。
このような位置の数はシミュレーションしながら容易に求めることができる。
魔力が減少する位置で帽子をかぶると結果が変わるのでシミュレーションし直さなければならない。
位置$p$で魔力が減少した結果$m$となるところを帽子をかぶることで$2p+m$になったとする。
この後$m \geq 3$ならば、$p+m-1$,$m-3$,$...$と続いていく。
これは次に魔力が$0$となる位置が$4$だけ小さくなることを表している。
よって$m \geq 3$の場合はまとめることができ、合わせて一回シミュレーションを行えば良い。
また$m \lt 3$の時は一つずつシミュレーションを行う必要があるが、魔力が$0$となるごとに定数個しかない。
いずれにおいても新たにシミュレーションをするのは$O(log \: N)$でできる。
以上より$O((log \: N)^2)$で答えを求められ、これは十分高速である。
但し、$N$に近い位置で帽子をかぶる時はコーナーケースになる恐れがあるので注意する。
関連
(新しい記事)＞