APRIL18B VAIMIN : April Challenge 2018 Division 2 - Vaibhav and Ministers

問題リンク
https://www.codechef.com/APRIL18B/problems/VAIMIN

概要

組合せをO(1) で求められるように前計算をし、
障害点を考慮しながらゴールまでたどり着く経路の総数を求めます。
for 文DPで書き、 O( (p + q) log MOD + M^2 )

考察

経路について

reputation がcを下回らないように、(p, q) に移動したい、
ということを図にして表すと、「カタラン数」で出てくるような
経路の数え上げ問題になっていることが分かります。

サンプル1 の場合、
f:id:arukuka:20180418233959p:plain

c は無駄の要素なので、与えられる p, q
から cを引いておきます。
その場合のコーナーケースとして、
c だけ good deals している間にVaibhav が提示している
点が通過点にないかチェックする必要があります。

経路は(0, 0) から (p', q) where p' := p - c
までを計算しますが途中M個の障害点を考慮してなければなりません。
包除原理を考える必要がありますが、ある点から次のある点までの
経路数が常に同じであるため、再利用できます。
これで、スタート位置からゴールまでにの経路数の
「奇数個点を通過してゴールについた経路数」 - 「偶数個点を通過してゴールについた経路数」
を計算すれば答えになります(スタートは偶数:0個とする)。
点はあらかじめ何回行動したか(g + b)でソートしてあげます。
同じ座標上に2点存在する場合もありますがそれを経由しようとすると
組合せは0になるため、特に考える必要はありません。

ある点Xから(右側の)ある点Y に移動する総数は

f:id:arukuka:20180418235907p:plain

このように、負のreptationを許す経路数から
「反射」の考えでその余分な分を引くことで求められます。
(自分も完璧に理解できていませんが、詳しくは下記書籍を読んでください。
自分はこれのおかげでなんとかACまで持って来れました。

note7.hyuki.net


以上を踏まえて実装すると

Solution: 18236218 | CodeChef

となります。