Codechef April Challenge 2016
解法の概要だけ書いておきます。詳しい解説は書きません。
A 問題 Chef and Coloring
問題概要
色のついた部屋が一列に並んでいる。すべての部屋を同じ色に変えるには最低でいくつの部屋を塗り替える必要があるか。
解法
色を一つ決めて、その色に揃えるコストを調べる。その最小値が答え。
Codechef April Challenge 2016 Chef and Coloring · GitHub
B 問題 Chef and Ballons
問題概要
赤色の風船が R 個、緑色の風船が G 個、青色の風船が B 個ある。無作為に N 個の風船を選んだとき、同じ色の風船がかならず K 個以上選ばれるような最小の N を求めよ。
解法
最初にそれぞれ K-1 個ずつ選んでしまうのが最悪ケースなので、min(K-1,R)+min(K-1,G)+min(K-1,B)+1 が答えになる。
Codechef April Challenge 2016 Chef and Ballons · GitHub
C 問題 Chef and Magical Path
問題概要
N×M のグリッドがあるので、始点と終点が隣接していて、かつ各マスをちょうど一回訪れるような経路が存在するか判定せよ。
解法
市松模様の白黒で塗り分けると始点と終点の色は異なる。（奇数）×（奇数）のとき経路が存在するとしたら白→黒→白→…→白という経路になるので構成不可能。一方で、少なくとも片方が偶数であれば構成できる。1×M の形だけ例外なので気を付けよう。
Codechef April Challenge 2016 Chef and Magical Path · GitHub
D 問題 Help Watson Escape
問題概要
問題文分からず。
解法
問題文が分からなくても k*(k-1)n-1 が答えであることは予想がつく。
Codechef April Challenge 2016 Help Watson Escape · GitHub
E 問題 Fibonacci Queries
問題概要
数列 An が与えられる。以下のクエリを処理せよ。
- A[x] を y に変更する。
- 区間 [l,r] のべき集合のすべての要素 S に対して F(sum(S)) を計算し、その総和を求める。
解法
セグメント木を使う。F(S):=sum(F(sum(A)),A∈2S) としたとき、F(S) と F(T) を使って F(S+T) が以下のように表せる。
- F(S+T)=F(S-1)F(T)+F(S)F(T+1)+F(S)+F(T)
これはフィボナッチ数の性質 F(n+m)=F(n-1)F(m)+F(n)F(m+1) から導ける。この計算には F(S-1) や F(T+1) も使っているので、実際にセグメント木のノードに持たせるのは F(S-1), F(S), F(S+1) の 3 つ。
- F(S+T)=F(S-1)F(T)+F(S)F(T+1)+F(S)+F(T)
- F(S+T-1)=F(S)F(T-1)+F(S)F(T)+F(S-1)+F(T-1)
- F(S+T+1)=F(S+T)+F(S+T-1)
Codechef April Challenge 2016 Fibonacci Queries · GitHub
F 問題 Devu and good strings
問題概要
文字列 S が与えられる。たかだか K 文字を書き換えて S[i]=S[i+d]=S[i+2d] となるような i,d が存在しないようにしたい。このような書き換え方は何通りあるか。
解法
実はそんなにパターン数がないため枝刈り全探索で間に合う。ただし僕はぎりぎり間に合わなかったので最悪ケースを埋め込んだ。
Codechef April Challenge 2016 Devu and Good String · GitHub
G 問題 Amazing Experiment
問題概要
木が与えられる。頂点 v を根とする部分木の半径を各 v に対して求めよ。
解法
木の半径を与える頂点を中心と呼び、中心は直径上に存在する。各部分木の中心は直径 DP をしながら効率的に求められる（と思う）。
中心を求めるときに最遠点との距離が欲しくなるが、最遠点はかならず直径の両端のいずれかなので簡単に計算できる。
Codechef April Challenge 2016 Amazing Experiment · GitHub
H 問題 Mario and Luigi
問題概要
グラフ G が与えられる。G の i 番目までの辺を使ったグラフで次のようなゲームを行う。
- プレイヤーは交互に操作を行う。
- まだ塗られていない頂点を自分の色で塗りつぶす。
- 塗れる頂点がなくなったらゲームを終了する。
- 辺の両端が同じ色だったら、その色のプレイヤーに辺のコストだけ得点が入る。
先手はスコアが最大になるように、後手はスコアの差が最小になるように行動するとき、最終的なスコアの差を求めよ。
解法
塗った頂点に接続している辺のコストの総和だけスコアが入るゲームだと考えてもスコアの差は変わらない。なぜなら、両端の色が異なる辺は両プレイヤーのスコアに加算されているため差には影響を与えないから。
そのため接続している辺のコストの総和が大きい頂点から塗るのが最善になる。これは以下の操作ができれば求まる。
- ソート列の（偶数番目の総和）-（奇数番目の総和）を求める。
- K 番目の値を x に変える。
僕は平衡二分木のノードに偶数番目の総和と奇数番目の総和の情報を持たせることで実現した。
Codechef April Challenge 2016 Mario and Luigi · GitHub
I 問題 Chef and Big Matrix
問題概要
N×Mのグリッドが与えられる。二匹のウサギが(1,1)→(N,M)に向かって同時に進むとき、ウサギが始点と終点以外で同じマスに止まらず、かつ途中にあるニンジンを合わせて D 個より多く取らないような経路は何通りあるか。
解法(7pts, 11pts)
- dp[ウサギ 1 の y 座標][ウサギ 1 の x 座標][ウサギ 2 の y 座標][今までに取ったニンジンの数] := この状態に至るパターン数
として DP をする。
解法(13pts)
ウサギが重ならないような移動というのは y1≦y2 かつ x1≧x2 を満たすような移動である。y座標とx座標の差にだけ着目することで場合の数が以下の式で表せることが分かる。
$$ \sum_{i=0}^{\min(h,w)} \frac{(h+w)!}{ (2i)! (h-i)! (w-i)! } C(i) $$
ここで C(i) はカタラン数。
任意 mod で二項係数を求めるには Lucas の定理の拡張が使える、ということを uwi さんのページを見て知った。
色々工夫しないと TLE するので注意。
Codechef April Challenge 2016 Chef and Big Matrix · GitHub
最後の問題の満点が全然分からなかったけど、任意 mod 二項係数のライブラリが完成したので満足。
