Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-12-31SRM528 Div1(Practice)

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

SRM528 Div1 250 Cut

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

Problem Statement

解答方針

eelって何だと思ったらウナギらしい。最初文意からしてソバかと思った。

しかしウナギってanguilla(アンギラ)じゃなかったっけ、、と思ったらアンギラは学名だそうだ。ふーん・・


解法は単に10で割れるものから優先的に切るだけ。

10で割れるものの中でも短いものを優先的に切る。

なぜならピッタリ切れると得するのが10で割れるものだけで、なるべくピッタリを増やすほうが得だから。


あんまり難しくはないと思ったけど随分pass率が低かったみたい。なぜだろう。


続きを読む

SRM528 Div1 500 SPartition

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

Problem Statement

解答方針

ナイーブにやれば、使った文字数 * Xに使った文字数 * 現在の文字パターン で40*20*2^20くらいのDPか?

更新コストが2で計算量16億と無理っぽい

実は文字パターンって入力文字列から一意に定まったりしないのかな?

・・・

無理。反例がある。

xxooxxoo で、xxoo と xoxo の2パターン取れる。

うーん

・・・

・・・

2^20っていうのがちょっと無駄な気がする。

oとxの数は決まっているのだから、入力文字列の長さをn、oの数をocntとすると、n C ocntでいいはずだ

最大20C10で、20万程度。計算量は、、3億くらい。。これでもちとオーバー気味。。

最初の文字と最後の文字は、入力の最初と最後から確定する。最初の文字だけ確定させるだけでも計算量は間に合うレベルになるはず。

19C10=10万くらいなので、総計算量1億5千万程度。ループ内部はシンプルなので大丈夫だろう。

文字パターンのループを一番外側のループにするとメモリは40*20くらいでいいので、メモリ的にも問題ない。


ところでxとoの並び替えをするのに、外側のループだからnext_permutationを使っても多分問題ないのだが、何となくnext_cmbという自前ライブラリを使ってみた。

コンビネーションの列挙で計算がシビアなときはこの関数が役に立つと思う。

でも使い方が微妙に癖があって、値が0のときを特別扱いする必要があるのでバグを生みやすい。実際にバグっていたのだがテストするまで見つけられなかったので、危険ではある。。


まあ最初の文字だけ確定とか、こんな微妙な調整をするのも綺麗じゃなくて何だなと思う。

結構スカスカなDPなので、メモ化再帰にするのが良かったかも。


このくらいの正答率(25%くらい)の問題が僕にはすぐには解けなくて練習にちょうどいいみたい。


ソースコード

続きを読む

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

2011-12-30SRM526.5 Div1(Practice)

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

SRM526.5 Div1 250 MagicCandy

| 21:20 | SRM526.5 Div1 250 MagicCandy - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM526.5 Div1 250 MagicCandy - SRM diary(Sigmar) SRM526.5 Div1 250 MagicCandy - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

これは難しい・・・

最近の簡単な250とは一線を画す問題だな

よく分からんので適当にシミュレーションしたら明らかな法則が出てきたのでとりあえずそれで通った


しかしこういうよく分からんままに通すのはとても良くない。

合っているかどうかの検証もちゃんとできないし、力がつかないと思う。

(とりあえずその場しのぎで通すだけならアリだけど後で理解して解きなおしたほうが良さそう)


Editorialによれば、何ターンで終わるかを最初に計算して、逆順でシミュレーションすることで解を出せるとのこと。

逆順のシミュレーションについては二分探索が使える。

なるほど。。何か250にしては難しいような・・・

他にも色々解き方があるようです。


ソースコード

続きを読む

SRM526.5 Div1 500 MagicBlizzard

| 21:20 | SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) SRM526.5 Div1 500 MagicBlizzard - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

これまた難しい!!

正直言って分からなかった。


Editorialによると、1セルの累積snowball数についてはレンジ内の全セルの平均値を使っても問題ないらしい。

そうすると、平均累積snowball数をxとすると、次のsnowballによる解の増分はどこに降ろうが(x+1)^2-x^2で2x+1となる


他にも分散の公式を使う方法とか。色々あるみたい。

結構数学的な発想を必要とする問題だなと思った。


続きを読む

TestTest2012/01/05 22:52double area=(2*r+1)*(2*r+1);
j=ra[i].second;
res+=j*(2*cnt+j-1)/area+j;
cnt+=j;

SigmarSigmar2012/01/14 00:40500 MagicBlizzardの最内ループを効率化できるよ、というコメントでしょうか?
ありがとうございます。

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

2011-12-22SRM527 Div1

  • 275:193.05, 450:274.22, score:467.27, rank:117, rating:2198(+37)
  • 史上最高に2199というイケてるスコアに近づいた

SRM527 Div1 275 P8XGraphBuilder

| 01:20 | SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) SRM527 Div1 275 P8XGraphBuilder - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

Treeになるということで、何かメモ化再帰すればいいんだろう

多少悩みながら以下の方針を思いつく

  • あるTreeが既に途中まで作られているとして、リーフ数と未使用のエッジ数を状態とする
  • 適当なリーフに総当たりで子をくっつけて新しいTreeを作る

何か本番はやっぱりテンパッてしまうようで随分時間がかかってしまった


ソースコード

続きを読む

SRM527 Div1 450 P8XMatrixRecovery

| 01:20 | SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) SRM527 Div1 450 P8XMatrixRecovery - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

辞書順最小ということで、やり方は限られてくると思う

何らかDPしながら最小のものを順番に作っていくとか、独立に1つずつ決められるとか、Greedyに1つずつ決められるとか

DPはちょっと考えても無理そう。方針が全く思いつかない。

独立に決めるのは・・・どう考えても他の値を決めると選択肢が狭まったりするから独立ではなさそう

Greedyにできるか・・・ある「?」を0か1にしたとき、その状態で解があるかどうかが分かれば良い

どう見てもカラムの二部マッチングである

しかし二部マッチングってあまり使わないので計算量を忘れてしまった。

えーと・・・

自分のライブラリはエドモンズカープだったはずだ

エドモンズカープはO(V・E^2)だった

フルメッシュでE=V^2とするとマッチングだけでO(V^5)、さらに「?」の数だけやるのでO(N^7)=無理

いや、よく見ると自分のライブラリはエドモンズカープではなかった

帯域幅優先探索で増加道を決めるフォードファルカーソンで書かれている

こんなもん、二部マッチングみたいな帯域1しかないやつに使っても遅くなるだけじゃないのか・・何だこのライブラリは

うーむしかしさすがに最悪計算量をあまりに最悪に取りすぎている気もする・・・

他に解き方も思いつかないので書くしかない

書いた

全部「?」のパターンでテスト

0.5sくらいで終わる

良かった・・・・・・・

提出


ソースコード

さすがに二部マッチングは書きなおしたほうがいい気がする。。。

O(V^3)の最大流アルゴリズムがあるようなので後日確認しておきたい。

続きを読む

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

2011-12-11SRM526 Div1(Practice)

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

SRM526 Div1 250 DucksAlignment

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

Problem Statement

解答方針

何かえらく実装が重いような・・・

ある列かある行に寄せる必要があるので全探索する

後は歯抜けになったところを適当に詰める必要がある

これは本当に適当に詰めればいい

よほど変な実装をしなければ同じ解になるはず・・である


ソースコード

自分のポリシー的には絶対にやってはいけないレベルの冗長なコードを書いてしまった

少なくとも行と列は回転などを使って同じコードを使いまわすべきである

続きを読む

SRM526 Div1 500 PrimeCompositeGame

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

Problem Statement

解答方針

大まじめにDPなどすれば当然間に合わないということで、何か法則があるんだろうということはすぐ想定できる

問題は何の法則があるのか分からないということだが・・


とりあえず自分が勝てる条件と相手が勝てる条件を考える

  • 5以上の任意の素数は1引くと合成数ということで、5以上のときにそのターンで相手が負けることはあり得ない。逆に3以下になると合成数がないので必ず相手が負ける
  • 相手が勝てる条件は・・・何か難しそうなので後回しにしよう(←実は難しくなかった)

自分が勝てる2や3から逆順にシミュレートできないか。

色々考えたけどよく分からない。うーむ。


もう一回相手が勝てる条件を考える。

少なくとも合成数がK連続するときに相手が勝てるよなぁ・・

ってそれが全てじゃないのか。相手が勝てる条件は、自分の番で数字nのときにn-1からn-kまで全部合成数の場合だけだ

ってことは、、、合成数がK+1個連続するか、初期値Nの下が合成数がK個連続していれば自分の負け。それ以外は勝ち。

シミュレーションは書くだけっぽいな・・


書いた。

何か意外とこまごました条件があって面倒くさかった

一応一発で通った。


ソースコード

(12/22追記)

Editorial見たら普通にDPで解ける問題だった

multisetとか使えばlog nで遷移先候補の更新と遷移先の判定ができるですね。。。

しかしmultisetとか意外と扱いづらく書くのは結構難しい気がする

続きを読む

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