読者です 読者をやめる 読者になる 読者になる

はまやんはまやんはまやん

hamayanhamayan's blog

HourRank 19 問題と解説

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的なことをやる(多分)。