Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-11-30SRM525 Div1(Practice)

  • 参加できなかったのでpracticeで

SRM525 Div1 300 DropCoins

| 20:34 | SRM525 Div1 300 DropCoins - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM525 Div1 300 DropCoins - SRM diary(Sigmar) SRM525 Div1 300 DropCoins - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

残す矩形を全探索

矩形の中身にコインが何枚あるか愚直に数えるとO(n^6)で7億くらいになる

といってもある程度枝刈りが入るので何とか間に合うレベルのようである

コインの数はDPで数えると計算量がO(n^4)に落ちるので安心


ソースコード

続きを読む

SRM525 Div1 525 Rumor

| 20:34 | SRM525 Div1 525 Rumor - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM525 Div1 525 Rumor - SRM diary(Sigmar) SRM525 Div1 525 Rumor - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Aを知ってる人とBを知ってる人を別々に管理すると、状態が2^32になる

どう考えても無理なので、別々に管理しなくても良い方法がないか考える・・・

十分に検討した結果、やはり別々に管理しないと無理。

さて・・

どうしよう。


・・・


待てよ

そもそも一度噂を伝搬した人は、一度に伝搬できる相手全員に伝搬するわけだから、二回以上伝搬する必要がない。

ということは、噂を受け取った次のターンで伝搬してしまえば、そのあとは一切伝搬しなくて良いことになる。

噂が二種類あるので、二種類の噂を同時に受け取ったときだけが問題か

このときに各ウサギがどちらの噂を優先的に伝搬するのか、2^16で全探索すれば良いのではないか。

優先順位が2^16、それぞれにつきシミュレーションが・・

最大伝搬回数16回くらい、16人それぞれで16人へ伝搬するとすると合計で16^3

2^16 * 16^3 = 2^28 ≒ 2億6千万くらい。

内部ループが重そうだし、ちょっと枝刈りが期待できるか微妙なので怪しい。

いや、16人へ伝搬する部分をビットマスク化すれば、計算量を16分の1に減らせる。

これなら計算量は1億以下で余裕ぽい。


書いてみた。

ビットマスクがいっぱい出てきて泣きそうになった。

一応一発で通った。本番でもこのくらいのパフォーマンスを出したい。。。


後でピョートルの成績を見たら470点台とかでどういう頭の回転してるんだろうって思った

コーディングが余りにも早過ぎる。。。


ソースコード

続きを読む

laycrslaycrs2011/11/30 22:01((525pt, 自分は,最大ターンは約16だけど,各人2回しか情報を伝搬しないので16^2 * 2^16と見積もってビット使わず突撃しました.

SigmarSigmar2011/11/30 22:57確かにそうですね!
3重目のループに入る回数は16*2でたかだか32回のような気がします。そうすると、おっしゃるとおりシミュレーションは16^2のオーダーなので、ビットを使わなくても計算量は問題なさそうですね。
コメントありがとうございました。

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

2011-11-19SRM524 Div1

  • 250:75.00, 500:Opened, score:75.00, rank:514, rating:2161(-142)
  • 500が解けなくて250再提出で死亡
  • またイエローコーダーからやり直しか・・・

SRM524 Div1 250 MagicDiamonds

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

Problem Statement

コーディングフェーズ

これは解が最大2なのではないか

合成数のときは明らかに1で、素数のときは、1とn-1に分けるとn-1が偶数だから確実に2でいける

n==1とn==2だけ怪しいので特別扱いしとけばいいだろう(←n==3の考慮漏れ)

できた

提出。243点くらい

みんな245超えてる。提出早い・・・


終わり際に赤い人が何人か再提出しているのを見てコーナーケースが不安になる

コーナーケースがあるとしてもn==3くらいしか思いつかないが・・・

ってn==3って答え3じゃないか。終わった・・

再提出


チャレンジも慎重になりすぎて全然できなかった


ソースコード

まあコーディングフェーズ中に間違いに気づけただけでも昔よりは成長したかな・・・

続きを読む

SRM524 Div1 500 LongestSequence

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

Problem Statement

コーディングフェーズ

まず、直接的に求めるのは何となく難しそうなので、解を探索し実現可能かという判定問題に変換する

今回は解がXでOKならX-1も明らかにOK、XでNGならX+1も明らかにNGなので二分探索が利用できる


さてどうやって判定するのか。

解のシーケンスを配列aとして、条件からすると、a[i]+a[i+1]+...+a[i+C[k]-1]>0とかみたいな条件式がたくさんできる

このままだと変数が多すぎて条件が訳わからんので、何とか変数を減らす工夫を考える。


・・・

・・・


色々こねくり回したけど分からん。時間切れ。。。。


後で

よく考えれば、a[i]+a[i+1]+...っていかにも和を別の変数に置き換えれば?というヒントに見える

それってまさにこないだ解けなかったSRM520 Medium SRMIntermissionPhaseと同じアイデアだ

全然反省が見についてないことに愕然とする・・・


sum[i]=a[0]+a[1]+...+a[i-1]とする。

例えば、sum[0]=0, sum[1]=a[0], sum[2]=a[0]+a[1], sum[3]=a[0]+a[1]+a[2], ...

すると先ほどの条件式は、sum[i+C[k] ]-sum[i]>0といような条件式に置き換えることができる

変形するとsum[i+C[k] ]>sum[i]

これで条件式がとても単純になる

当然ながら、sum[i]<sum[j]かつsum[j]<sum[i]となると矛盾するため、解は存在しない

逆にそのような矛盾がなければ、必ず解が存在する。x軸が添え字、y軸がsum[i]のグラフにプロットしてみれば簡単にプロットできることが分かる。

sum[i+1]-sum[i]の値がまさにa[i]の値である。

ということは、結局推移律が成り立たないようなパターンが存在するかを判定する問題に変換できる。

これは、小なり記号を有向グラフのエッジに置き換えることでループ存在判定問題に置き換えることができる。

ここまでくればあとはやるだけ。。。


なお二分探索の上限値によって計算量が決まるので、上限値を定めることが必要になる。

ここでは無限大のパターンを除いて上限は2000を超えることはない。

無限大にならない条件は、Cに正と負の値が両方存在することである。

その場合に2000を超えるとすると、Cに含まれる任意の正の値をp、負の値をqとすると、r=| |p|-|q| |として、|p|>|q|のときr、|p|<|q|のとき-rをCに加えることが可能になる

例えば1000と-600があるとすると、任意の長さ400のシーケンスが正になる

これを再帰的に続けると、いつかrと-rの両方がCに含まれる状況が発生し、矛盾が生じる


念のため上限を10000にしても、計算量は50*10000*log(10000)<1000万程度である


また、このやり方でいくと、わざわざ場合分けをすることなく、二分探索で解が上限に張り付くパターンは解が無限大、すなわち-1になるのだという判定ができる。


ソースコード

続きを読む

utmathutmath2011/11/19 21:26参考になりました!

SigmarSigmar2011/11/20 11:04コメントありがとうございます。
お役に立てたのであれば幸いです。

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

2011-11-15SRM523 Div1(Practice)

  • 参加できなかったのでpracticeで

SRM523 Div1 250 CountingSeries

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

Problem Statement

解答方針

等差数列については割り算で個数を求める

等比数列についてはイテレーションで個数を求める

等比数列をイテレーションする際に、等差数列に含まれるものを除いていけばOK

意外と等差数列を数えるときに、upperBound<aのときの処理を忘れている人が多かったようで、非常に正答率が低かった。

サンプルを信じすぎないことが大事だと思う。


ソースコード

続きを読む

SRM523 Div1 500 BricksN

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

Problem Statement

解答方針

1つの列について並べ方を列挙していって、再帰的に上に登っていく感じ

連続する空白+連続するブリックで適当に再帰的に並べ方を数えると50^4くらいの計算量になる

もう少し場合分けして工夫すると50^3に落とせるが別にそこまでする必要はない


ソースコード

続きを読む

SRM523 Div1 900 AlphabetPaths

| 02:29 | SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

パスの中間地点でパスを2つに分割すると、長さ11のパスの探索問題にオーダーが落ちる

中間地点をイテレーションし、長さ11のパスを全探索すれば解が算出できる

計算量は21^2*3^10*log(3^10)=4億くらい?実際にはある程度枝刈りが入るためこれよりは大分小さいと思う

計算量が厳しいため無駄な計算をしないように注意が必要

最初サイズ200万の配列を21^2回memsetしていたら余裕でTLEしてしまった。memsetは安易にしないほうがいいですね。。


ソースコード

続きを読む

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