アルゴリズム忘備録

競技プログラミングとかデータ分析とか

C: 茶碗と豆 - AtCoder Regular Contest 038

arc038.contest.atcoder.jp

 

位置iにある石を移動させるゲームを行う。位置iの石は左に1からC[i]の範囲で好きなだけ動かすことができる位置0にある石はそれ以上移動させることができない。先攻と後攻どちらが勝つか。

 

まずは位置iに石が1個ある時のGrundy数を愚直に計算する。位置0にある時、先攻の負けなのでGrundy数は0。あとは左から順にGrundy数を計算する。例えばgrundy数が{0, 1, 2} のとき、C[3]=2 ならば、一手勧めたときにあり得るGrundy数集合は{1, 2} であるから、この集合に含まれない最小の非負整数なので結局Grundy数は0になる。

 

さて、これを愚直に計算すると、石の数が1個の時Grundy数の1回の計算にO(N)の計算量が必要になる。そこで、インデックスがGrundy数を表し、そのGrundy数が最後に現れた石の位置を値に持つようなRMQを考える。すると、例えば[0, x)のminがi - C[i] 以上である時、すなわちGrundy数が [0, x) の範囲において、そのGrundy数が最後に現れたIndexが全てi - C[i] 以上である時、iにある石はいずれも [0, x)の範囲のGunrdy数を取ることが可能である。そこで、このようなxの上限を二分探索する。ただし、まだ1回も現れてないGrundy数の値は-1とする。すると、xがGrundy数になる。

このRMQをSegment Tree等で実装すると一回のGrundy数の計算がO(logN)になり、全体の計算量はO(N logN)になりまにあう。

E: Jigsaw - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

+字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か?

 

まず分かることは+と┴みたいなのは交互に来る必要があることがわかる。そこで、+の左の高さ(問題文でいうC)と┴の右の高さ(問題文でいうA)などが一致する、ということをグラフで表現する。高さと上に来る or 下に来るということを頂点として表し、n+ またはn-という頂点を作る。図形はそれぞれの形状に応じてとm±を結ぶエッジになる。また、下に来る頂点同士は常に接続可能なので連結にしておく。(図形でいうと┴を並べることに相当する) これらのことをUnionFindで確認し、全体が連結でない場合は不可能と判定する。

 

また、全体が連結であった場合でもある頂点に対して、右から接続する図形と左から接続する図形の数が合わない場合は不可能である。ただこの場合どちらかは┴型の図形なので、この図形よりも+型の図形の方が少ない、という判定のみでよい。

 

以上の条件ですべてNGと判定されなかった場合は可能と返す。O(N) (UnionFindを定数関数をみなすとだが)。

 

要は与えられた有向グラフがEulerグラフになっているかどうかの判定なんだとおもうけど、一般的なアルゴリズムでは計算量が間に合わない。そこで上のような方法を取る。

E: Awkward Response - AtCoder Regular Contest 078

arc078.contest.atcoder.jp

 

公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。

nN かつ 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

arc078.contest.atcoder.jp

 

木が与えられる。頂点のうち、1点は白、もう1点は黒、残りは色なしの状態である。先手は白に塗られた頂点から隣接する頂点にだけ、後手は同様に黒の頂点だけ色を塗っていくことが可能である。ただし、既に塗られたところには上塗り出来ない。交互に手番がきて操作ができなくなったほうが負けのとき、勝つのはどちらか?

 

木なので、最適戦略はなるべく自分しか塗れない領域を増やすことだとわかる。そこで、まず最初の白の頂点と黒の頂点について最短パスを求めよう。この最短パスの長さが偶数、及び奇数の場合について場合分けし、それぞれが塗ることが可能な最大距離を求める。あるところで最短パスの中で白と黒の頂点の境目ができるが、ここで木を分離し、二つの木を作る。するとこの木は白及び黒が塗ることができる最大手数になっている。あとはこれをdfsなりでカウントすればよい。O(N)。

D: Game on Tree - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

木の根を含まない部分木を交互に取り除いていき、操作ができなくなった(根しかない状態になった)ほうが負けとする。最適な行動を取る時先手後手どちらが勝つか?

 

Green Hackenbushとかいう有名問題とのこと。明らかにGrundy数であるが、導出はやや複雑。結果だけ書くとある部分木について、その部分木のGrundy数をすべてxorを取り、1を足すことで元の部分木のGrundy数になる。これを再帰的に計算し、Grundy数が0ならば後手の勝ちで、そうでなければ先手の勝ちである。O(N)。

C: Snuke and Spells - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

数列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

arc078.contest.atcoder.jp

 

数列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)。