https://www.hackerrank.com/contests/hourrank-19/challenges
問題から
Recover the Arrays
N個の配列が与えられる。
これを先頭から「e a[0] a[1] ... a[e-1]」のルールで改行する。
何行になるか。
What Are the Odds?
N個の石の山に対してNimをする。
ゲームの前にAliceは[b,e]の範囲の石を全て取り去り、Bobが先手でNimが始まる。
AliceがNimで勝てる[b,e]の範囲は何通り？
Maximal Tree Diameter
N頂点の木がある。
以下の操作を1回だけ行うことで木の直径を最大化する。
- 辺を1つだけ削除
- 辺を1つだけ再び木に戻るよう追加
直径の最大値は？
※ 木の直径 : 木の中の最長距離
以下、解説
Recover the Arrays
https://www.hackerrank.com/contests/hourrank-19/challenges/recover-the-array/submissions/code/1301193675
先頭から順に見ていくだけ。
実装するだけの問題。
What Are the Odds?
https://www.hackerrank.com/contests/hourrank-19/challenges/what-are-the-odds/submissions/code/1301193745
Nimでの勝敗判定を知らないと解けない。
hamayanhamayan.hatenablog.jp
部分点解法
[b,e]の区間を全て試して残った山に対してxorをとり、Aliceが勝つものをカウントする。
満点解法
部分点解法を改良していくのだが、eの部分だけ全探索する。
[0,e]～[e,e]の中でAliceが勝てる場合が何通りあるかを高速に数え上げていく。
これは、[e+1,N-1]のxorと同じxorが[0,0]～[0,e-1]に何個あるかと同じである。
その為、累積和のような感じでcnt[i] := [0,0]～[0,e-1]の範囲でxorがiとなる個数を更新しながら求めていく。
配列Lと配列Rを事前に計算(pre関数)しておき、それを役立てて計算していくと間に合う。
Maximal Tree Diameter
部分点解法
削除する辺を全探索して、削除後の2つの木について直径を求める。
すると作れる最大の直径は二つの直径の和+1となるため、この最大を取る。
満点解法
全方位木DP的なことをやる（多分）。
