FHC#R1感想
前置き
Facebook Hacker Cup Round1お疲れさまでした。
私はABC3完でしたので、それぞれの感想とかを書いていきます。
A問題
（記法：考察→実装の流れ）
証明は面倒なのでしませんが、正しい配管配置は凄く限られます。
1.左端の列と右端の列は、必ず問題文の図の左端,右端にあるような配管しか出来ません。
2.0-indexedとして、2*i+1列目と2*i+2列目(0<=i<N/2)は、必ず問題文の図の1,2列目のように上に凸、もしくは下に凸の配管しかできません。
3.2より、Nが奇数のとき、絶対に配管が不可能なことが分かります。
考察は、以上のような流れで行けます。
実装は、まず3番より if (N%2==1)return 0;
1番より、if (左端の列と右端の列のうち必要な場所が埋まってる) return 0;
2番より、求める場合の数を初期値1にしたうえで、
上に凸が出来れば1倍,下に凸が出来れば1倍,両方できるなら2倍になります。
雑に言うとこういう流れの実装をすると通ります。
B問題
（記法：実装ベースの考察）
AIZUの階段本ありますか？
そこに、木を先行順巡回,後攻順巡回する関数の実装例があります。
これで先に、巡回順番を配列データに起こしましょう。
次に、2つの配列データをデバッガなどで見ながら考えてみましょう。
それぞれをA[i],B[i] (0<=i<N)とします。
この時、A[i] == B[i] となるようなラベル割り当てが、問題文での要求です。
そこで、UnionFindを導入しましょう。
A[i]==B[i]なのであれば、併合して同じグループにしてしまうのです。
それを繰り返せば、同じ数字にならなくてはならない頂点同士は、同じグループに居ます。
後は、グループがK個以上であれば、それぞれに1~Kのいずれかを割り当てればOKです。(1~Kはそれぞれ1回以上使うことは忘れずに)
C問題
（よく分からん）
全体の実装順は、前計算O(N*M)→二分探索O(log(Z))→範囲縮小O(N)です。
では順番に見ていきましょう。
前計算
・とりあえずHの値は漸化式として与えられています。それを展開しましょう。
・パルクールをする方に関しては、担当区間と高さの差の上限下限だけ与えられてます。
そこで、配列limUp(size:N),limDown(size:N)を定義しましょう。
limUp[i] := 地点iから見て、i+1がどれだけ上にあってもパルクール出来るか。
limDown[i] := 地点iから見て、i+1がどれだけ下にあってもパルクール出来るか。
A<B or A>Bで少しだけ混乱しますが気を付けましょう。
範囲縮小
前置き
先にこっちの方を考えてみましょう。
先程の前計算結果をどのようにしたら活用できるのかを考えます。
先程の前計算で分かったことは、
・H[i]の値
・H[i+1]の取りうる値の範囲(H[i]基準で)
です。
小さな具体例
さて一度、答えを0secと仮定して全体を見渡してみましょう。
H[0]に着目すると、limUp[0],limDown[0]を元に、H[1]の取りうるべき値の範囲が分かりますね。その範囲の中にあれば、全てのパルクール演者はH[0],H[1]間のパルクールが成功します。
これを一般化して、H[i]に着目すれば、limUp[i],limDown[i]を元にH[i+1]への（からの）パルクールが成功するかどうかが判定できます。全てのiで成功すれば、答えが0secでもパルクールが成功します。
一般化
さて問題は、0secじゃない場合にはどうなるのか？
これは恐らく、図を書いてみると解きやすいと思います。
まず初めに、答えが t secであると仮定します。
区間 0-1における、0の方が取るべき高さの区間
次にH[0]から見たH[0]が最終的に取りうるべき高さを考えます。
(これは換言すると、t secという条件下に置いて、更にH[0]がその時間内に動ける範囲をH[0]自身を用いて定義しているフェーズです。)
これは(H[0] - t) ～ (H[0] + t)－① の区間です。その範囲であれば、t sec以内に高さが調節できます。
区間0-1における、1の方が取るべき高さの区間
そしてH[0]から見たH[1]が最終的に取りうるべき高さを考えます。
（これは換言すると、t secという条件下に置いて、更にH[0],H[1] 間の高さの差分の条件を満たすH[1]の高さの範囲を、H[0]を用いて定義しているフェーズです。）
H[0]は先程の結果より、 (H[0] - t) ～ (H[0] + t) の区間で自由に高さを決定できます（ただし下限は0です）。その上でlimUp[0],limDown[0]の情報も付け加えると、結果としてH[1]が最終的に取るべき高さは、(H[0] - t - limDown[0]) ～(H[0] + t + limUp[0])ー② の区間になります。それ以外の高さをH[1]が最終的に取ると、どう頑張ってもパルクール演者の誰かは失敗します。
さて後は、これを区間1-2以降も繰り返していくだけです。
（ただし次の場合は、①と②の重複部分が、H[1]の取るべき高さの区間になります）（ここ上手く文字にしにくい）
これを、H[i] , H[i+1]それぞれに対して順番にやっていきます。
最終的に可能な区間が残っていれば、、t sec以内にパルクールの準備が可能です。
二分探索
さて、所要時間を固定すれば、パルクール成功判定は出来ます。そこで所要時間で二分探索します。
こういう感じでやっていけば、何とか解けます。
感想
C問題の考え方を文字に起こすのめっちゃ難しいし、野生のプロの文章読みながら書き方習います。
ともかく、Round2に進出出来て良かったです。
Round2が午前2~5時にあること、その12時間後くらいに予定があることはヤバいですが、多分大丈夫だと信じて、Tシャツを狙っていきます。
（確かTシャツは上位500人でしたよね？）
Round3は、運が良ければ行きたいなぁ・・・
以上、Round2進出を確認してから1時間で書き上げてみました。
