Facebook HC 2012 Round 1

NHC

問題は悪くないのに、なんで...、っていうもったいないコンテスト感。

A

目的地に向かってマンハッタン距離で最短になるように移動することを考える。スタート地点からある点を経由してゴールするときの最短距離での移動方法がK通りのとき、最短距離として可能な最小値を答えよ、という問題。


経由する点を考えるのは後にして、距離と移動方法の関係を考える。x軸方向にAマスy軸方向にBマスある場合、A+BからA(またはB)個選ぶ方法だけ移動方法があることが分かる。そこで取り敢えずK以下のすべての数について、A+BからA個選ぶ方法がKになるような最小のA+Bをメモすることにする。パスカルの三角形を思い浮かべれば、最初のうちは全部チェックしないといけないけれど、途中から数個調べれば良くなることが分かるので、このメモ化は十分間に合う。(実際、トータルの持ち時間は6分もあるので、多少ヘマしても大丈夫だし、そもそも入力によらず全部求めておけば問題ない。)


中継地点を考えると、中継地点までがN通りだとすると、そこからゴールまではK/N通りになるので、全部調べても、K^(1/2)通りくらい。それぞれの最小のA+Bは既に求まっているので、合計すれば全体の値になる。ということで、さらにこれらの最小値を答えれば良い。

B

あるマージソートのアルゴリズムについて、途中で行った比較の結果と配列の大きさが与えられるので、ソート前の状態を復元せよ、という問題。


マージソートの各マージステップで行う比較の回数から比較の結果のどの部分が相当するかを計算して、その後で逆向きに処理を適用するという作業を実装すれば良い。


実はソート済みの配列に同じマージソートのアルゴリズムをその比較結果に従って適用すれば、逆向きのマッピングが得られるので、それを元に戻せば終わります、という問題でしたとさ。

C

M以下の正整数をくっつけて作ったN桁の整数が与えられるので、元の整数配列として可能なものは何通りあるか答えよ、という問題。


単純なDPをやるだけですね。