Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-04-20SRM468 Div1

SRM468 Div1 250 T9

| 23:47 | SRM468 Div1 250 T9 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM468 Div1 250 T9 - SRM diary(Sigmar) SRM468 Div1 250 T9 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

非常に問題文が長く、読むだけで10分以上かかりました。

アルゴリズムとして難しいところはないので、実装するだけです。

特にひっかけなどもなさそうなので、submit。

システムテストも問題なく通りました。

何人か落ちてる人がいましたが、あまり落ちるような要素は見つけられていなかったので、チャレンジはしていません。

source

SRM468 Div1 500 RoadOrFlightHard

| 23:47 | SRM468 Div1 500 RoadOrFlightHard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM468 Div1 500 RoadOrFlightHard - SRM diary(Sigmar) SRM468 Div1 500 RoadOrFlightHard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

読んだ感じ、一瞬グラフかなと思いましたが、逆戻りするエッジがないので、DPで解けそうだなという印象を受けました。

しかし、街iまでフライトj回で到達できる最小時間を記録するDPをすると、40万*40で1600万のlong longのメモリが必要です。SRMで使えるメモリは64MBなので、long longに換算すると800万個程度までしか変数を使えません。このようにメモリ容量をオーバーする場合、コンパイルエラーにはならず、実行時にSIGKILLとかいうエラーが返るので、TLE狙いと同様チャレンジに使えます。

ということで、20分くらいダイクストラとか状態の持ち方を変えるとか色々考えてましたが、どれも計算量・メモリ量ともに大きすぎて、いい方法が思いつきません。

しかし、最初から気になっていたのですが、街iから街i+jにフライトする時間が、街iから街i+1へのフライト時間+・・・+街i+j-1から街i+jへのフライト時間となっており、最初に考えたようにDPした場合にこの条件を全然活かせないので、無駄があるのではないかと考えていました。

よく考えると、街iから街jへの経路は考える必要はないのでは・・?街iへの到達が歩いてきたかフライトしてきたかさえ記憶すれば、街i+1へフライトする際に、フライト回数を増やす必要があるかどうかは常に判定可能じゃないですか!!ということは、40万の街の状態をすべて覚えておく必要はなく、直前の街に到達したときの最小時間さえ覚えておけばよいことになるので、必要なメモリ量は2*40*2=160程度しかありません。

ということに気づいたときには、既に残り15分でした。ぎりぎり間に合うかと頑張りましたが、コンパイルエラーやら何やらで結局間に合わず。。。今回初めて知りましたが、大きな配列を宣言するときに、初期化するとエラーになることがあるんですね(こんな感じ→int rt[400010]={0})。"Your compiled binary exceeds the current system limit of 1000000 bytes"という不親切なエラーメッセージで全然原因が分からなくて非常に疲れました。宣言時に初期化するとバイナリコードにデータが埋め込まれるということなのかな。よくわかりませんが。

チャレンジタイムでは明らかにメモリ容量オーバーのコードを書いている人がいたので、ありがたく50点頂戴しました。

以下、本番終了後にバグを取った500点問題のsourceです。

続きを読む

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

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

2010-04-04SRM466 Div1

Match Editorialsという素晴らしい解説があるのと、ライティングが間に合わないので、あまり詳細な解法を書くのはやめようかなと思ってます。
というわけで、SRM466の参加記録です。

SRM466 Div1 250 LotteryCheating

| 22:49 | SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) SRM466 Div1 250 LotteryCheating - SRM diary(Sigmar) のブックマークコメント

約数の個数が奇数の数を0~10000000000までの間で列挙できれば解けるような問題です。
実は「約数の個数が奇数の数」⇔「平方数」(Wikipedia)ということだそうなのですが、全く気づきませんでした。予備知識としては常識の範囲なんでしょうか?
正直いって、250の問題でその場でこの法則に気づくのは難しい気がします。500点くらいのレベルかと・・・

SRM466 Div1 500 LotteryPyaterochka

| 22:49 | SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) SRM466 Div1 500 LotteryPyaterochka - SRM diary(Sigmar) のブックマークコメント

250の解法が全然思いつかなかったので、こちらを開きました。場合の数を列挙するだけで解けるので、どう考えても250よりこっちのほうが簡単に思えます。。
250と500の内容が入れ替わってるのかと思いました。
source

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