Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-09-26SRM483 Div1

250 ACでした。

波乱の回でどの問題も皆さんボロボロ落としてランクが上がり、チャレンジも手伝って少しレートが上がりました。

SRM483 Div1 250 BestApproximationDiv1

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

Problem Statement

問題を見る

→問題長い・・

→問題が分かりにくいが、0<=A<B<=maxDenの範囲で小さいものから全探索して、最もexact digitが多いもの(同じdigitでは最初に見つかったもの)を探せば良いみたい</ppp>

→小数点以下6桁まで計算しないといけないらしい

→こういう小数点以下を正確に計算する必要がある問題では、散々doubleには痛い目に合わされている

→doubleは表現方法などが実装依存なところがあり、うまくいった試しがない

→ということで、doubleは使わない。A/BをA*1000000/B%1000000とすれば、小数点以下6桁を整数で正確に計算できる(A/Bは1未満なので、今回は%1000000は必要ない)

→書く→string subscript out of range

→A*1000000/Bが6桁未満の数になる場合があるのが問題らしい。6桁になるまで後ろに'0'をpush_backする(←大間違い)

→答えが合わない・・・・・・

→デバッグする

→・・・

→・・・

→あ・・・後ろでなくて前に'0'を埋めないといけない

→アホか・・

→streamのsetwとsetfillを使って'0'を埋める

→サンプル合う

→提出

→170点とか・・・500できないと終わる・・・

→500へ


チャレンジフェーズ

→多分doubleとか使ってる人は大体落ちるんじゃないか

→まあ・・でも落とすケース作るのは結構大変ですよね。無理ですね。

→もしかしたら0<=A<B<=maxDenのところでoff by oneエラーをする人がいるかもしれない</ppp>

→まさかと思ったが本当にいた。B<maxDenになってる。相手が日本人で申し訳ないですが+50</ppp>

システムテスト

→Passed


以下、ソースです。

提出時からちょっと体裁整えてます。

続きを読む

SRM483 Div1 500 Bribes

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

Problem Statement

問題を見る

→普通にやれば2^50のDPの問題

→いかにもDPなので計算量を削減できる可能性を考える

→例えば本当に50個も状態を覚える必要があるのか。何しろ隣に行くごとに1/2になる上に余り切り捨てなので・・・

→influenceの最大値は500・・ということは、、512が2^9なので10個以上離れたところの状態は覚える必要がない

→ということで最大2^18(*50)くらいのDPではなかろうか

→d番目のvoterについて、直前18人が買収されたかどうかの状態を記録する。

→d番目から9人前のvoterが、前後18人の買収状況でresistanceが0にならなければ、DPを更新しない。そうでなければ更新する

→うーん・・・でも、結構書くのが面倒そうな感じなんですが・・・本当にこれが答えか・・

→最小カットとか、どうだろ・・

→ダメっぽい。使えない

→うーん・・・

→うーん・・・

→やっぱりDPしかないか。。残り30分になったから書こう

→まず18人以下だと直前18人の状態が覚えられないので全探索で答えを出して・・

→次に18人より多い場合、DPの初期値として最初の18人分の全状態を計算して・・・

DPの本体を書いて、DPの終了値として有効なものを探索して・・・

→できた→18人より多いサンプル3、4が合わない

→いろいろ間違ってる。直す。合わない。

→まだ間違ってる。直す。合わない。

→だめだ・・時間切れ・・・終わった・・・


チャレンジフェーズ

→他の人のは長くて読み解けない。

→何もせず。


システムテスト

→皆さんFailedだらけになりみるみるうちに順位が上がる

→提出時から200位以上も上がった・・こんなこともあるんだな・・


終了後

→500の間違ってるところが3箇所くらいあった。だめだこれは・・

→特にbitmaskの上位と下位の桁がDPの進み方と逆になってたのが大きな設計ミスだった。これのせいで非常に混乱した。

→250も前後を間違えたし、前回もハノイの問題で前後間違えたし前後間違いが最近の鬼門なのか


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

よく考えたら512未満だから前後9人ではなく8人でよかったのでそこは修正しました。

あと、ir5さんの記事を見て思ったけど16人以下の場合の全探索やらDP初期値の計算やら有効な最終解の計算やらの面倒なところは(0,0)の番兵を前後に8人置けば必要なかった気がする。こういうのができるとコーディングがはるかに楽になるので勉強不足を感じる次第です。

続きを読む

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

2010-09-16SRM482 Div1

250 WAで0点でした。

またレーティングが100以上下がった。散々。。

文章読解テストはもう沢山です。


SRM482 Div1 250 LockersDivOne

| 00:10 | SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) SRM482 Div1 250 LockersDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→最初に開いてないロッカーを見つけ、そこからn+1個ごとにロッカーを見ていって開いてないロッカーを開けていくと理解した

→良く分からんがロッカーの状態を配列で持てば良いんじゃ・・?これだとTLEする?

→とりあえず書く→サンプル合う

→200万(最大値)でもTLEしない。これでいいのか・・・

→念のため1と2の場合もチェック・・2が合わない・・ループ回数に少し余裕を持たないとだめなようだ

→直す→提出→500へ


チャレンジフェーズ

→他の人はリストとか使ってるみたい?

→コードが理解出来ない・・何やってるんだこの人たち・・

→あれ?落とされた?訳分からん(>_<)


終了後

→問題でも読み間違えたかなあ

→何度も読み直す・・だめだ・・・間違いが分からない・・・・・・・・

→・・・

→・・・

→もしかして"open every (n+1)th unopened locker"というのは、全ロッカーを(n+1)個おきに見ていって開いてるのを探すのではなくて、開いてないロッカーだけを(n+1)個おきに見ていくとか?

→あ・・そういう意味か・・

→"open every (n+1)th locker if it is unopened"みたいな雰囲気で解釈していた

→思い込みって怖いですね。。。

→でもこれを解釈間違えてもサンプル合うってどうなんだ。英語読み解きテストじゃなくてアルゴリズムとかコーディングで競争したいんですが・・・・


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

setを使おうかと思ったけど、setの挿入削除は対数時間、listは定数時間なのでlistを使うことにする

実はlistを使うのは初めてかもしれない・・

時間はこれで1.9sとぎりぎりみたい。

続きを読む

SRM482 Div1 500 HanoiGoodAndBad

| 00:10 | SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) SRM482 Div1 500 HanoiGoodAndBad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→ハノイですか

→Daveのほうはいいとして、Earlは何だこれ、何がしたいのか意味が分からない

→よく読むと、Earlのやり方で全部の置き方ができるということらしい。なるほど・・・

→Sampleの0を読んでみる

→なぜEarlがこういう動きになるのか全然分からない。何だこれは

→(15分後)→やっと分かった。1枚目からわざわざこんな無駄な動きをするようなやり方なのか。

→合理的に効率的な動かし方をしようとする人間の自然な考え方と反するやり方だから意味が飲み込めなかった・・ということにしておこう・・

→ともかく、Sample0は分かったが、全体的にどのような動きをするのか

→Daveのほうは2^Nなので簡単にシミュレーションできる。問題はEarlのほうかな。

→色々図を書いてみる→(10分後)→良く分からん・・図で描くシミュレーションは限界があるな

→よく考えると、Earl手法は全部のパターンを必ず1つずつ通ることができるわけだから・・

→一番大きいディスクから目的の位置に移動するまでシミュレーションし、さらに再帰的に次に大きいディスクの移動をシミュレーションし、とやれば良いのでは

→しかもN枚のディスクの移動は3^N-1回でできるとはっきり書いてあるから、実はやるだけの問題だな・・

→もう時間がない・・・早く書こう

→ハノイの状態の表し方に悩みつつ書く

→だめだ答えが合わない→デバッグ→合わない→時間切れ・・・


チャレンジフェーズ

→250が撃墜された時点で、1つ2つ程度落としてもほとんど順位が変わらないので諦め

→自分の間違ってたところでも探すか

→・・・

→上からn枚移動するのを下からn枚移動させてる・・またしょぼいミスしてた・・・


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

ハノイの状態をsetで表そうとしたんだけどeraseを含むイテレータの操作でかなり苦労してしまった・・勉強不足です。

それにしても、250は認識誤りから抜け出すきっかけすらなかったのである意味どうしようもないけど、500は反省すべき出来だった

問題を理解するのに時間がかかりすぎだ。集中ができていない・・・

ハノイの状態を表す手法についてはどんなのが良いのか、また勉強が必要かな・・・

続きを読む

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

2010-09-09SRM481 Div1

250 AC、500 WAでした。

赤が一人もいない部屋で、チャレンジで少し儲けたのでレーティングも上がりました。


SRM481 Div1 250 ChickenOracle

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

Problem Statement

問題を見る

→何か、ややこしそう

→うーん・・・eggのうち、嘘つきの人数をi人と仮定するとchickenのうちの嘘つきはliarCount-i人か

→そうすると、、iを0からliarCountまでイテレートして、eggかchickenがlieCountと一致するか確かめれば良いのかな

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

→条件を色々間違えている。eggとchickenで嘘つきがそれぞれの人数を超えるとcontinueしなければ・・・

→書き直す→サンプル合う→提出

→・・・間違ってないな・・よし

→500へ


チャレンジフェーズ

→たぶん、イテレートせずに数学的な条件式で答えを出す人はいるだろう

→そうすると、間違えやすそうなのは・・・eggをliar数で補正すると常に奇数か偶数のどちらかにしかならないところか

→%2という記載がない人を2人撃墜


システムテスト

→Passed


以下、ソースです。

続きを読む

SRM481 Div2 500 BatchSystemRoulette

| 01:19 | SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) SRM481 Div2 500 BatchSystemRoulette - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→何かすごく難しいような・・

→とりあえず、同じ人のタスクは連続でやったほうが良いのかどうなのか・・?

→1の人のタスク1a, 1bと2の人のタスク2aがあった場合、1a->2a->1bとやるより、2a->1a->1bとやったほうが1の人の終了時間は変わらないが2の人の終了は早くなり全体として良くなる

→ということは常に同じ人のタスクは連続でやるのが良い

→次に、何となく軽いタスクから終わらせたほうが良いように見えるがどうなのか?

→軽い順に1,2のタスクがあったとする

→1と2を入れ替えると、2->1となるが・・2つ目が終わる時間は変わらないのに、1つ目が終わる時間が遅くなり平均時間は長くなる

→タスクを増やして一般化しても同じことが成り立つので、軽い順に終わらせるのが良い

→何だ、簡単なGreedyじゃないか

→よし、書こう

→うまく書けない・・・同じ大きさのタスクがあるとランダム性が生まれるので混乱する

→複数のタスクを持つ場合の平均時間も良くわからない

→色々ぐだぐだになりつつようやく書けた

→何とか終了3分前くらいに提出

→何かミスってそうな気がする・・


チャレンジフェーズ

→出してる人もほとんどいないので何もせず

→あ・・撃墜された・・何を間違えたんだ・・


終了後

→一部オーバーフローしていた。基本的なところができていない。もったいなさすぎる。

→というか、コードが長すぎる。他の人を見て短く書く工夫を勉強しなければ。。。


(9/10追記)

ということで提出が早い5人くらいのコードを見てみましたが、この問題で見落としていた重要な点が分かりました。

タスクの処理順がGreedyに求まるというところが分かった時点で、何とでもなると思い書き始め、途中でコーディングが難しいことに気づいて「実装が難しい問題なのかな」と思い込んでいました。

よく考えると期待値の問題では基本的なテクニックである線形性を利用すれば、非常にコードが簡単になるんですね。もう一つブレイクスルーがあると思っていませんでした。。

線形性というのは、X,Yを確率変数、E(X)をXの期待値としたとき、E(aX+bY)=aE(X)+bE(Y)となる性質のことを言っています。

この問題では確率変数はタスクが終わる時間となりますが、全タスク実行時間の総和で表すことができます。つまり、あるタスクiが終わる時間をXiとし、各タスクjを1つだけ実行する時間をxj、タスクの数をnとすると、Xi=x1+x2+...+xnとなります。(xjはiの前に実行される場合duration[j]、iの後に実行される場合0になります)

従ってE(Xi)=E(x1)+E(x2)+...+E(xn)で計算できますので、P(xj=duration[j])(以下Pと省略)が計算できれば簡単に解けることになります。ここで、人ごとにタスクの総和を求めると、タスクjを実行する人のタスク総和がタスクiを実行する人のタスク総和より短い場合、P=1となり、jとiのタスク総和が等しい場合はP=0.5となり、jの総和がiより長い場合P=0となるのは明らかです。また、jとiが同じ人が実行するタスクだった場合、P=0.5となるのは明らかです。

というわけで、jとiが同じ人の場合、タスク総和が自動的に等しくなりP=0.5となるので、同じ人かどうかは特に判別しなくても良いです。


この問題を解いた本番時に立ち返ると、Greedyだと分かった時点で解けた気になってしまうのは、うまく思考的な罠が仕掛けられていた気がします。やっぱり難しいなと思った時点で一度立ち止まって、再考してみることが必要ですね。


以下、上記解法を反映したソースを追記します。

続きを読む

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