Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-11-23SRM488 Div1(復習)

SRM488 Div1 500 TheBoredomStoreDivOne

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

Problem Statement

ir5さんの記事を見て、共通パートと残余パートに分ければ解ける気がしたので解いてみた。

大まかな方針としては、共通パートの探索を先にして記憶しておき、残余パートの探索時に使用可能な共通パートの最長のものを持ってくるという方法。

共通パート1の探索は、Jの中でインデックスk,lの全ての組み合わせに対し、k,lで終わる共通部分文字列の最大長を記憶する。Bは逆にk,lで始まる共通部分文字列の最大長を記憶する。

残余パートはJとBの共通部分文字列s全てに対し、Jはsの前にくっつけられる最長の共通パート1を探索、Bはsの後ろにくっつけられる最長の共通パート2を探索して、両方の共通パート長が0より大きい場合のみ有効な解とする。

計算量はO(n^4)です。

感想としては添え字周りの実装が大変。本番中に思いついても解けなかった可能性大です。。


以下、ソースです。

システムテストは通ります。

続きを読む

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

2010-11-19SRM488 Div1

日本人がたくさんいる部屋でした

250WAで0点でした。だめだ・・・

SRM488 Div1 250 TheBoredomDivOne

| 20:22 | SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) SRM488 Div1 250 TheBoredomDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

期待値の問題

とりあえずrecursiveに書けそうなので、書いてみる

期待値をf(n,m)とすると、f(n,m)=a*f(n,m)+bの形になるので、このままだと無限ループする

変形するとf(n,m)=b/(1-a)となるので、プログラムを変形

→できた

→サンプルが全然合わない

→うーん・・・

→・・・

→手計算する

→手計算の結果がサンプルと合わない

→あれ?問題勘違いした?

→よく見直す・・・

→・・・

→分からん

→読み違いは見当たらないけど・・

→・・・

→手計算間違っとる(泣)

→考え方は合ってた

→何が間違ってるのか・・

→・・・

→doubleにキャストしないといけないところが勘違いで抜けてた

→直す

→まだ合わない

→まだ間違ってる

→直す

→まだ間違ってる

→直す

→やっと合った

正しい漸化式は以下の通りになった(C(p,q)はpからq個選ぶコンビネーション)

f(n,m)=(f(n+2,m-2)+1)*C(m,2)/C(n+m,2) + (f(n+1,m-1)+1)*(m*n)/C(n+m,2) + (f(n,m)+1)*C(n,2)/C(n+m,2)

f(n+2,m-2)とf(n+1,m-1)はrecursiveに計算すると定数と扱えるので、f(n,m)=a*f(n,m)+bに変形すると、

a=C(n,2)/C(n+m,2)

b=(f(n+2,m-2)+1)*C(m,2)/C(n+m,2) + (f(n+1,m-1)+1)*(m*n)/C(n+m,2) + C(n,2)/C(n+m,2)

となるので、後はf(n,m)=b/(1-a)に当てはめて解くだけ

一応m==0の場合とm==1の場合は分けて書いておこう

(n==1の場合も厳密には分けなければならないが自分のコンビネーションの計算方法だと分けなくても答えは合う)

→(n,m)=(47,47)の場合をテスト

TLEする

→適当に50*50の配列でメモ化する(←間違い)

→47,47が時間内に終わった(←答えが3とか変なのになってたのだが気づかず・・・)

→やっとできた・・・

提出・・・

132点・・・期待値はもっと勉強しないと駄目だな・・

→500へ

500は色々考えたが分からない。難しい・・・時間切れで終了


チャレンジフェーズ

メモ化してない人は・・・いない

LayCurseさんに撃墜される

→ええー自信満々だったんだけど何でだ

→分からん・・・


後で

メモ化の配列が50*50だと全然足りてなかった

47,47だと最終的には94,0になるので、100*50くらいの配列が必要

むしろ片方が決まればもう片方決まるので、1*50の配列でもいい

自分があほすぎて泣ける・・

手計算もまた間違えてまた一杯時間浪費したし、だめだめだ・・


ソースコード

修正しました。システムテスト通ります。

続きを読む

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

2010-11-15SRM487 Div1

250, 550, 950のセット。

250ACでした。。

SRM487 Div1 250 BunnyComputer

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

Problem Statement

コーディングフェーズ

全探索系か・・?

・・・

あ、、全然違いますね。。

(約10分思考停止・・)

あー何だ、mod (k+1)でグループに分類すればいいんじゃないか

だめだ、理解するまでに時間がかかりすぎ・・ちょっと酷い・・

さて分類したグループの要素数が偶数なら全部足すだけだが

要素数奇数のとき、どうするか・・

んーこれは・・奇数番目のうち最小値を捨てればいいっぽい

→書く

→サンプル通った

→提出

175点とか・・駄目すぎる・・・


チャレンジフェーズ

TLEしそうな人が2人いたので適当に大きいケースを投げる

→1成功1失敗

どうやら成功したほうもTLEじゃなかったみたい。最近どうも適当になりすぎてるような・・・


システムテスト

Passed


ソースコード

続きを読む

SRM487 Div1 550 BunnyExam

| 01:18 | SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) SRM487 Div1 550 BunnyExam - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

え・・?これはm/kするだけじゃないの?

直感的にはlinkageとかの制約でRandomな機械が期待値を上げられるとは思えないし・・・

(結局正答率を上げる上で何のプラス情報にもなってないよね?)

証明はうまくできないけどm/kじゃなかったら多分解けないだろう。

ということは-1になるかどうかの判定問題と見た

-1になるのは、サンプル見る限りではk<=2のときはすぐ分かる

とりあえずk>2のときは置いておいて、これで書いてみるか

→サンプル合う

10分くらいでできてしまった。

って550がこんなのでいいわけないよね。

一応m/kになるか、いくつか試しておくか

(手計算でちょっと試す)

あれ?m/kにならない

やっぱりちゃんと期待値を求める問題なのか?

うーん・・・

(約30分経過)

やっぱりlinkageとかの制約が期待値に関係するなら、Sampleの5番目がm/kになると思えない

この手計算もしかして間違ってないか?

あ・・・間違ってる・・・・・・最悪だ・・・30分無駄にした・・・

残り5分くらいなんだけど、k>2は結局考える時間もなかったし良くわからん

時間ないし出してしまうか・・・

→提出


チャレンジフェーズ

予想通り即撃墜される


後で

他の人のブログを見たところ、こういうのはグラフ彩色問題というらしい

地図の彩色問題は知ってるけどそんな一般的なのがあったのね。。知識不足すぎる・・

Wikipedia先生によると、貪欲彩色法(Welsh-Powell)というアルゴリズムでグラフの最大次数+1以上の色があれば必ず塗り分けられるらしい(詳細は分からんが・・)

この問題では最大次数はlinkageの制約から4なので、5色以上だと必ず塗り分け可能ということで、3色と4色で塗り分け可能か探索すればOKみたい

(3色以上ならlinkageに含まれない部分は必ず塗り分け可能なのでlinkageに含まれるもののみ探索する)

ちなみにブルックスの定理とやらで、奇閉路か完全グラフでなければ最大次数の色で塗り分け可能だそうだ

奇閉路だと3色にしかならないので問題にならないとして、この問題ではlinkageの要素中の最小値を持つペアは他のlinkage要素ペアと最大3つしかつながらない(最大値も同様)ので次数4の完全グラフにはならない。なので4色だと必ず塗り分けが可能。

どちらにしても4色全探索が計算時間的には十分可能なので、そこまでする必要はないが・・・


色々書いたけどちょっと知識問題的だなあ。

kohyatohさんによるとグラフ彩色だとか気づかなくて貪欲彩色法も知らなくても解けるということなんできっとそっちが想定解法なんだろうなあ。

とにかく今回は手計算で変な思考ループに入ったのがいけてなかった。

なるべく検算はプログラムでやるようにしたほうが良いのかな。。。

期待値の線形性が成り立つことも未証明だしちょっと厳しい感じでした。。


ソースコード

4色以下全探索で解いてみました

システムテストは通ります

続きを読む

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

2010-11-01SRM486 Div1

300, 450, 1000のセット。

結果は300AC, 450ACでした。

SRM486 Div1 300 OneRegister

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

Problem Statement

コーディングフェーズ

何か頭が回らない・・・

とりあえず全操作を試してみよう

・・・

tは0にはならないし、一度0になったらそれ以外の値にはなれないので、-は使わない

値がいくつでも/を使うと1になるので、/は最初の1回しか使わない

+は2倍、*は2乗を意味するので、単調増加にしかならない

+の場合でも30回くらいで10億に到達するはずなので単純な探索で行ける

ということは、最初に/する場合としない場合でそれぞれBFSすれば良いか

→とりあえず書く

→/した場合としなかった場合の結果比較が結構面倒・・・

→できた

→サンプル合った

→提出


チャレンジフェーズ

オーバーフロー狙い・・・

→intの人いた!

→失敗

→何と・・・最大値を割り算して判定することでオーバーフローを避けている・・やられた


システムテスト

Passed


ソースコード

あとで考えたら、辞書順にBFSしているので最初に/するのを特別扱いする必要がなかった・・・

続きを読む

SRM486 Div1 450 QuickSort

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

Problem Statement

コーディングフェーズ

DPっぽい?

2^50か・・・無理だなぁ

期待値の問題によくある線形性バンザイな感じだろうか

うーんすごく場合分けが多そうで難しそうなんだが・・

やっぱりDPで解けるんじゃないのか実は

整列済の状態を基準に考えると、1回の分割により、一定の連続した区間が選ばれることが分かる

ということは状態数は実は50*49/2しかない

じゃあ、整列済みのインデックスi,jにおいて、各ピボットL[i]に対し、初期状態でL[j]がL[i]の左側にいるか右側にいるかを計

算すればDPできる!

→書く

→サンプル通った

→提出


チャレンジフェーズ

map<vector <int>, double>でメモしている人がいるんだが・・・

ああ、、いいのか、別に。。状態数はどちらにしても1000ちょっとしかないのか。

結局何もできず。


システムテスト

Passed


ソースコード

続きを読む

SRM486 Div1 1000 BatmanAndRobin

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

Problem Statement

コーディングフェーズ

さてあと35分もあるし、1000でも見てみるか

ふーむ 凸包の面積を求めるだけじゃないのか、これは・・

あー頂点の分け方が2^50あるのか。。

うーんでも、任意の2点を選んで直線を引けば分けられるのでは・・・・

分けられそうだが・・・

凸包のライブラリがない

以前別の凸包の問題を解いたときにバグって放置してしまっていた

しまった・・・

頂点2分割と凸包計算の部分、complex<double>なら時間内にできなくもなさそうだが・・

うーん誤差死しそうな予感がする。long longで書けるコードなだけに嫌な予感がする。。

やめよう。。

300と450を見直す時間に充てるか。。


システムテスト

いっぱい出してる人がいましたがいっぱい落ちてました


後で

頑張ってライブラリ書きました

ちなみに「アルゴリズムC++」という本の内容を大いに参考にしています

というかほぼそのままで少しだけmodifyしています

この本によると普通に僕でもすぐ思いつく包装アルゴリズムというやつよりはグラハム走査という手法が最悪時間において優れる

ようなのでそちらを採用しました

ちなみに凸包の直線上にある点は全て消去した(つもり・・・)


結果的には頂点が1つしかない場合の例外を忘れてたので、本番で書けても多分通らなかったかな・・


ソースコード

続きを読む

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