Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-01-28SRM495 Div1

・定期的にやらかしてます

・275 Opened, 500 Opened, score 0, rating -150

・(問題勘違い→思考無限ループ)×2問

・課題:サンプルちゃんと読む

SRM495 Div1 275 ColorfulCards

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

Problem Statement

コーディングフェーズ

全てが一意に定まらなければ{-1}を返すと勘違いしDPで解けそうな気がしたので進める

意外とうまく解けなくてはまる

20分くらいで何となくできた気がしたがサンプル合わない

というか全然勘違いしてる!!!サンプルの解って-1がいっぱいある何これ

読み直すと一意に定まらない部分だけ-1を返すことに気づく

頑張ってそのままDPを修正して何とかならないか・・

20分後全く答えが合わないのであきらめて500へ


後で

冷静になって考えれば皆さんがやっている両サイドからの挟み撃ち的な解が素直で当然思いつくべき解だと思う

最初にDPに行った時点で完全にループに陥った・・

まあDPでもちゃんと書けば解けるのだが。焦ってばかりでそんな精神状態を保てていない。。。

以下書きたかった内容のDPのソース

続きを読む

SRM495 Div1 500 CarrotBoxes

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

Problem Statement

コーディングフェーズ

Yを人参が入っている箱と勘違いする

色々悩む

箱を開けると1/nの確率で空箱なので、これを繰り返すと(乗算で)確率が求まるのか?

適当に書く

サンプル合わない

今更だがどうしても矛盾が発生する気がする。空箱が3だったときに1を開けて3がYだったらどうなるんだ

もう一度よく読むとYのところは人参箱決定ではなく、人参箱か空箱かが分かると書いてある

・・・終わった・・・

というか最初におかしいって気づけよ・・

時間切れ


後で

さて・・解くか・・

  • サンプル3の解析とかシミュレーション計算ですぐ分かるが、n個の箱の状態が全て分かるまで空箱が特定できない場合のみを考えても問題ない(そうでない場合も確率は結局同じになる)
  • その場合に、空箱の可能性がある箱を開けた数をkとすると、答えは(n-k)/nになる(k/nの確率で空箱を開けてしまうから)
  • 最後の1個は開けなくても全状態が把握可能(n-1個分かれば当然残りの1個の状態も分かるから)
  • 1個は開けなくていい箱があるが、これは50通りしかないので単純に全探索すればいい
  • informationを有向グラフと見ると、直感的に言えば入力辺がない箱は全て開けなければならないのは明らかだが、これは必要であって十分でない、なぜならループがある場合があるから
  • 入力辺がない箱を全て開けたとき、残るのはループを持つノードのみである。ということはあとは残ったのをGreedyに適当に開けていけば良いのかというと、これも真ではない
  • ループ構造からループ構造への一方向性がある場合がある。例えば、、A->B、B->A、C->A、C->D、D->Cの4ノード5エッジを考えると、AかBを開けると追加でCかDを開けなければならないのに対し、CかDを最初に開けるとそれ以上開ける必要はない
  • 従って適当に選んだノードの親を適当に辿るなどし、ルートっぽい(CやDのような)ノードを探索する必要がある
  • 以上をコーディングすると答えが出る

ブレイクスルー多すぎです。普通に時間内には間に合わなかったと思います。他の考え方もあるんかな・・

いずれにしても160人出して30%強の正答率なので数十人しか正解しておらず500としてはかなり難易度の高い問題と言える


(1/29追記)

親を辿ってルートっぽいのを探せば、入力辺0のものを最初に探索する必要はないのでコードはもっと単純になることが分かりました。なお最初に書いた遡り方は間違っていたのでコードを修正しています。(これでもシステムテストは通っていたのだが・・・・・)


以下、ソースです

続きを読む

AkshayAkshay2013/02/16 22:43This is the peercft post for me to find at this time

fmsxxkqfmsxxkq2013/02/18 05:16cyP1oT , [url=http://xumbuxjdrfyr.com/]xumbuxjdrfyr[/url], [link=http://zreanbrrqnwm.com/]zreanbrrqnwm[/link], http://xdivklnewdbg.com/

ryzincryzinc2013/02/19 14:04fQHNP4 <a href="http://lwdlhcdpomaw.com/">lwdlhcdpomaw</a>

indkdahindkdah2013/02/19 19:14zwiioO , [url=http://crmdrspswgmq.com/]crmdrspswgmq[/url], [link=http://vfasoeacrate.com/]vfasoeacrate[/link], http://zdjmdopeoupz.com/

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

2011-01-23SRM494 Div1

250AC、500Opened、チャレンジ+50でした。

500をゆっくりやっていたら時間切れになってしまった・・・また勿体無いことした

もっと上位を狙うためには可能な限り早く解くよう努力しなければ・・

レートはようやく2000を超えました。


SRM494 Div1 250 Painting

| 13:50 | SRM494 Div1 250 Painting - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM494 Div1 250 Painting - SRM diary(Sigmar) SRM494 Div1 250 Painting - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

おお、最近では珍しくやるだけの問題っぽい

O(n^5)だが・・・まあループ内の計算はしょぼいから何とかなるだろう

→書く

→サンプル合わない

何か繰り返しの範囲とか色々間違っている

→直す

→サンプル合った

→最大ケース(全部B)を試す

→問題なし

→提出

結構時間かかっちゃった・・・

コーディングスピード勝負はイマイチ勝てない感じ・・


チャレンジフェーズ

明らかにおかしい人を発見!!ラッキー!!!

+50


システムテスト

Passed


ソースコード

ブラシの大きさ2~50について、塗れるところを全部塗った場合に、目的とする絵が描けるかをチェックしています

続きを読む

SRM494 Div1 500 AlternatingLane

| 13:50 | SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) SRM494 Div1 500 AlternatingLane - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

いかにもDP

これはDPに違いない(←そうでもない)

ビューティを最大化するってどうしたら良いんだろう

んー・・・あ、そうか、極大か極小となっている高さの木以外を全部切り倒せばいいんだ

・・・

ということは結局何も切り倒さなくても一緒?みたいだな・・

じゃあ、、書くだけなのでは・・

DPでi本目まで倒したときの、最後の木の高さhのときのビューティの期待値を計算する(←まだDPにこだわっている)

何となく計算量無理そうだが、とりあえず答えが合うかどうか、DPで書いてみる

→答え合わない→色々直す

やっと答え合った・・・

確率計算の考え方が合っていることは分かったが計算量10万*10万なので無理

というか

DPの必要ないだろこれ

隣り合う木の高さの差分の平均値を合計するだけじゃないか

あー残り10分しかない

どうするんだどうするんだ・・(焦る)

i-1番目の木の高さlow[i-1]のときの、i番目の木の高さlow[i]~high[i]までの差分の合計値を求めれば、O(n)でlow[i-1]+1~high[i-1]の高さのときの差分合計値も求められる

よしこれだ

書いた

合わない

何でだーーー

→時間切れ

ゆっくりやりすぎた・・・最後は焦ってダメダメだし・・要反省・・


ソースコード

min関数が1個抜けてたのが合わない原因だった

というか、単に等差数列の和を求めればもっと簡単ですよね・・・何で気付かないんだ・・

続きを読む

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

2011-01-13SRM493 Div1

300、450、1000の変則セット

450スピード勝負かと思いきや意外とそうでもなかった。

むしろ300のほうが難しかった。

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


SRM493 Div1 300 StonesGame

| 00:04 | SRM493 Div1 300 StonesGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM493 Div1 300 StonesGame - SRM diary(Sigmar) SRM493 Div1 300 StonesGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これはmin-maxゲーム木ぽい?

状態数100万・・・まあ大丈夫だろう(←大間違い)

書いてみた

→stack overflow

あー無限ループしている

サンプルを見直すと無限ループはDrawなのか・・

ふむ・・勝ち負けの2値ではなくDrawを含む3値にすれば良いかな

訪問済の状態を配列で記憶して・・

書けた

サンプル通った

と思ったら4以降通ってない

stack overflowしてる

あ、そうか・・そりゃそうだよな・・深さ100万のDFSじゃオーバーフローして当たり前だ

そんなこと最初に気づけよ・・・何で気付かなかったんだ・・

ってどうするんだ・・

・・・

・・・

min-maxじゃ解けないのか、もしかして

今更そんなことに気づいてもすでに30分経過してるんだが・・・

だめだ

はまるパターンだ

諦めて450を解こう

450はきっと簡単に違いない

→450へ


後で

結局450終わったあとも良くわからなかったがチャレンジフェーズでようやく2ターンしか考えなくていいことに気づいた

ということで解いてみた

2ターンのみと分かっても結構条件がややこしく、難しい

個人的には450より難しい・・・


ソースコード

続きを読む

SRM493 Div1 450 AmoebaCode

| 00:04 | SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

いかにもDP

普通にやれば・・7^50 明らかに無理

やっぱりここは7という数字がいかにも何かありそうですよね

7・・・うーん・・

7種類しか数字がないわけだから、鳩の巣原理で解は最大7か。

これだ!

直前の7個だけ覚えとけば良いに違いない

7^7*50だから、約4000万。いけるか・・

状態の表現方法は・・・ビットに収めようとすると、3*7=21ビット必要

しかし2^21*50にすると1億超えるからきついような気がする

・・というか直前6個が異なる数字なら解が7だから覚えるのは6個でいいのか

2^18*50になった。でもまだ厳しい気がしてきた・・

よく考えるとイテレーティブに書くと2^18*50になるがリカーシブに書けばそんなことないのでは

そもそも6個覚える場合は6個とも違う数字でなければ意味がないので、状態は7P6*50=25万くらいしかないんじゃ・・・

これはmap<vector <int>, int>を使っても楽勝な予感。いける。

最初だけ直前6個が存在しないから、SRM483 500(Bribes)の反省を生かして番兵っぽく0を6個並べとこう

→書けた→サンプル通った

一応0を50個試しておこう

一瞬で終わった。大丈夫そう。

→提出


チャレンジフェーズ

誰かが絨毯爆撃したらしく、数分で半分くらいのmediumが落ちた

特に何もできず・・


システムテスト

Passed

いつもmediumは下らないケアレスミスやらで落とすのだが今日はPassしてくれて助かった

今回はeasyが提出できなかったから本当に助かった・・・

easyを適度に諦めたのが功を奏して十分な時間が確保できたのが良かったかな


ソースコード

実は一番計算量が厳しいのは0が49個+最後に7が1個とかのパターンだったみたい

最悪でも1秒ちょいで終わるが思ったより時間がかかった。コストの見積もりを勘違いしたのかそんなもんなのか。。。

あともう少し綺麗に書きたいものです・・

続きを読む

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

2011-01-11Facebook Hacker Cup 2011 Qual Round

Q&Aにはソースコードを提出しないと解は無効みたいなことが書いてあるのにソースコードが提出できるようになっていないとい

う非常にmessyな雰囲気の仕様でした

結論的にはどうやらQual Roundではソースコードは必要ないらしい

一応3問全部通りました


Facebook Hacker Cup 2011 Qual Round DoubleSquares

| 22:59 | Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) のブックマークコメント

Problem Statement

数Xが与えられるので、平方数2つの和で表す方法が何通りあるか答える

0<=X<=約20億


解答方針

0~X/2までの平方数(sqとする)を列挙する

平方根をイテレートして列挙すると0~3万くらいで0~10億まで列挙可能なのですぐ終わる

X-sqが平方数かどうか確認して、平方数なら解を+1する

非常にストレートフォワードな問題・・・


ソースコード

続きを読む

Facebook Hacker Cup 2011 Qual Round PegGame

| 22:59 | Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

パチンコみたいな台が与えられる

市松模様的に障害物があるが一部障害物のない部分が入力で与えられる

一番上の任意の場所から玉を落とし、障害物に当たると、左端と右端以外は1:1の確率で右か左に跳ねる

一番下のどこかに目的地が与えられるので、その位置に行く確率が最も高い入り口及びその確率を答える


解答方針

各入口から落とした場合について、行き先候補の確率をDPで計算する

シンプルなDP。やるだけ。

tieはないという注意書きがあったがサンプルにtieがあったような気がするのは気のせいだろうか


ソースコード

デバッグしやすいようにvector <string>で台を表現しています

(VC++だとvector <string>が図としては見やすい)

続きを読む

Facebook Hacker Cup 2011 Qual Round StudiousStudent

| 22:59 | Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) のブックマークコメント

Problem Statement

1~9個の長さ最大10の単語が与えられるので、適当に順番を並び替えて全て連結し、辞書順で最も早い文字列にする


解答方針

数が少ないのでnext_permutationで全探索すれば良いです


・・・と簡単すぎてあまりにあっけないので、時間もあることだしもっと簡単で効率的な方法を考えました。

ある2つの単語aとbを比較した場合、片方がもう一方のprefixでない限り、辞書順に早いほうから並べれば良いのは明らか。

prefixだった場合は・・何となくa+bのほうがb+aより辞書順が早ければaを先に持ってくるべきな気がする。

色々場合分けして考えてみると本当っぽい。

厳密には証明していないが上記の順序付けでソートするだけで良いのでは。

200ケースくらい試したがnext_permutationの解と完全に一致するので多分大丈夫だろう。


ソースコード

続きを読む

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