Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-27SRM471 Div1

途中から全くコンパイルができなくなり、ノーゲームになりました。

SRM471 Div1 250 PrimeSequences

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

素数を2で割って余りを切り捨てると、また素数になるような数を考えます。さらにその素数を2で割って余りを捨て、ということを素数でなくなるまで続けます。このようにして生成される素数の列について、N以下の数でD個以上の素数を生成できる最大の数を求める問題です。

2<=N<=10000000、1<=D<=10


最初Nが100万に見えて、エラトステネスの篩で楽勝だなと思ったのですが、よく見ると1000万だったので、TLEするなあ、やはりそんな簡単なワケないか・・と考えました。(←間違い、というか記憶違い・・・そんな簡単でした)

難しいなあと思っていたら、みんなぽんぽん提出しているので、何か簡単に解く方法を見落としているに違いないと思い・・・

色々試してみると、Dが最大10となっているけど、N以下で1桁でない数のうち、

  • 1の位が偶数か5の場合は素数ではなく、
  • 1,3,7の場合は5回以下で循環するため、

1の位が9でない限りDは最大5になるようでした。

この分だと9のときでもDが6以上になる場合はほとんどなさそうだなと思い、定義通りに実装したプログラムでローカルで走らせてみると、予想通り6のときはほとんど解がなく、7以上で答えなしとなりました。

解の算出に時間がかかるのはD>=5の場合だけなので、この場合だけ埋め込みをしてしまえば2秒以内は余裕そうです。という感じで頑張って書いてコンパイルしようとしたあたりでサーバー様がお亡くなりになりました。

本番で提出できなかったのは残念ですが、いずれにせよすでに50分ほど経過しており、ひどい成績になってしまったのである意味ラッキーでした。

ソースは下のほうに載せます(解1)。


本番が終わってから、埋め込みなどしなくても解けるもっと効率的な方法に気づきました。

定義では素数を2で割っていきますが、生成する素数の列を逆方向に作ることもできます。その場合、2をかけて1を足すことを繰り返すことになります。

そうすると、Nが1000万、Dが10のときでも、解の候補は1000万/(2^10)で1万くらいになるので、だいぶ計算が余裕になります(解2)。


さらに今日みなさんのブログを見ると、普通に篩で解けたようで・・・。何か、一度はまると抜け出せないですね。。篩で間に合うということはまさかないだろうと思い込んでしまってました。篩で解いたソースも書いたので載せておきます(解3)。

続きを読む

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

2010-05-22Google Code Jam 2010 Round 1A

Google Code Jam 2010 Round 1A C Number Game

| 21:50 | Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) のブックマークコメント

Problem Statement

各問題のポイントを見て、BとCがポイントが小さかったのでCから取り掛かりました。

少し考えて、Nimの一種だということはすぐに分かりました。この種のゲームでは、先にkの値を複数から選択できるほうがゲームの主導権を握り、100%勝つことになります。

A>Bの場合について考えます。(B>Aの場合は、AとBを反転させれば良い。A==Bは必ず先手が負けるので、考慮する必要がない)

A/2>=Bのとき、最初から取りうるkの値が2種類以上となり、先手が勝ちます。また、(2/3)A<=Bのとき、1ターン目で後手が必ず取りうるk>=2となり、後手が勝ちます。では、(2/3)A>B>A/2のとき、どうなるでしょうか。。。

ここらまで考えて、30分くらい経ちました。ポイント的には簡単な問題のはずなのに随分時間がかかってしまっているなと思い、スコアボードを見ると、small/largeがそれぞれ5点/10点だったはずの問題Cが、16点/25点に変わってます。え・・・。Googleさん・・・。一番難しい問題を最初に解いてた・・・・・・。

ここまで来て別の問題に行くと忘れてしまいそうなので、このまま突き進むことにしました。

話を戻すと、今までは1ターン目でどちらかが主導権を握れるパターンしか考えていませんでした。では、誰も主導権を握れないままに終わるパターンはどのようなパターンかと考えると、、、

(B,A)=(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),・・・

つまり、AとBがa_(n+2)=a_(n+1)+a_nの数列の隣同士となるときに、最後までどちらも主導権を握れないパターンになります。これは、明らかにフィボナッチ数列です。

しかし、これが分かったから何なんでしょう。もう少し色々試してみました。いくつかのフィボナッチ数列のペアを使って、Aの値を固定したままBの値を少しずつ増やしたり、減らしたりしてゲームをシミュレーションしてみます。すると、Bの値を増やせば増やすほど、後手が早いターンで主導権を握れるようになります。また、逆にBの値を減らせば減らすほど、先手が早いターンで主導権を握れるようになることが見えてきました。

これ以上厳密な証明はしませんでしたが、フィボナッチ数列の隣同士の値の比率を計算してみると、約0.618になるので(黄金比になるんですね)、B=0.618Aくらいに先手が勝つか、後手が勝つかの境界があるらしきことは間違いなさそうです。

あとは、マシンパワーで何とでもなるレベルです。1~1000000までの全てのAに対して、先手が勝つBの最大値を求めます。仮に最大値をA*0.618とおいてシミュレーションし、先手が勝てば最大値を増やして先手が負けるまでシミュレーションします。最大値がA*0.618のときに後手が勝てば、先手が勝つまで最大値を減らしていきます。

全てのAに対し先手が勝つBの最大値が分かれば、あとは全ての取りうるAに対して先手が勝つパターン数を合計するだけです。

結局、提出まで1時間半もかかってしまいました。Small、Largeともに通ったので、良かったです。。

以下、ソースです。(少し体裁を手直ししてます)

続きを読む

Google Code Jam 2010 Round 1A A Rotate

| 21:50 | Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) Google Code Jam 2010 Round 1A A Rotate - SRM diary(Sigmar) のブックマークコメント

Problem Statement

Cが終わったので最も簡単と思われるAを解きました。見た感じ、シミュレーションするだけのようなので、何も考えずシミュレーションしました。90度回転後の片寄せのところでバグが出て、おかしな答えが出ていたので修正に30分くらい費やしてしまいました。

さらに、サンプルは答えが合ったのですが、smallでWA。GCJでWAすると、どのケースで間違ったのか分からないため非常に解析に苦労します。手動で答えを数ケース計算して、間違ってるところがすぐに見つかったので良かったですが・・・。結局if文の条件中で括弧付け忘れがあり、計算の優先順位が間違って適用されていたことが原因でした。こういうのに気付かず書いてしまうと、致命的なのに発見しづらいので何とかならないでしょうか・・・。

バグ取りやら何やらで結局40分くらいかかってしまいました。さらに、Largeの解を提出しようとしたらブラウザがフリーズ・・・。なんとか8分以内に復旧したので何とかなりましたが、今日はどうもついていないです。

Aを出し終えた頃には残り10分だったので、Bはとりかかりませんでした。見た感じBはDPぽいですね。解説にもDPと書いてありました。

何とかAもSmall、Large両方通せたので、最終的には64点で305位、Round1は通過しました。次は、かなり厳しくなりそうです。。。

以下、Aのソースです。Inputファイルの解析は省略です。solve関数が本体です。

続きを読む

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

2010-05-21SRM470 Div1

SRM470 Div1 250 DoorsGame

| 21:58 | SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) SRM470 Div1 250 DoorsGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

こういうのをゲーム木というんですね。以前も同じような問題が出たような気がします。250にしては複雑だなと思いつつもそのまんま実装してしまいましたので30分以上もかかってしまいました。250らしくGreedyに解けたようですね。。

チャレンジタイムはTLEの人がいましたので50点いただきました。

特に問題なくシステムテストはパスしました。

source

SRM470 Div1 500 DrawingLines

| 21:58 | SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) SRM470 Div1 500 DrawingLines - SRM diary(Sigmar) のブックマークコメント

Problem Statement

DPかなと思いつつ最後まで方針が分かりませんでした。

ゆる系エンジニアさんによると、上辺のみに着目して全ての2点のペアが交わる期待値を独立に計算し合計すれば答えが出るとのこと。E(X+Y)=E(X)+E(Y)ですね。5000万回の足し算なので、計算時間も問題なしです。DPじゃないし・・・

一般的で、ひねった複雑なやり方ではないのに、なぜかその切り口に至らない辺りに自分の視野の狭さを感じます。。。

こちらの問題もチャレンジでTLEの人がいたので50点いただきました。

以下、コンテスト後に書いたコードです。

続きを読む

MarkMark2013/02/17 00:33That's way more cvleer than I was expecting. Thanks!

kqqrytedphbkqqrytedphb2013/02/18 06:35xPNt08 , [url=http://gjdzistspmta.com/]gjdzistspmta[/url], [link=http://lbucohbaehdl.com/]lbucohbaehdl[/link], http://jpslatqfcovk.com/

pwzcytpwzcyt2013/02/19 19:43inRfr9 , [url=http://uoklvogqeeon.com/]uoklvogqeeon[/url], [link=http://dcqqpgtkbqzr.com/]dcqqpgtkbqzr[/link], http://cvifolqjcbmx.com/

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

2010-05-16TCO2010 Qual2

とりあえず予選は通過しましたが、まだまだ課題が多いです。。

TCO2010 Qual2 250 JingleRingle

| 23:25 | TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) TCO2010 Qual2 250 JingleRingle - SRM diary(Sigmar) のブックマークコメント

Problem Statement

1jingle買うと1jingle売ることができるようになる。最も少ないringleで1jingle購入し、最も多いringleで1jingleを売却することでGreedyに儲けを最大限にできる。儲けが出なくなるまでこれを繰り返す。

特に引っ掛けもないのでsubmit。passed。

source

TCO2010 Qual2 500 FuzzyLife

| 23:25 | TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) TCO2010 Qual2 500 FuzzyLife - SRM diary(Sigmar) のブックマークコメント

Problem Statement

ライフゲーム(Wikipedia)という有名なゲームがあるらしい。これをシミュレーションする。

どうにも実装に時間がかかってしまいます。練習が必要ですね。。。

結果はpassed。

何かプログラムがおかしい人が2人撃墜できて100点もらえました。ラッキーでした。

source

TCO2010 Qual2 1000 HandlesSpelling

| 23:25 | TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) TCO2010 Qual2 1000 HandlesSpelling - SRM diary(Sigmar) のブックマークコメント

Problem Statement

ある長さまでの最大スコアをDPしていくのかと思って一生懸命コーディングしていましたがそれでは正しい答えが出ないということが分かり、本番終了しました。

実は最大スコアではなく、ある位置からある位置までの最大カバー文字数(≒最小非カバー文字数)をDPしてやれば答えが出たようです。

もう少し色々な角度から解法を考えることができなければ、やはりダメですね。少し一方向に進みすぎる傾向があるので、視野を広げる訓練が必要そうです。。。

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

2010-05-09Google Code Jam 2010 Qual Round

Google Code Jam 2010 Qual Round A Snapper Chain

| 14:36 | Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) Google Code Jam 2010 Qual Round A Snapper Chain - SRM diary(Sigmar) のブックマークコメント

Problem Statement

Snap数が最大1億回なので何となくシミュレーションでも解けそうですが、問題数が1万あるので厳しいかも?と思いました。ちょっと考えたらシミュレーションする必要は全くありませんでした。

1回Snapすると1個目がON、2回Snapすると2個目がONし1個目がOFF、・・・(以下同様)。ということは、n個目までが全部ON時にSnapするとn+1個目がONとなりn個目までは全てOFFとなるため、漸化式にすると、n個目まで全てONになるSnap数*2+1がn+1個目まで全てONになるSnap数となる。漸化式を解くと、n個目まで全てがONになる最初の数は、2^n-1となる。連結がn個だと、2^nで最初の状態に戻るので、mod 2^nで2^n-1となるとき答えはON、それ以外のとき答えはOFFとなる。

以下、ソースです。Inputファイルの解析は省略します。

続きを読む

Google Code Jam 2010 Qual Round B Fair Warning

| 14:36 | Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) Google Code Jam 2010 Qual Round B Fair Warning - SRM diary(Sigmar) のブックマークコメント

Problem Statement

64bitに入りきらない数が出てくるので、多倍長整数の扱いが必要です。私はJavaとか使えないので、今後Topcoderとかでも使うかもしれないと思いC++で多倍長四則演算の関数を作ってみましたが、例外処理などが多くて大変なので、疲れました。しかも途中Leading Zeroの処理ミスで1WAしてしまいました。とりあえず今回の問題で使うには十分なものができましたが、汎用的に使えるようにするにはかなり大変なので、少なくともCode Jamでは今後多倍長演算が必要な場合は既存のライブラリを使おうかなと思います。

肝心の問題そのものは、最大公約数を求めるだけの問題で、一旦Sortして隣同士の差をとってから、全ての最大公約数を求めてやれば良いです。解は、最大公約数から(最小の値 mod 最大公約数)を引くことで求まります。

提出版は自作ライブラリですが、以下は今後のためにNTLを使って書き直したソースです。ZZが多倍長整数の型です。(それにしても、NTLを使うとGCD関数なんかも用意されてるし、随分楽でした・・・あたりまえか・・)

続きを読む

Google Code Jam 2010 Qual Round C Theme Park

| 14:36 | Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) Google Code Jam 2010 Qual Round C Theme Park - SRM diary(Sigmar) のブックマークコメント

Problem Statement

高々1000グループしかいないので、1001回ジェットコースターを動かせば、必ずどこかでループします。ということで、1001回繰り返しシミュレーションして、先頭グループが同じものが2回来た時点でシミュレーションを終了します。あとはループの開始位置と終了位置に気をつけて、1ループの長さと稼ぎから全体の稼ぎを求めます。

配列のインデックスを書き間違えるという凡ミスで1WA、提出する結果ファイルを間違えるという更につまらないミスで1WAといけてないことをしてしましました。Topcoderだったら0点ですね。。今後気をつけようと思います。

以下、ソースです。

続きを読む

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

2010-05-05SRM469 Div1

Topcoder Openに参加しようと思ったら、Webページで24時間前までにRegistが必要だそうで、参加できませんでした。

TCOのページをよく見ると確かに右上にRegisterという三角のボタンが・・・

正直、こんな位置にあるのは予想外です。RulesのRegistrationのところ(事前にRegistが必要と書いた注意書きのところ)にリンクを貼っておいてくれれば良いのに・・・。

しょうがないので、次回のQual Round2に参加しようと思います。

SRM469 Div1 250 TheMoviesLevelOneDivOne

| 12:29 | SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) SRM469 Div1 250 TheMoviesLevelOneDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

やるだけの問題です。予約済みの席がある列だけ数え上げをして、それ以外の列は(席数-1)×列数で計算すれば答えが出ます。

どうも書くのが遅くてバグ多いしでダメダメでした。もっと綺麗なコードで早く書けるようになりたいです。

結果はpassed system testです。

source

SRM469 Div1 500 TheMoviesLevelTwoDivOne

| 12:29 | SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) SRM469 Div1 500 TheMoviesLevelTwoDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

いかにもDPな感じの問題です。

見終えた映画の集合を状態として、起きたまま見れた映画の最大数を記憶するんだろうなという感じで進めましたが、問題で求められているのが、最大数ではなく見る順番なので、順番をどうやって記憶するかで引っかかってしまいました。

とりあえずvectorで見た順番を全部記憶してみると、MLEかつTLEにもなってしまうので、ダメです。いろいろ考えましたが結局時間内には分からず。

チャレンジタイムではvectorでDPしてる人が2人いたので何となくこの人たちはダメそうだなと思い突撃してみたところ1成功1失敗で+25になりました。

後で分かったのですが、順番については全て記憶する必要はなく、ある状態から次にどの映画を観ると見れる映画数が最大になるかだけを記憶しておけば、あとで最適な順番が計算できるので、vectorを使う必要はありませんでした。

分かってしまえば何てことはないですが、こういうちょっとしたブレイクスルーがDPの勘所というか、難しいところなんでしょうね・・・簡単なようで意外と分からないものです。

以下、終了後に書いたコードです。映画20本でも状態数2^20×平均更新数10=約1000万ループの計算量で、700msくらいで終わるのですが、このコードを最初書いたときは再帰関数recにlengthとscaryのvectorを引数で渡していたところ、TLEしてしまいました。これまたTLEする原因が分からず、修正に苦労しました。。引数にvectorを渡すと、vectorのコピーやらで時間がかかるのかな?引数でvectorを渡すのは注意が必要なようですね。。。

続きを読む

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