Educational Codeforces Round 22 C. The Tag Game
木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。
Aさん及びBさんがいる地点からの距離を全列挙する。この時、木の性質としてある2個の地点間の最短距離はただひとつのルートしかいない、という性質を使うと、ある頂点pに於いて、d(A, p) > d(B, p) であれば、その頂点にBさんは来ることが可能になる。なぜならそこまでの経路上の点qに於いて、d(A, q) <= d(B, q)という点があったとすると、先述の性質によりqはB-p間の最短経路上の点になりえず、Bさんがまっすぐそこに向かえばqは通らないからである。
なので、Bさんとしてはd(A, p) < d(B, p) であるような点のうち、最長の点に行くという行動を取るのが最適になり、Aさんはそこにまっすぐ向かい追いついた時点でゲーム終了となる。O(N)。
コーナーケースとして、初期位置からAとBが重なっている場合は0になる。
Yukicoder 524 コイン
N(0<N<2^32)枚のお皿に1個、2個、…、N個の石が入ったNIMを行う。先手の勝ち負けを判定せよ。
Editorial読むと単なる実験ゲーでmod4 = 3を出すだけ。
ここでは自分で解いた時の考察を残す。
NIMなのでGrundy数を計算する。Grundy数は1 xor 2 xor 3 xor ... xor Nであり、これが0なら先手の負け、それ以外は勝ちである。
ただし、Nが大きいのでO(N)では間に合わない。そのため各bitごとにxorを計算し、1になる桁があった時点で勝ち判定を返す。
1桁目は1 0 1 0 の繰り返しなので、N mod 4が1または2の時1なので、勝ち確定。それ以外のときは2桁目へ進む。
2桁目は0 1 1 0 0 1 1 の繰り返しなので同様に判定する。これを最上位の桁まで行う。すべての桁で0であれば負け確定。
Codeforces 417 B. Sagheer, the Hausmeister
n階m部屋と両脇に階段(よって全体の幅はm + 2)の建物がある。最初は1階の左はじにいる人が各階の電気をすべて消し、上にのぼる、次の階もすべて消し上にのぼる…を繰り返してすべての部屋の電気を消す。最初に点いている部屋が与えられる時、最短の距離を求めよ。
ある階を消し終わって右端にいる時の最短距離及び左はじにいる時の最短距離を仮定すると、次の階はそれらの二つを使って求められるのでdpになる。最後の階だけは端の階段に戻らない、最初の階は一番右にある電気のついてる部屋 or m+1というところを気をつける。dpの遷移自体はO(n)。単に入力の読み込みだけがO(nm)。
Yukicoder No.520 プロジェクトオイラーへの招待
No.520 プロジェクトオイラーへの招待 - yukicoder
三角形の各辺について、a個、b個、c個の内分点が与えられる。頂点及び内分点同士で直線を互いに交わらないように引けるだけ引く。線の引き方は何通りあるか？
真ん中に三角形ができるパターンと出来ないパターンの二通りを考える。
真ん中に三角形ができるパターン
各辺から1個点を選び、それで三角形を構成する。これが真ん中にできる三角形になる。a * b * c通り。
次に各頂点と今引いた線で構成される、真ん中の三角形を除いた3個の三角形を考える。
dp[a][b] = dp[a-1][b] + dp[a][b-1]
の漸化式でカウントできる。(ある直線が引かれる1個前の組み合わせは二通りしかないため。)また、dp[a][1] = dp[1][b] = 1である(1点から残りのすべての辺に線が引かれる。
三角形ができないパターン
一つの辺から残り2この辺への直線のみで構成される。このパターンはdp[a + b + 1][c] などで計算できる。
Yukicoder No.519 アイドルユニット
n (2の倍数, 24以下) 人のアイドルでn/2組のペアを作る。それぞれのペアの相性がn*n行列で与えられるとき、ペアの相性の和の最大値を求めよ。
nが小さいのでペア成立済みのアイドルを状態にしたbitDPでメモリとしては十分。問題は計算量である。制限時間が1秒と短いので、漸化式の遷移をよく考える必要がある。m組のペアができている状況で、n - 2m人の中からペアを作る組み合わせは(n-2m)C2とおりであるが、これをすべて試していたら定数倍が大きくTLEする可能性が高い。
そこでよく考えると、現在の状態が例えば 00011110101 (1は既にペア成立済みのアイドル)の時、一人目は2番目のbitであると決め打ちしてしまってもよい。(bitDPの遷移順としては、bitが小さい方から配っていく感じのdpになる) つまり00011110111 からもう一人選ぶ見合わせだけ選べば良い。これで(n-2m-1)通りだけ調べれば良くなる。
また、状態として立っているbitの数が偶数個のときだけ遷移が発生する。これは次のように考える。まずdp[0]は0とし、それ以外は負の数を入れておく。そしてこっからbitを2個立てた時の配るdpを行うと、遷移先のは0以上の整数になっており、遷移先は必ず偶数個のbitが立っている。その為、dp[state]が負の時はスキップしてしまえばよい。
(ここで素直にbitcountすると定数倍でTLEする可能性が高い) 計算量は O(2^n) であるが、nが24まであるので、約1600万回のループになりC++以外の言語では定数倍をガチガチに最適化する必要がある。
AGC015 C - Nuske vs Phantom Thnook
N * M のグリッドに0または1が書いてあり、1をノード、1が隣同士になっているときにはエッジが張ってあるとみなすと、1の集合はTreeになる。領域(x[1,i],y[1,i], x[2, i], y[2,i])がQ個与えられるので、その領域でTreeの部分集合をとった時、領域内の連結成分の数を答えよ。
Treeの部分集合は一般に森(複数の木)になる。木は一般に「頂点数 - エッジ数 = 1」を満たすため、領域内の「頂点数 - エッジ数」がそのまま連結成分の数になる。エッジ数は各点ごとに上下左右を見ておき、その累積和を作っておく。また、領域の途中で切れた分を除くために、縦方向及び横方向での累積和も作っておく。また、頂点数は単に1の数で累積和を作っておく。すると領域が指定された時の「頂点数 - エッジ数」はO(1)で計算可能。全体ではO(N M)。
AGC015 B - Evilator
各階に上または下のボタンしかないエレベーターがある。最上階は下、1階は上であるときに、i階からj階に移動する全組み合わせについて移動の最低回数の合計値を求めよ。
移動の最低回数は多くても2回。なので、すべての組み合わせ N * (N - 1) に2回の移動が必要な組み合わせの数を足せばよい。移動に2回必要な移動というのはi階において上ボタンしかない場合は1～i-1階まで、下ボタンしかない場合はi+1～N階までであり、各階が上か下かによって、i-1 または N-i を足していけばよい。O(N)。
