Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-26TCO2011 Round2

  • 250:230.68, 500:203.23, score:433.91, rank:82, rating:2155(+101)
  • 予想外に500が解けて随分うまくいった。

TCO2011 Round2 250 GuessTheNumberGame

| 13:30 | TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何これ むずい

いやしかし落ち着け。Easyからそんなに難しい問題が出るはずがない。

よく考えると、合成数がYだと必ずその因数もYになるはずだ

ということは、素数だけ考えればOKか!!

いや、違う

2がYでも4や8がYとは限らない

素数のべき乗を考えないといけない

まずエラトステネスの篩でnまでの素数を列挙して

各素数について、n以下で最大何乗までいけるか計算する

そしてその指数+1を解に掛けていけば、答えが出る

書いた

サンプル合った

提出

サンプルが非常に強固だから問題なさそう


ソースコード

続きを読む

TCO2011 Round2 500 STable

| 13:30 | TCO2011 Round2 500 STable - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round2 500 STable - SRM diary(Sigmar) TCO2011 Round2 500 STable - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これまたむずい

各セルの文字列長は簡単に計算できるので計算するとして

各セルについて、上と左を比較したときにどちらが辞書順で小さいか判定できれば解ける気がする

うーん・・・・

・・・

・・・

分からん

普通に上のセルと左のセルを1文字ずつ比較してみるか

k文字目が最終的に(i,0)か(0,j)のどのセルに行き着くのかは、各セルの前半と後半が上からきたのか左から来たのか記憶しておけばすぐ求まる

あとは、自明な枝刈りとして、k文字目が同じセルから由来しているのであれば、その文字数分飛ばす

頑張って書いてみた

おおー意外と一瞬で解答出た!!!枝刈りだけでいけるとは。

サンプル強そうだし問題なさそうだな・・・

提出


ソースコード

多くの人はDP的に解いていましたが全く別解法と思われます

続きを読む

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

2011-06-22SRM510 Div1

  • 250:105.63, 500:Opened, score:105.63, rank:213, rating:2054(-35)
  • 250がすごい罠の掛け具合。こういうのどうなんだろう。。全体的に非常にハードな回でした。

SRM510 Div1 250 TheAlmostLuckyNumbersDivOne

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

Problem Statement

コーディングフェーズ

これは・・ほとんど4と7しか出てこないんだったら全探索で良いのでは?

2^16*10*10くらいだよなぁ・・・全然いけそう

さて書くか・・ん???解がlong longだと・・???

そんなばかな・・・どう考えても32bitを超えると思えないが・・

・・・

・・・

メモ化できるようにdfsで書いてみよう(←判断誤りでした。とりあえず全探索コードを書いておけば・・・)

とてつもない場合分けが発生

答え合わない~~

途中ちょっと500に浮気。500難しい。戻ってくる

結局50分くらい経ってようやく答え合った

最大ケースで700万くらい。やっぱりlong longいらんじゃないか!!罠か!!!最初から全探索書いて試せば良かった。

結局メモ化もせず提出。

終わった・・・


チャレンジフェーズ

非常に僅差で並んでいるためリスクが大きいので何もせず


ソースコード

続きを読む

SRM510 Div1 500 TheLuckyGameDivOne

| 20:47 | SRM510 Div1 500 TheLuckyGameDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM510 Div1 500 TheLuckyGameDivOne - SRM diary(Sigmar) SRM510 Div1 500 TheLuckyGameDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

そもそもJohnがminimize、Brusがmaximizeするのかと勘違いしていた

答え合わなくて終了

いい加減ちゃんと問題を読むようにしないと・・・


後で

まずは、ラッキーナンバーが2^11程度しかないので、それを全部列挙すること

あとは適当に全探索したらOK

・・・なんだけど、この全探索が曲者でとても難しい


手始めに、ラッキーナンバー数をnとすると、解を1~nで探索する

解がiだとすると、全てのbLenで解がi以上となるjLenが存在するか判定できればOK

全てのbLenで解がi以上となるとはどういうことだろうか

ラッキーナンバーが以下のような数直線で並んでいたとする(*がラッキーナンバー)

---*-----*----------*----*-----*----

例えば、解が3になるためには、bLenが以下のような範囲以上である必要がある

--[*-----*----------*---]*-----*----

同様に、bLenは以下のような範囲以上である必要がある

---*----[*----------*----*----]*----

この時点で、どちらの範囲もbLen以上だったとすると、この5つのラッキーナンバーの内側では全てのbLenで解がi以上となる区間ということができる。

(実際には左端や右端はbLenの長さによってある程度はみ出せるため、もう少し広い範囲でOK)

この範囲内にjLenを置くことができれば、解がi以上となりうると言える。


このような複雑な判定をすることで答えが求められるが・・・ちょっと大変すぎなような

もっと簡単に出せないかなぁ。。。


ソースコード

続きを読む

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

2011-06-19TCO2011 Round1

  • 250:WA(+200), 500:418.97, 1000:Opened, score:618.97, rank:197, rating:2089(+54)
  • 250でコーナーケースミスを出してしまった。痛い。
  • 今回の1000くらいのレベルが解けるようになりたい。

TCO2011 Round1 250 TripleStrings

| 17:19 | TCO2011 Round1 250 TripleStrings - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round1 250 TripleStrings - SRM diary(Sigmar) TCO2011 Round1 250 TripleStrings - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

どう見てもBとCをそれぞれo専用とx専用のバッファに使うだけ

initのsuffixとgoalのprefixが等しくなるまでBやCに詰め込めば良い

簡単だな

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

答えを2倍しないといけなかった(←ここで2箇所修正が必要なのに1箇所しか修正しなかった)

サンプル合った→出した


チャレンジフェーズ

何気なく開いた人のコードに、最後にinitの長さ*2を返すというのが見える

そういえば自分は最後にinitの長さを返していたような気がする

これは大丈夫なのか・・・

・・・

・・・

大丈夫ではない。{"xoxo", "xxoo"}で落ちる

まずい。

同じミスをしてる人を探す

いた。落とす

またいた。落とす。

合計5人落とした

最後時間なくて適当に投げたら2人ミスった。もったいなかった。

チャレンジ運が良かったから被害が少なく済んだけど、今回は非常に良くないミスをしてしまった。。。


ソースコード

修正済みコード

続きを読む

TCO2011 Round1 500 MuddyRoad

| 17:19 | TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) TCO2011 Round1 500 MuddyRoad - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは、次がmuddyであれば、その次がmuddyかどうかに関わらず、ジャンプしたほうが良いよね

(そのほうが早く連続するmuddyの区間を抜けられるから)

それから、次がmuddyでなければ、無条件にそこを通れば良いよね

(muddy区間のぎりぎり手前でジャンプしたほうが良いだろうから)

という戦略に基づいて、道iを通る確率をdpで求める

で、道iにいるときに、次とその次が両方ともmuddyだった場合のみ、muddyの道を通ることになるわけだ

ということでコーディングする

サンプル合った

比較的すぐ解けた!いい感じ。


ソースコード

続きを読む

TCO2011 Round1 1000 IPv444

| 17:19 | TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) TCO2011 Round1 1000 IPv444 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

最近APNICのIPv4アドレス在庫が枯渇しましたから、それにちなんだ問題かな

現実のIPv4アドレスはトレードされるということはないと思いますが・・・


コーディングフェーズ

価値の高い順に売っていって、既に売った分を数えないように計算しようと思ったが全然うまく書けなかった

1時間弱もあってこれでは・・・

もう少し戦略的に書き方を練るようにしないとダメだな・・


後で

あまりいい書き方が思いつかなかったのでtop submissionを見てしまいました

C++のtomekkulczynski氏の書き方が分かりやすかったです。

4つの数字の左側から分岐して、dfs的にパターンを列挙し、そのパターンで最も価値の高いものを売るようにする

JavaのPetr氏も見たけど、書き方は違うが同じような感じで、単に全探索している感じ

パターン的には高々50^4しかないので、計算量も大丈夫

しかし、Petr氏は各パターンが有効な範囲かの判定と各パターンの最大価値算出を同一変数で書いたり、出現する数字を種類数で圧縮したりとやや巧妙な書き方が多いので何でそんな早く書けるのか不思議・・・


今回はうまく全探索が書けるかというのがポイントだったかな


ソースコード

続きを読む

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

2011-06-05Google Code Jam 2011 Round 2

  • A-small/A-Large/B-small(1WA)/B-Large:Passed, score:38, penalty(time):1:48:41, rank:739
  • B, Cでハマって敗北・・・何をやってるんだ・・・

Google Code Jam 2011 Round 2 A Airport Walkways

| 21:25 | Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) Google Code Jam 2011 Round 2 A Airport Walkways - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

歩く速さと走る速さの差は一定なので、歩道が遅いときに走るほど効果が高い

例:歩く速さ2、走る速さ4、歩道Aの速さ2、歩道Bの速さ4とすると、Aで走ると歩きの1.5倍の速さ、Bで走ると歩きの1.333倍の速さになるので、Aで走ったほうが得

ということで、歩道の速さでソートして遅い歩道からGreedyに走るようにすればOK

すぐ解けた

提出時間:Large 18m28s


ソースコード

続きを読む

Google Code Jam 2011 Round 2 B Spinning Blade

| 21:25 | Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) Google Code Jam 2011 Round 2 B Spinning Blade - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

よくある普通のDPに見えるのだが何かうまく計算できなくてとりあえずsmallを全探索しようとし始める

サンプル合ったのでsmall提出。WA。おいおい・・・

(Kが偶数のときと奇数のときで重心位置が0.5刻みになるのに1刻みみたいに書いていたのが原因)

・・・

・・・

(すでにコンテスト開始から1時間経過)

よくわからないので再度Largeを真面目に考え始める

やはりDP

モーメントの計算方法Σ(p-c)*mass(p)を変形すると、Σp*mass(p)-c*Σmass(p)

従ってある正方形のp*mass(p)とmass(p)の和を記憶しておけば定数時間でモーメントを計算できる(⇔重心が中心にあるか判定できる)

ある長方形のΣmass(p)を求めるDPは、左上隅(0,0)~右下隅(r-1,c-1)までの長方形の重さをsum[r][c]、位置(r,c)の重さをmass[r][c]とすると、sum[r][c]=sum[r-1][c]+sum[r][c-1]-sum[r-1][c-1]+mass[r-1][c-1]で計算できる

このDPを使って、左上隅(r,c)~右下隅(r+k-1,c+k-1)の正方形の重さを求めるには、sum[r+k][c+k]-sum[r][c+k]-sum[r+k][c]+sum[r][c]を求めれば良い

あとは4隅の重さを引けば求めたいものが求められる

Σp*mass(p)はr成分とc成分に分けるとやはり同様に計算できる

DP部分の計算はO(R*C)

あとは正方形の位置と大きさを定めれば定数時間でモーメントが計算できるので、計算量はO(R*C*min(R,C))≒500^3程度


というDPを書くのにバグりまくってとんでもないことになった

mass[r][c]を事前計算せず混乱してしまったのが大きな過ちだった

提出時間:Large 1h44m41s


ソースコード

続きを読む

Google Code Jam 2011 Round 2 C Expensive Dinner

| 21:25 | Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) Google Code Jam 2011 Round 2 C Expensive Dinner - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

取り掛かった時点で残り45分

とりあえずウェイターを呼んだ回数=客が注文した回数かと思い20分ほど考えたが全然分からない

よくよくExplanationを読んだところ、全然注文した回数とcallした回数が一致してない

再度問題をよく読むと、客が入ってきた時点で新しいウェイターが呼ばれ、全員満足するまでその人が注文を受け付けるらしい

ということは一人のウェイターが最大何回注文を受け付けるのか、の最小と最大を求めるのか

でも合わない

さらに20分くらい経って、ようやくウェイターが呼ばれるのが客が入ってきたときだけだということに気づいた

この時点で残り5分

とりあえずNから1の順と1からNの順でlcmを取って差分を求めてみた

そもそもlcmがオーバーフローして話にならない

だめだ

終了


後で

そもそも読み違えすぎ。(問題自体も分かりにくいと思うのだが・・)

「新しい客が入店時ウェイターを呼ぶことになる回数を求める」とか書いてほしかった


Aさんが入店したときに、それまでのlcmをLとしてlcm(A, L)!=Lのとき、ウェイターが呼ばれることになる

別の言い方をすると、Aを素因数分解して、Lの素因数分解に含まれないものがあった場合ウェイターが呼ばれる

最終的には、lcm(1~N)がトータルコストになるので、これを素因数分解することが重要

lcm(1~N)を素因数分解して、指数が1のものはその素数をもつ人が入店したときにウェイターが呼ばれ、それ以降呼ばれない

指数が2以上のものは、それまでに指数がnだったとすると、nより大きい指数をもつ人が入店したときにウェイターが呼ばれる

従って指数が1->2->3->...->nの順に呼ぶと最大でn回ウェイターが呼ばれ、逆順だと最小で1回しか呼ばれない

指数が2以上のものを対象に計算するので、√Nまでの素数を全て求め、N以下の最大指数を求めれば、(指数-1の和)+1が答えとなる

(最後の+1は、最初に1の人が入店すると+1されるため)

N==1のときだけ例外で、解は0となる


ソースコード

続きを読む

Google Code Jam 2011 Round 2 D A.I. War

| 21:25 | Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) Google Code Jam 2011 Round 2 D A.I. War - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

基本的にはBFSで最短路を求める問題

threatenされた星は次の星かその次の星までに再度threatenの対象として現れうるが、それ以降現れることはない

(なぜなら、3つ以上先に同じthreaten対象の星が現れた場合、threaten対象の星を通ったほうが最短路になってしまうから)

従ってとりあえず2つ前の星までのthreaten対象を覚えながらBFSすればそんなに状態は爆発しない


公式の解説では、2つ前の星までのthreaten+conquer数を覚えるDPが載っていた。

確かにconquer数は後で引けばいいので、そのほうが書きやすそう。

DPの方が簡単に書けて効率もよさそうですね。


続きを読む

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

2011-06-03SRM508 Div1

  • 250:208.13, 500:Opened, score:208.13, rank:217, rating:2035(+6)
  • 250がすぐ解けていい感じだったが500で少しハマり勿体無い終わり方だった

SRM508 Div1 250 DivideAndShift

| 23:17 | SRM508 Div1 250 DivideAndShift - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM508 Div1 250 DivideAndShift - SRM diary(Sigmar) SRM508 Div1 250 DivideAndShift - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは・・・DivideとShiftの操作は可換だ。ピンと来た

これが分かったら解けたも同然だな

エラトステネスの篩で素数を生成しておいて、再帰的にNを素数で割っていく

各Nの最小手数をメモ化しておけば計算量は問題ない(Nが決まればMが決まるため、状態数は100万程度しかない)

書いた

サンプル合った

提出

多少実装と可換の確認に時間を食ったがそこそこ早めに解けた


ソースコード

続きを読む

SRM508 Div1 500 YetAnotherORProblem

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

Problem Statement

コーディングフェーズ

すぐに分かるのは、各ビットにつき1が1つ以下でなければORとADDが一緒にならない

1つずつ要素を加えていくDPをすると10^18のメモリが必要

うむ、全然分からん

どう考えても要素数が10しかないことを利用するんだろうが・・・

1桁ずつDPとかできるのかな・・・

各要素の最大値が決められているというのが扱いにくい

最大ってどうしたらいいんだ・・・

(何か色々迷走、終了10分前くらいに解法を思いつく)

上位の桁から順番に、全要素のビットを確定していけばいいのでは

例えば、10100という5桁の2進数があったとする

最初の桁を0にすると、下の4ビットは最大値1111で任意の数字を選択できる

最初の桁を1にすると、下の4ビットは最大値0100でそのまま残る

0100という4桁の2進数があったとする

最初の桁は0しか選べず、下の3ビットは最大値100でそのまま残る

このルールさえ分かれば、後はDP可能だ

各要素につき、任意のビットが選択可能になっているかを記憶すれば良い

各桁につき、1になるのは最大1つなので、せいぜい11分岐、次のビットマスクの生成コストが10であるから、

計算量は約60*2^10*11*10=6600000くらいと全然余裕

ここまで分かった時点で残り5分

コーディングは大したことないので何とかなるか?

頑張って書く

合わない

終了

くっ・・・


ソースコード

微修正で答え合った

続きを読む

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