アルゴリズム忘備録

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

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

B: Moderate Differences - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

長さ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)。

A: Biscuits - AtCoder Grand Contest 017

agc017.contest.atcoder.jp

 

数列A[i]が与えられるので、部分列をとってその和の余りを0または1にしたい。そのような部分列は何通りあるか?

 

k番目までの数列の部分列をとったときにあまりが0または1になる組み合わせをa[0][k], a[1][k]とおく。A[k + 1]が奇数または偶数によって場合分けし、dpを更新していく。O(N)。

C: 節約生活 - AtCoder Regular Contest 007

arc007.contest.atcoder.jp

 

最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。

 

周期の長さを持つ01bitでoxを表現する。これを幾つかローテーションしてandをとったときに0になる最小の個数を求めればよい。周期は最大10個なので、全探索で十分に間に合う。O(N*2^N)。

C: THE☆たこ焼き祭り2012 - AtCoder Regular Contest 008

arc008.contest.atcoder.jp

 

N人の人が(x[i], y[i])にいる。それぞれ最大t[i]の速度でたこ焼きを投げられ、また最大r[i]までの速度で投げられたたこ焼きをキャッチできる。一人目の人が1秒おきにたこ焼きを投げ、その他の人もたこ焼きを受け取ったらそれを更に別の人に投げることができる。これを繰り返すことで全員にたこ焼きを行き渡らせる時、最小で何秒かかるか?

 

すべての人のペアについて、min(投げられる最大速度、受け取れる最大速度) の速度でたこ焼きを投げるとして、そのペアについてたこ焼きを投げるのにかかる時間をエッジの長さとしてグラフを構成する。

 

双方向だがそれぞれのエッジの長さが異なる完全グラフになる。完全グラフなので隣接行列で、最初の人からダイクストラで全員までの距離を計算する。この距離を降順ソートし、順に一秒おきにたこ焼きをその人に向かって投げるという戦略が最適。この時、min(たこ焼きを投げる時間+距離)が最小の時間になる。O(N^2)。