Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-07-29SRM477 Div1

250 AC、500 WAでした。

またもや500をつまらないミスで落としてしまいました。。

500が通っていればかなり良い成績だっただけに非常にもったいないことをしました。

SRM477 Div1 250 Islands

| 01:44 | SRM477 Div1 250 Islands - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM477 Div1 250 Islands - SRM diary(Sigmar) SRM477 Div1 250 Islands - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→英文が難しい・・・

→ともかく、六角形の区画で海と陸の区切りとなる辺の数を求めればいいらしい。revenueとか普段使わないような変な単語使わないでほしい。。

→とりあえず横幅を2倍にすれば解けそうな気がする

→横幅2倍にして、奇数行を1文字ずらして、海と陸の境界線をカウントする

→サンプル通る→提出

→・・・

→もう少しよく考えてみよう

→む・・よく見たら・・偶数行の最後にパディングするのを忘れている

→でも、サンプル実行でアクセス違反にならないなぁ

→デバッグしてみると、stringのサイズを超えて添字アクセスしても実行時エラーにはならない

→実際にはもっと多くメモリをアロケートしているからなのかな?

→どうしよう・・再提出するか・・・

→まあ・・・多分大丈夫かな・・・・・・・やめとこ

→500へ


チャレンジフェーズ

→突っ込みどころが思い当たらない

→何もせず


システムテスト

→Passed

→よかった。。後で考えるとやっぱり通るか確実でないものを放置するのは危なかった。本来なら再提出ですね。


以下、ソースです。

続きを読む

SRM477 Div1 500 PythTriplets

| 01:44 | SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) SRM477 Div1 500 PythTriplets - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→またもや英語が・・・難しい。legって脚かと思いきやここでは三角形の辺のことを言ってるんですかね。

→つまり、ピタゴラス数となる3つの数の組のうちの小さい方の2つの数の組の数を最大化するということですね。

→うーん・・DPとかですかね・・

→いや・・違うな。。ペアリングの数を最大化するのだから、2部グラフの最大マッチングの可能性が高いと見た

→どうやって2部グラフにするのか。。

→とりあえず全部の要素をソース側とシンク側において、あとで2分の1すれば良いような気もするけど・・何となく反例がありそうな気もするなあ・・(←実はこれでも良かったみたい)

→何となくピタゴラス数の一覧を見ていると、必ず偶数と奇数の組み合わせになるような気がしてきた

→あまりよろしくないけどGoogle先生の力を借りるか・・

→必ず偶数と奇数のペアになるという証明を発見

→マッチングのプログラムを書く

→サンプル通る→提出

→うーん・・間違ってないよなあ・・さすがに偶奇ペアのところは大丈夫だろうし、最大マッチングもライブラリコピペだし・・

→要素数も最大200だし。。→最大ケース試す→全く問題なし

→単純なプログラミングミスもないな。よし!問題なし!久々に500ができた!


チャレンジフェーズ

→最大ケースで落ちそうな人は・・・1人いたが速攻で誰かに落とされる

→他の人のでも読んでみるか

→何か他の人はGCDとかしてるなぁ

→あれ?GCDっていらないんだっけ??

→あれ?問題文にもきっちり書いてある。というか、証明のほうにもきっちり互いに素の場合だけって書いてある(当たり前だが・・)

→あれ?あれ?あれ?何で僕のプログラムはGCD取ってないの??なんで???

→(T-T)...

→なぜかチャレンジを2回受けるものの落とされずに残る


システムテスト

→当然Failed


以下、GCDを取って修正したソースです。

なんというか、ついこないだちゃんと問題文は読まないと、という教訓を得たばかりなのに、なぜ見落としが出るのかよく分からないです。

チェック表でも作って確認するしかないかなぁ・・・

続きを読む

stringのアクセス違反

| 01:44 | stringのアクセス違反 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - stringのアクセス違反 - SRM diary(Sigmar) stringのアクセス違反 - SRM diary(Sigmar) のブックマークコメント

SRM477 Div1 Easyで、stringのサイズを超えた添字アクセスをしても実行時エラーとならないことが不思議だったので、ローカルのVC++の環境とアリーナで、空のstring s対してs.capacity()とs[0]とs[1]を出力してみた

→VC++ -> s.capacity()=15、s[0]='\0'、s[1]の出力で「問題が発生したため、topcoder.exeを終了します」

→アリーナ -> s.capacity()=0、s[0]='\0'、s[1]='\0'

→VC++は、一応stringの最後に\0を入れてcの文字列のような形にしているんだろうか。

→アリーナは・・g++だっけ?capacityを超えたアクセスをすると\0を返すみたい

→結論としては、今回(SRM477 Div1 Easy)はどちらの環境でも1文字パディングを忘れたことでは(どんなテストケースでも)WAにはならないようです

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

2010-07-18SRM476 Div1

250 ACでした。レーティングは5ptと微増。

今のところスピードより確実性を重視して慎重に解いているので、スピード勝負の回はつらいです。。

SRM476 Div1 250 Badgers

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

Problem Statement

問題を見る

→読みにくい・・

→つまり、、2匹以上の場合のみgreed[i]だけ追加の餌が必要ということなのかな?

→あ、違う、よく読んだら他のbadger1匹につきgreed[i]の餌が追加で必要ということか

→えーと・・たかだか50匹しかいないので、x匹飼えるかどうか全部試せばOKかな

→書く→サンプル合わない

→何やら色々書き間違っている→直す→サンプル合う

→コーナーケースは・・0匹と最大匹数を確認、問題なし

→提出

→500へ


チャレンジフェーズ

→狙いどころは0と最大値のコーナーケースくらいか・・

→全員0から最大値までちゃんと見てますね

→特になにもせず


システムテスト

→Passed


以下、ソースです。

ちょっと問題読解とミス修正で時間を取りすぎた・・


続きを読む

SRM476 Div1 550 FriendTour

| 13:49 | SRM476 Div1 550 FriendTour - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM476 Div1 550 FriendTour - SRM diary(Sigmar) SRM476 Div1 550 FriendTour - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→えーと・・・ハミルトン路のような問題かな

→確率を計算するためには、、、うーん・・全探索+DPしかない気がするけど

→ノードは最大36。36*2^36になるから、普通にDPしても無理ですね

→エッジ数は36文字で表現するので、各ノード最大15エッジになるけど・・・だから何なんだろう・・何かに使うのかな。。

→他の方法は・・(色々考える)・・・駄目だ・・解く方法がない

→とりあえず全探索してみよう。もしかしてエッジ数が少ない分、記憶容量が少なくて済むからMAPとかでDPすればいけるかも知れん。

→書く

→むぅ・・なぜかサンプルの0と1しか合わない。なぜだ・・・

→時間切れ


チャレンジフェーズ

→2^36でDPしてる人は・・いるわけないか

→特に何もせず


終了後

→何でサンプルの2番以降の答えが合わなかったんだろう。

→注意深くデバッグしてみるが・・どう見てもプログラムは合っているようにしか見えない

→何か問題の読み違えがあるのかな。もう一度よく読んでみよう。

→ん・・?

→あれ?

→「マナオは自分の友達以外のページを訪問しない」

→は・・?36人全員訪問するんじゃないんですか??

→問題文はよく読まないとダメですね。。。

→以下、修正したソースです。マナオを含めて最大16人に圧縮して全探索+DPしてます。

続きを読む

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

2010-07-07SRM475 Div1

300、600、900と、かなり変則的なセット。

結果は、300 ACでした。Mediumを通せるようになりたいです。

SRM475 Div1 300 RabbitStepping

| 23:22 | SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) SRM475 Div1 300 RabbitStepping - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→シミュレーションか

→計算量は高々17_C_8=24300回のシミュレーション。2^17でも128000だから余裕そう。

→何らかの法則性がありそうな問題の気もするが・・前の失敗もあるから、ナイーブに実装することにしよう。

→書く→サンプル合わない

→ミスだらけ・・問題の読み違い、条件分岐の間違い、For文終了条件の間違い、etc...

→ちょっと酷すぎました。もっと集中力を高めて書くときのミスを減らさなければ・・

→サンプル通る(結局30分もかかりました・・)

→コードが汚すぎてプログラム上のミスを確認する気にもなれない。コーナーケースを確認して提出。

→500へ


チャレンジフェーズ

→みんなシミュレーションのコードが長いから確認が大変すぎる・・

→この問題はサンプル通ってれば問題ないような気がするけど・・・

→特になにもせず


システムテスト

→Passed


以下、ソースです。

最初、Redのマスのために元の位置を各ウサギ毎に記憶する必要があると思ってしまいましたが、よく考えると同じマスに重なったウサギは消滅するので、ウサギ毎ではなくマス毎に状態を記憶すれば良かった。そうすればもう少し早く書けたかな。。。

続きを読む

SRM475 Div1 600 RabbitIncreasing

| 23:22 | SRM475 Div1 600 RabbitIncreasing - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM475 Div1 600 RabbitIncreasing - SRM diary(Sigmar) SRM475 Div1 600 RabbitIncreasing - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→えーと・・問題文が無駄にややこしいです・・・何月にどうなるとか、分かりにくいです

→つまりこれは漸化式にするのかな?

→生まれて1年目、2年目、3年目以降に分けると漸化式にできますね

→kが大きいようだから行列にして計算する問題なのかな

→時間がないし早く書こう

→書く→サンプル合わない

→うーん・・・あ・・MODだから普通に減算したり2で割ったらダメだ・・

→というか、ここが難しいところか。あせりすぎた・・

→時間切れ


チャレンジフェーズ

→2人しか提出してない。

→うーむ・・そうか、実はkは1000万しかなかったからO(N)で良かったのか・・ちゃんと問題を読んでなかったな・・・何となく10億くらいと勝手に思ってた

→1人はどう見てもオーバーフローしているので怪しげなコードだけど落とせるのか良くわからない。赤の人だし罠か・・

→結局何もせず終了


終了後

→とりあえずMODの中で2で割るところは、2^(MOD-2)をかけるように変更

→でも、3年目ウサギの数が全体の半分より多いか等の判断はどうするのか・・

→うーん・・ああ、year=1以外の場合は必ず1年目ウサギと3年目ウサギの数が等しいのか。ということは、3年目ウサギを0にして、2年目ウサギを半分にすれば良い。

→2年目ウサギの偶奇で計算方法が変わるがここはどうするのか・・・

→MOD2で並行して2年目ウサギの数を計算してみよう

→ダメだ、1度2で割ると偶奇が分からなくなる

→ということは、MOD4でやれば・・

→やはりダメか、2度2で割ると偶奇が分からなくなる・・

→ん・・?じゃあ最大50回しか2で割らないから、MOD2^50でやれば・・

→何となくいけそうな気がする

→サンプル通る

→Passed System Test


以下、終了後にシステムテストを通したソースです。

色々試してみましたが、やはりMOD2^50なら通るけど、MOD2^49だと通りませんので考え方は合ってると思います。

続きを読む

余りの出るModの除算

| 23:22 | 余りの出るModの除算 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - 余りの出るModの除算 - SRM diary(Sigmar) 余りの出るModの除算 - SRM diary(Sigmar) のブックマークコメント

SRM475 Mediumで、整数の世界なら余りの出る除算についてModの世界でどうなるのか色々悩んだので、考えたことを記しておきます。


Modでの除算は、フェルマーの小定理を利用して一意な商が出るように定義されます。

フェルマーの小定理:pが素数でnとpが互いに素のとき、n^(p-1)≡1 (mod p)

フェルマーの小定理によると、n^(p-2) * n ≡ 1 (mod p)なので、nの逆数はn^(p-2)と考えて、m/nをm*(n^(p-2))で計算します。

(通常SRMではpは素数のものが選ばれるよう問題が出されるので、上記の方法で除算が可能)


SRM475 Mediumでは、pは素数なので上記除算が可能です。

この問題文中に、nが奇数のとき、(n+1)/2を計算するという記述が出てきます。

通常のintの演算では、nが奇数のとき(n+1)/2はn/2+1と同じ結果になりますが、Modの世界では同じ結果になりません。

intの世界ではn/mに余りが出るとき、m*(n/m)はnになりません。

一方でModの世界では、フェルマーの小定理を利用した除算は余りが出ない仕組みになっているため、m*(n/m)は必ずnになります。


ということで、答えをmod pで返せという問題では、余りの出る除算はしないこと!

ということが分かりました。間違ってたら教えてください。

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

2010-07-01SRM474 Div1

250 AC、500 WAでした。

SRM474 Div1 250 RouteIntersection

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

Problem Statement

問題を見る

→うーん・・・座標をvectorで保存してシミュレーションするだけではないのか、これは・・

→通った点の座標をsetに入れて、移動した数+1より小さければNOT VALIDかな

→書いてみる

→あ、、だめだ、よく見たら次元の最大は10億なのでvectorで表せない

→といっても50個しか点が出てこないので、とりあえず出現する次元にmapで適当にIDをつけてしまおう

→書く→サンプル通る

→mapを使うところ以外は難しいところはない。少し簡単すぎるので不安。。引数Nを使わないというのも大丈夫か、これ・・

→5分ほどかけてコーナーケースなどをチェック

→問題ない。提出

→500へ


チャレンジフェーズ

→10億個vectorを確保しようとしてる人はいないかな・・・

→一人もいない。みんな優秀だなあ。


システムテスト

→Passed


以下、ソースです。

続きを読む

SRM474 Div1 500 TreesCount

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

Problem Statement

問題を見る

→何だろ・・DPっぽいなあ

→どのエッジを削るか、DPしてみるか・・・

→ダメだ、計算量が多すぎる

→どのエッジを使うか、DPしてみるか・・・

→ダメだ、計算量が多すぎる

→順番を変えたりしたらいけるんじゃないか

→ダメだ、どう考えても計算量が減らせない

→うーん・・色々考えていたら30分も経ってしまった

DPばかり考えるとダメだな。。こういうときは、他のアプローチを試さなければ・・

→とりあえずダイクストラで最短経路を求めてみるか

→実はあるノードに同じコストで到達できる数を数えて適当に掛けあわせれば答え出るのでは

→何を数えれば良いか・・・ん・・全ノードにつき、同コストで到達する親の数を数えれば良いか

→あとは、全ノードの親の数を掛けあわせれば、それが解となりそうだ

→合ってるのかな。とりあえず書いてみよう。

→書く→サンプル通る

→10分くらいで書けてしまった。普通のダイクストラに、親の数を数える1文を追加しただけだし、実装が簡単すぎる。怪しすぎる・・・

→うーん・・頭が回らない。。アルゴリズムは合ってると思うんだが・・

→とりあえず提出

→・・・やっぱり合ってるよね。。(不安)


チャレンジフェーズ

→何度か攻撃されるものの耐える。

→意外と普通に通るかもしれんなぁ。


システムテスト

→Failed

→やっぱり。。。(泣)何を間違ったんだろう。

→あーーー・・・ダイクストラの変形の仕方が間違ってる。

  • priority queueを使ったダイクストラでは、次のノードへのエッジをキューに入れていく。
  • ただし、同じノードへ到達できるより小さなコストのエッジが見つかった場合、前に見つかったエッジを破棄し、新たなエッジをキューに入れる。
  • この破棄の際に、これまでに数えた親の数もリセットして1に戻さないといけない。これが抜けていた・・・

→んー・・・単純な間違いがないことは一通り確認したが、この辺まで深く考えてなかった。。

→ダイクストラなどは元々複雑なことをやっているので、変形には細心の注意を払わなければ・・・


それにしても、DPをあきらめてグラフ最短路のアプローチへ移行するのが遅すぎました。

視野を広げてさまざまなアプローチを試すというところはできてきましたが、よりBFS的に早めに切り替えていかなければいけないかな。。


以下、修正したソースです。

続きを読む

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