Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-04-16SRM467 Div1

SRM467 Div1 250 LateProfessor

| 00:43 | SRM467 Div1 250 LateProfessor - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM467 Div1 250 LateProfessor - SRM diary(Sigmar) SRM467 Div1 250 LateProfessor - SRM diary(Sigmar) のブックマークコメント

Problem Statement

アルゴリズムとしては難しい部分はないですが、実装が面倒で間違えやすいタイプの問題です。

変数がたくさん出てくるので、頭の中だけで考えているとワケが分からなくなってきます。最初にコンパイルするまで20分くらいかかってしまいました。

テストケースにもあるので気づいたのですが、教授の到着時間がbest==worstのとき、0divideにならないよう、計算方法を変える必要があります。
どうも0divide以外のケースの計算で疲れていたのと、20分もかかってあせっていたので、適当に書いて出してしまいました。
あっさり撃墜されてしまったので、あとで見てみたらワケの分からない条件が書いてあり、反省しきりです。。。
ホントなんでこんなコード書いてしまったんだろう。

source

SRM467 Div1 500 SuperSum

| 00:43 | SRM467 Div1 500 SuperSum - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM467 Div1 500 SuperSum - SRM diary(Sigmar) SRM467 Div1 500 SuperSum - SRM diary(Sigmar) のブックマークコメント

Problem Statement

kとnの2変数を使った漸化式を計算する問題です。
特に片方の変数kが最大50と小さい場合、ベクトルと行列を使えば解けるということで、同じような問題を解いたことがあったので、条件反射的にベクトルの方向で考えてました。

与えられた漸化式をそのまま使うと、
(k,n),(k,n-1),・・・,(k,1)
のベクトルを、
(k-1,n),(k-1,n-1),・・・,(k-1,1)
のベクトルから漸化的に計算できることになります。
そうすると、n行(最大10億行)のベクトルを用意する必要があるので、解けません。

漸化式を変形すると、
(k,n)=(k,n-1)+(k-1,n)
なので、さらに同じ式を(k-1,n)に適用して(k-1,n)を展開していくと
(k,n)=(k,n-1)+(k-1,n-1)+(k-2,n-1)+・・・+(1,n-1)+(0,n)
となります((0,n)=n)。
これで、
(k,n),(k-1,n),・・・,(1,n),n
のベクトルを、
(k,n-1),(k-1,n-1),・・・,(1,n-1),n-1
のベクトルから計算できるようになりました。
あとは、ベクトルを更新するための行列Aを作成して、n=1の初期ベクトルVを作成すれば、解は(A^(n-1))*Vで計算できることになります。
A^(n-1)の計算方法は、いわゆるbinary methodを使えばn-1のビット数*2回(最大60回程度)の乗算で計算できます(Wikipedia)。

コードそのものはすぐ書けましたが、漸化式の変形のところを間違えると台なしなので、検証に15分くらい費やしてしまいました。
さらに、最大ケースの(50,1000000000)を突っ込むと、なぜか答えが0に・・・。
何か間違っているのかと終了間際まで探しましたが間違いは見つからず、しょうがないのでそのままsubmit・・・。

部屋の人のコードを見ると、行列で解いてるの僕だけ・・・。
終わったかな。。と思いましたが、システムテストは通りました。
結局、(n+k)C(k+1)で一発で計算できたようですね。
これだったら、mod 1000000007だから最大ケースを突っ込むと0になるわけだ・・・。

今度から条件反射で行列にせずに、色々考えてみても良いかなと思いました。

source

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100416