pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

HackerRank Week of Code 21

https://www.hackerrank.com/contests/w21/challenges

Kangaroo

最初、移動が連続的だと思ってたので v1>v2 なら追いつく、と考えたがよく読むと離散的だった。

毎秒 v1-v2 ずつ距離が縮まるので、x2-x1 が v1-v2 の倍数だったら追いつく。もちろん v1≦v2 のときは追いつかない。

gist.github.com

Luck Balance

unimportant なコンテストは全部負ければよくて、important なコンテストは luck ができるだけ大きいもの K 個を負ければいい。

gist.github.com

Lazy Sorting

最初からソートされている場合が気になったが、擬似コードを見る限りだと 0 回で良さそうである。

最初からソートされていなかったら良くある「あたりを引くまでに掛かる回数の期待値」を計算すればいい。あたりが出る確率が p なら、あたりが出るまでに平均 1/p 回引くことになる。

ランダムシャッフル後にソート済みになる確率を計算して、その逆数を取ってみると $(a[1]+a[2]+\cdots+a[100])!/(a[1]!a[2]!\cdots a[100]!)$ という多項係数の形になっている。 つまり整数になるので long long で計算できる。小数点はハッタリで全部 0。ちなみにこのソートはボゴソートと呼ばれている。

gist.github.com

Demanding Money

最大独立集合問題。問題の特性上、全探索してもほとんどのケースでは時間がかからない。簡単な高速化としては、次数 1 の頂点の取捨選択を後回しにするという方法がある。こうすると大抵は勝手に次数 0 になってくれるので探索を省略できる。かならず消えるというわけではなく、2 点だけが繋がってる形で残ることがあるので注意。あとは C[i]=0 のときの処理を忘れないように。

下のスライドを見る限りだと上手く実装すれば O(1.466n) になるらしい。

指数時間アルゴリズム入門

別の方に注意が行き過ぎてて、パターン数を int に入れてしまうというミスをやらかしてしまった。

gist.github.com

The Letter N

  • cnt[i][j] := ベクトル PiPj から反時計周り 90 °以下の領域にある点の個数

としておくと、cnt[i][j]*cnt[j][i] の総和が求める値になる。cnt[i][j] は偏角ソートとしゃくとり法を組み合わせれば計算できる。

gist.github.com

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 だよね)。

gist.github.com

Nのやつをミスったのは仕方ないにしても、最大独立集合の問題のミスはダメ。もう少しで 10 位内だっただけに惜しいことをした。