Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-07-27SRM513 Div1

  • 250:226.16, 500:Opened, score:226.16, rank:203, rating:1956(+10)
  • パターン考慮漏れでまた500ができなかった。いけてなかった。

SRM513 Div1 250 YetAnotherIncredibleMachine

| 15:18 | SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) SRM513 Div1 250 YetAnotherIncredibleMachine - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

どう見ても全探索するだけ

の割には時間かかってしまった。。。

と思いきや皆もっと時間かかっていた。不思議。みんな高速化を頑張ってたのかな。


ソースコード

続きを読む

SRM513 Div1 500 PerfectMemory

| 15:18 | SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) SRM513 Div1 500 PerfectMemory - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

神経衰弱

ペアが両方Openしたマーク数(two)と片方だけOpenしたマーク数(one)を状態として持つDP

DP更新のパターンを漏れ無く考慮できていればすぐ終わる

私は最後まで漏れに気づきませんでした


ソースコード

続きを読む

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

2011-07-14SRM512 Div1

  • 250:WA(-25), 500:Opened, score:-25.00, rank:843, rating:1946(-173)
  • 定期的なポカの日

SRM512 Div1 250 MysteriousRestaurant

| 15:03 | SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) SRM512 Div1 250 MysteriousRestaurant - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

何というかイテレーションするだけ

問題勘違いしてて時間かかってしまった

この時点でかなり終わっていたが更にチャレンジされてしまった

isupper関数を書くところでislower関数を書いていた

その上変な2分探索してる人を間違ってると勘違いしてミスチャレンジ

ダメな日はどうにもならん・・・


ソースコード

続きを読む

SRM512 Div1 500 SubFibonacci

| 15:03 | SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) SRM512 Div1 500 SubFibonacci - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

任意の2つの数を選択して、その2つがあるフィボナッチに含まれるかは、そのフィボナッチ上で何要素離れたペアなのかを決めてやれば2分探索で判定可能だと思ったがすごく書くのが面倒そうなので他の方法を考えていたが結局他になさそうなので書いたが時間内にバグが取れなかった。


ソースコード

続きを読む

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

2011-07-10TCO2011 Round3

  • 250:75.00, score:75.00, rank:186, rating:2119(+1)
  • 250が500並に難しかった。500は見る余裕すらなかった。再提出で敗退。

TCO2011 Round3 250 ArtShift

| 14:47 | TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) TCO2011 Round3 250 ArtShift - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

好きなようにpermutationできるのでWとBの順番はどうでもいい

循環させるグループに分類すれば終了


例えば{0,1,2,3,4}という順列があったとき、{1,0,4,2,3}というpermutationを作ると、{0,1}と{2,3,4}がそれぞれ循環する

このように循環させるグループに分けると、順番は任意にできるので例えばW1個B2個のグループならWBBといったようにWを左端に片寄せするような順番にすることが可能

なので1グループで最大でグループ要素数分のパターンがある

ただし全部同じ色だと1パターンしか取れない

以上が分かれば、Wの数とBの数で1つずつグループを決めてやるような書き方で計算量問題なし


ソースコード

続きを読む

TCO2011 Round3 500 PrefixFreeSuperset

| 14:47 | TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) TCO2011 Round3 500 PrefixFreeSuperset - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

実装問題的な感じ

既存のwordに対し2分木を作ってやる

あとは空いているところを使って木の高さを平準化しながら必要なだけ高さを増やしていくだけ

「空いているところを使って」というのが意外と難しいと思う


ソースコード

続きを読む

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

2011-07-03SRM511 Div1

  • 250:213.51, 500:WA, score:213.51, rank:308, rating:2118(-37)
  • 入念に確認したはずの500で2箇所もミスっていたことにショックを隠せない

SRM511 Div1 250 Zoo

| 17:46 | SRM511 Div1 250 Zoo - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM511 Div1 250 Zoo - SRM diary(Sigmar) SRM511 Div1 250 Zoo - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

明らかに片方が0~n、もう片方が0~mみたいになるはずだ

考え方は簡単だが、サンプルがすごく弱いので、コーナーケースに細心の注意が必要そう

まずは各数字の数をカウントしておく

数字の0を最初とすると、最初はカウント2が0個以上の任意数続いて、次にカウント1が0個以上の任意数続いて、最後は全てカウント0となるはずだ

全パターンを網羅すると、、カウント数の遷移としては以下のように分類される

(有効は解が存在可能、無効は解がないことを示す)

  • 2→1 ... 有効
  • 2→0 ... 有効
  • 1→2 ... 無効
  • 1→0 ... 有効
  • 0→2 ... 無効
  • 0→1 ... 無効
  • 任意の数→3以上の任意の数 ... 無効
  • 3以上の任意の数→任意の数 ... 無効

少しまとめると、前の数字より増える場合は無効、3以上の数が含まれる場合は無効、それ以外は有効となる

あとは2の数(=twoとする)と、1が登場するかどうかを判定する

答えは2^twoで、1が登場する場合のみ、さらに2倍する

(例えば、0,0,1,1,2,3,4とかだとすると、0の選び方が2通り、1の選び方が2通り、2の選び方が2通り、3,4は2の選び方に応じて一意に定まる)

ということでコーディング

いろんなパターンを試す

有効パターン:2→1→0、2→0、1→0等

無効パターン:上記で挙げたもの

全部問題なさそう

提出

かなり入念に確認したので結構遅くなった・・・でもコーナーケースが怪しそうな回はそれで良いと思う。

(本当は怪しげなコーナーケースが出てこない書き方をするのが最も良いと思いますが・・・)


チャレンジフェーズ

上に挙げたテストケースで、サンプルに含まれない2→0のパターンが最も怪しそうだと睨んだ

この場合に1が登場する場合と同様に最後に2を掛けている人がいそうだ

実際いた

確認中に誰かに落とされる

気づいたらそんな人はみんな落とされていた。みんな早い・・・


システムテスト

Passed


ソースコード

続きを読む

SRM511 Div1 500 FiveHundredEleven

| 17:46 | SRM511 Div1 500 FiveHundredEleven - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM511 Div1 500 FiveHundredEleven - SRM diary(Sigmar) SRM511 Div1 500 FiveHundredEleven - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

相変わらず500は難しい

まず511=(2^9)-1=111111111(2進数)

ということで、最終的に9つのビットが全て立てば負けということか

or演算なので一度立ったビットが戻ることはない。。。

普通に使用したカードでビットDPすると・・・2^50なのでできるはずがない

まともにやると2^50の呪縛から抜けられないので使用したカードが厳密に分からなくても勝敗が分かる方法があるはずだ

Nimだとxorした結果で勝敗が分かるがそのようなルールはないのか・・

・・・

・・・

20分くらい時間を使ってしまった。すぐには見つかりそうにない。Wrong Attemptのような気がする。

よく考えると、ある状態のときに、使っても状態が変化しないカードは区別する必要がないな

(例えば2進数11のとき、01や10や11を使っても状態は変わらないので、全て同じカードと見做せる)

逆にある状態のときに、使うと状態が変わるカード集合は一意に定まるのでは

うむ。間違いない。ということは、状態が2^9で、さらに使っても状態が変わらないカード数が最大50枚のはずなので、512*50=250000くらいの状態数に落とせる。いける。

ある状態のときに、使うと状態の変化するカードを管理するため、9つの各ビット毎にそれを含むカードをまとめておこう(←誤ったアプローチ)

あとは、全カードのorが511にならない場合は特別扱いしておけば良いかな

よし書けた

何か色々変な書き間違いを発見

直した

間違いないよね・・・(←コードだけ確認して、コーナーケーステストを怠っていた)

提出


システムテスト

チャレンジされなかったのでいけると思いきやあっさり落ちた


後で

  • 0のカードは最初から常に状態を変化させないカードとして計上しないといけないのに、無視していた。コーナーケース何も考えてなかった。猛省すべき点だ・・・
  • ある状態から別の状態に遷移するとき、各ビットごとに、まだ立っていないビットに対して、そのビットを立てることのできるカード集合を管理していた。遷移するとき、各ビットのカード集合の中で状態を変化させられなくなるものだけ数えておけば良いと思ったが間違いで、別のビットを立てるカードも数えないといけなかった。

例えば01と10と11の3つがあり、現状態が0とすると、1ビット目集合が{01,11}、2ビット目集合が{10,11}としており、1ビット目に着目して11を使用したときに、状態を変化させなくなるカードは01だけかと思った。実際には10も状態を変化させなくなるため計上漏れが発生していた。

これははっきり言って気付けそうにもない。どうすればいいんだろう。無駄にビットごとに管理などという結果的に意味のないことをしたのが誤りなんだろうが・・・

なるべくシンプルに書くように注意することくらいしかできないのかな。。。


ソースコード

続きを読む

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