HackerRank Week of Code 21
https://www.hackerrank.com/contests/w21/challenges
Kangaroo
最初、移動が連続的だと思ってたので v1>v2 なら追いつく、と考えたがよく読むと離散的だった。
毎秒 v1-v2 ずつ距離が縮まるので、x2-x1 が v1-v2 の倍数だったら追いつく。もちろん v1≦v2 のときは追いつかない。
Luck Balance
unimportant なコンテストは全部負ければよくて、important なコンテストは luck ができるだけ大きいもの K 個を負ければいい。
Lazy Sorting
最初からソートされている場合が気になったが、擬似コードを見る限りだと 0 回で良さそうである。
最初からソートされていなかったら良くある「あたりを引くまでに掛かる回数の期待値」を計算すればいい。あたりが出る確率が p なら、あたりが出るまでに平均 1/p 回引くことになる。
ランダムシャッフル後にソート済みになる確率を計算して、その逆数を取ってみると $(a[1]+a[2]+\cdots+a[100])!/(a[1]!a[2]!\cdots a[100]!)$ という多項係数の形になっている。 つまり整数になるので long long で計算できる。小数点はハッタリで全部 0。ちなみにこのソートはボゴソートと呼ばれている。
Demanding Money
最大独立集合問題。問題の特性上、全探索してもほとんどのケースでは時間がかからない。簡単な高速化としては、次数 1 の頂点の取捨選択を後回しにするという方法がある。こうすると大抵は勝手に次数 0 になってくれるので探索を省略できる。かならず消えるというわけではなく、2 点だけが繋がってる形で残ることがあるので注意。あとは C[i]=0 のときの処理を忘れないように。
下のスライドを見る限りだと上手く実装すれば O(1.466n) になるらしい。
別の方に注意が行き過ぎてて、パターン数を int に入れてしまうというミスをやらかしてしまった。
The Letter N
- cnt[i][j] := ベクトル PiPj から反時計周り 90 °以下の領域にある点の個数
としておくと、cnt[i][j]*cnt[j][i] の総和が求める値になる。cnt[i][j] は偏角ソートとしゃくとり法を組み合わせれば計算できる。
Counting the Ways
yukicoder の貯金箱の焦りと同様の手段が使える。
a[i] を複数回使えるというのが扱いづらいので、a[i],2a[i],4a[i],...,260 a[i] をそれぞれ 1 回ずつ使える問題に変換する。そして 2 進数桁 DP を行う。
- dp[ pos ][ borrow ] = num
下 0 桁目に影響するのは a[0],a[1],...,a[n-1] だけなので、これらだけ使って dp を更新する。その後、次の桁に borrow を流す。
下 1 桁目に影響するのは 2a[0],2a[1],...,2a[n-1] だけなので、これらだけ使って dp を更新する。その後、次の桁に borrow を流す。
これを繰り返し、最終的に borrow=0 となるものが答えになる。
borrow は a[i] の総和を S としたとき、S+S/2+S/4+S/8+...≦2S まで大きくなるので、200000 程度の dp テーブルを持つ（積が 100000 なので、総和の最大値は 100000 だよね）。
Nのやつをミスったのは仕方ないにしても、最大独立集合の問題のミスはダメ。もう少しで 10 位内だっただけに惜しいことをした。
