E: Jigsaw - AtCoder Grand Contest 017
+字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か?
まず分かることは+と┴みたいなのは交互に来る必要があることがわかる。そこで、+の左の高さ(問題文でいうC)と┴の右の高さ(問題文でいうA)などが一致する、ということをグラフで表現する。高さと上に来る or 下に来るということを頂点として表し、n+ またはn-という頂点を作る。図形はそれぞれの形状に応じてn±とm±を結ぶエッジになる。また、下に来る頂点同士は常に接続可能なので連結にしておく。(図形でいうと┴を並べることに相当する) これらのことをUnionFindで確認し、全体が連結でない場合は不可能と判定する。
また、全体が連結であった場合でもある頂点に対して、右から接続する図形と左から接続する図形の数が合わない場合は不可能である。ただこの場合どちらかは┴型の図形なので、この図形よりも+型の図形の方が少ない、という判定のみでよい。
以上の条件ですべてNGと判定されなかった場合は可能と返す。O(N) (UnionFindを定数関数をみなすとだが)。
要は与えられた有向グラフがEulerグラフになっているかどうかの判定なんだとおもうけど、一般的なアルゴリズムでは計算量が間に合わない。そこで上のような方法を取る。
E: Awkward Response - AtCoder Regular Contest 078
公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。
n≤N かつ str(n)≤str(N)を満たす
n>N かつ str(n)>str(N) を満たす
この時、最大64回の質問でNを特定せよ。
まず分かるのはnにSuffix 000000... をつけておくと n>=N は必ず満たされるので文字列比較のみになり2分探索でnのあるprefixとNが一致するように特定することができる。ここではN<=10^9がわかっているので、10Nから100Nの範囲で探す。
その後、prefixの桁数を特定すればそれが答えである。Nが10の累乗の場合でない場合は、10^10, 10^9,...などと比較していくと、一番目の条件が一致した段階でちょうど桁数になっている。Nが10の累乗でない、というおのは探索したnの最上位の桁が1より大きい時と見ればよい。
Nが10の累乗の可能性があるとき、こちらは逆に9999999... と言った数字と比較する。すると2番目の条件で判定できる。O(logN)。
D: Fennec VS. Snuke - AtCoder Regular Contest 078
木が与えられる。頂点のうち、1点は白、もう1点は黒、残りは色なしの状態である。先手は白に塗られた頂点から隣接する頂点にだけ、後手は同様に黒の頂点だけ色を塗っていくことが可能である。ただし、既に塗られたところには上塗り出来ない。交互に手番がきて操作ができなくなったほうが負けのとき、勝つのはどちらか?
木なので、最適戦略はなるべく自分しか塗れない領域を増やすことだとわかる。そこで、まず最初の白の頂点と黒の頂点について最短パスを求めよう。この最短パスの長さが偶数、及び奇数の場合について場合分けし、それぞれが塗ることが可能な最大距離を求める。あるところで最短パスの中で白と黒の頂点の境目ができるが、ここで木を分離し、二つの木を作る。するとこの木は白及び黒が塗ることができる最大手数になっている。あとはこれをdfsなりでカウントすればよい。O(N)。
C: Snuke and Spells - AtCoder Grand Contest 017
数列A[i]が与えられる。この数列は時刻tにX[i]番目がY[i]に変化する。時刻tでの数列に於いて、「k個の数がある時、kの数字を削除する」という操作を繰り返すことで数列を空にしたい。そのためには時刻tでの数列から何個の数字を変えればよいか。それぞれの時刻について答えよ。
数列内にYという数字が書かれた数がk個あるとき、[1, N]に対して [Y, Y - k) という被覆を考える。この被覆が[1, N]をダブりなくかつ完全に被覆するときに操作で空になることがわかる。すなわち、被覆されてない長さが変えなければいけない数字の個数である。
ここでX番目の数YがY'に変化すると被覆はそれぞれ
[Y, Y - k) -> [Y, Y - k + 1)
[Y', Y' - k') -> [Y', Y' - k' - 1)
という変化をする。まず初期状態の被覆について、それぞれの被覆の多重度をもつ配列count[y]を計算しておく。このcountを上の被覆の遷移に従って更新していく。この時、この変化によって元々被覆の多重度が0であったところが正になったり、その逆が起きた時全体の被覆されてない長さはそれぞれ1増えたり減ったりするのでそれをカウントしていくと、それぞれO(1)で計算できる。全体ではO(N+M)。
C: Splitting Pile - AtCoder Regular Contest 078
数列a[i]が与えられる。|(a[1]+...+a[k]) - (a[k+1]+...+a[N])|を最小化せよ。
a[i]の累積和sum[i]を計算しておくと、(a[1]+...+a[k]) 及び (a[k+1]+...+a[N]) はそれぞれO(1)で計算可能。これでkを全探索すればよい。O(N)。
B: Moderate Differences - AtCoder Grand Contest 017
長さNの数列を構成したい。最初と最後の要素がA, Bで与えられる。また、隣り合う要素同士の差はC以上D以下になるようにしたい。このような構成は可能か?
最初の要素を除くN-1個の要素について、k個が前の要素以上、N-1-k個が前の要素以下と仮定してもよい。その時、kを固定すると、最後の要素Bとして可能な値の範囲は次のようになる。
A + kC - (N-1-k)D <= B <= A + kD - (N-1-k)C
与えられたBがこの条件を満たすなら構成が可能。O(N)。