https://www.codechef.com/COOK80
問題
Safe Robot
https://www.codechef.com/COOK80/problems/ROBOTG
縦N横Mのマスがある。
ロボットはLRUDから構成された命令に従って移動する。
全ての命令の過程でマス目からはみ出ないロボットの初期マスが存在するか。
すれば"safe"、さもなければ"unsafe"
Rainbow Graph
https://www.codechef.com/COOK80/problems/RAINBOW
N頂点の無向完全グラフがある。
各辺には色（自然数）がついている。
頂点の部分集合で全ての頂点から出ている辺のうち少なくとも色が異なる2辺があるものを"面白い"とする。
面白い頂点の部分集合のうち、頂点数が最大のものは？
Yet Another Card Game
https://www.codechef.com/COOK80/problems/CARDS777
R個の赤カードとB個の青カードがある。
P個の赤コインと(R+B-P)個の青コインがある。
R+B回、以下のクエリを行う
1. コインを1つ選ぶ
2. カードをランダムに1枚選ぶ
3. もし、同じ色ならば1ポイント得点
得点できる点の期待値は？
Increasing Xor Sequence
https://www.codechef.com/COOK80/problems/INCXOR
N個の数列Aがある。
以下のルールを満たすようなN個の数列Bは何通りあるか(mod 10^9+7)。
- 0 <= B[1] <= B[2] <= ... <= B[N] < 2^31
- A[1] xor B[1] <= ... <= A[N] xor B[N]
以下、解説
解説
Safe Robot
https://www.codechef.com/viewsolution/13127530
全ての初期マスに対して全探索をして、はみ出さないマスがあればsafeで1つも無ければunsafe
Rainbow Graph
https://www.codechef.com/viewsolution/13133429
結果が収束するまで異なる2色の辺がつながっていない頂点を消していく処理をする。
収束したら残った頂点を数えて答え。
毎回、1個だけしか消えなくてもO(TN^2)で間に合う。
Yet Another Card Game
https://www.codechef.com/viewsolution/13133957
赤コインr個、青コインb個、カードの総和・コインの総和（どちらも同じ）をN個としておく。
想定解はEditorial見るといいですが、「(R*r + B*b) / N」が答えです。
Editorialの方に数学的帰納法で証明してますが、聞きたいのは証明よりも何故この数式にたどり着いたかなんですけど…（そこが分からんけど、他の人結構解いている）
上の方の自分の解答は赤でポイントをx点取ったとして、このxで全探索して期待値計算をするものです。
赤でxポイント得点、青でyポイント得点する確率は、
Combination(r,x) * Combination(b, R-x) / Combination(N,R)
でこれを掛けて足していくのがNaive解法です。
でも、これだと分母分子の数が大きくなってしまうので、こまめに割っているように変えます。
しかし、これでも毎回確率計算するとTLEするので、xのインクリメントに合わせて確率の差分のみ計算するようにしています。
これで理論上はACできるのですが、C++だと計算精度（主にオーバーフロー）の問題でWAになってしまいます。
PythonあたりでやるとACできるかも。
