Hatena::Grouptopcoder

shnyaの参戦記録

2011-06-14練習

ちっともMedium解けるようにならない・・・。

Member SRM 461 Div1 Easy ColoringRectangle 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10731&rd=14181:title=Member SRM 461 Div1 Easy ColoringRectangle] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10731&rd=14181:title=Member SRM 461 Div1 Easy ColoringRectangle] - shnyaの参戦記録

大きさが違う赤の円盤n枚と、こちらも大きさの違うk枚の青の円盤を順番に並べた時に、最小となる枚数を答えよという問題。

貪欲に実装すればいいだけなんだけど、実装が微妙な感じになってしまった。

続きを読む

Member SRM 461 Div1 Medium BuildingCities 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10732&rd=14181:title=Member SRM 461 Div1 Medium BuildingCities] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10732&rd=14181:title=Member SRM 461 Div1 Medium BuildingCities] - shnyaの参戦記録

(x,y)平面上に都市がならんでいて、1日に距離r以内の都市に移動できるとする。

既に存在している各都市の位置を配列で与えられた時、最初の都市から最後の都市までにn日以内に辿りつくためには、追加で最小いくつの都市を建築しないといけないか。


新たな都市を建築するのは、都市iから都市jに距離rで辿りつけない場合だけを考えればよい。

(これは思いついた。)

しかし、n日以内に辿りつけるという条件のもと、最小の建築数を考える方法はすぐにはおもいつかず、二分探索とかも考えたが不適。とりあえず、ダイクストラでN-bestを列挙する感じで書いてみるもTLE。答えを見ると、適当に枝狩りすれば良さそうな感じだった。


続きを読む

SRM 460 Div1 Easy TheQuestionsAndAnswersDivOne 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146:title=SRM 460 Div1 Easy TheQuestionsAndAnswersDivOne] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146:title=SRM 460 Div1 Easy TheQuestionsAndAnswersDivOne] - shnyaの参戦記録

前に解いた問題。

質問数と、それに対して回答者が各質問に対してYesとNoを答えた履歴を教えてくれる。

重複して質問した可能性もあるとすると、何通りの質問の仕方が考えられるだろうか?

配列の大きさが小さいので全探索でOK.

続きを読む

SRM 460 Div1 Medium TheFansAndMeetingsDivOne 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10771&rd=14146:title=SRM 460 Div1 Medium TheFansAndMeetingsDivOne] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10771&rd=14146:title=SRM 460 Div1 Medium TheFansAndMeetingsDivOne] - shnyaの参戦記録

前に解こうとした問題。

合った人数ごとの確率をDPで求めれば良い。

続きを読む

SRM 459 Div1 Easy Inequalities 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145:title=SRM 459 Div1 Easy Inequalities] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10682&rd=14145:title=SRM 459 Div1 Easy Inequalities] - shnyaの参戦記録

「x < 3」のような不等式及び等式が与えられるので、その条件を最大いくつ満たすことができるかという問題。

探索範囲が少ないので、やるだけ、な問題。


続きを読む

SRM 459 Div1 Medium NumberPyramids 01:26  [http://www.topcoder.com/stat?c=problem_statement&pm=10683&rd=14145:title=SRM 459 Div1 Medium NumberPyramids] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10683&rd=14145:title=SRM 459 Div1 Medium NumberPyramids] - shnyaの参戦記録

むずかった。

    15
   6  9
  3  3  6
2  1   2  4

のように頂上の数字を2分割してできる数字のピラミッドがあるとする。

頂上の数字Nと、最下段の数列の長さBaseLengthが与えられた時、何通りの組み合わせが考えられるか?


とりあえずNの範囲からBaseLengthが20以上の時は成り立たないことがわかる。

20以下の場合だけを考えてよい。

組み合わせの数を効率的に計算する方法が思いつかず断念。(最近こればっかりだな・・・)

最下段の最上段への影響は二項定理の係数と同じだけの重みになっている。

3段の場合、一番左の数字が1増えると頂上の数字も1増える。左から2番目の数字が1増えると頂上の数字は3増える、といった具合。

そのため、最下段の数について、頂点がNとなる全てのありうる数をかんがえることになるが、その組み合わせ数はDPを使って効率的に計算できる。

うーん、ひとひねり(k > 20の時は考えなくてよい)+もうひとひねり(2項定理の係数)+DPというのは、手がでてないなぁ・・・。。

続きを読む

2011-06-07練習

ちょっとした更新を使って上にあげてなかったのに間違ってあげてしまった。

練習としての自分用のメモなのでスルーしてください。

SRM 462 Div1 Easy AgeEncoding 02:08  [http://www.topcoder.com/stat?c=problem_statement&pm=10589:title=SRM 462 Div1 Easy AgeEncoding] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10589:title=SRM 462 Div1 Easy AgeEncoding] - shnyaの参戦記録

年齢ageをB進数で表した時、candlesLineという"010001"のような文字列にエンコードされる。

ageとcandlesLineが与えられた時に基数Bを答えよ。

Bは、実数。

最初は解析的に解けるかなーとちょっと考えてたけど、無理っぽかったので方針変更。単調増加なので2分探索で解く。

Div1の人間でも10%しか通っていない罠に自分もまんまとはまった。

続きを読む

SRM 462 Div1 Medium CandyBox 02:08  [http://www.topcoder.com/stat?c=problem_statement&pm=10744&rd=14147:title=SRM 462 Div1 Medium CandyBox] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10744&rd=14147:title=SRM 462 Div1 Medium CandyBox] - shnyaの参戦記録

得点の違う飴がC個づつ、N個の箱に入っている。初期状態はスコアの違う飴は各箱に別れて置かれているが、S回任意の飴2個を選んで交換を行った時に、最終的に各箱の期待スコアはどうなっているか?

交換は完全にランダムとする。


Sの個数が普通にシミュレーションするだけではTLE解けないとばかり思っていて、答えを見てしまって、実はシミュレートで十分間に合うのか・・・。

ちゃんと問題を見返そう。

1問1問大事に解いていかないと意味がない。

続きを読む

SRM 508 Div2 Hard YetAnotherORProblem2 02:16  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437:title=SRM 508 Div2 Hard YetAnotherORProblem2] - shnyaの参戦記録

1 <= a_i <= Rの整数からなるN個の配列がある。

a_1 | a_2 | ... | a_n-1 | a_n = a_1 + a_2 + ... + a_n-1 + a_nとなるような並びは何通りあるか。

(|はOR演算)


ビットDPかなぁと思って考えてみるも、空間計算量がO(NR^2)ぐらいになってしまってちょっと厳しいなぁと思い、考え続けるも答えが出ない。


なんとか次元をひとつ落とせばなんとかなるかなぁといいなぁと思いつつも浮かばない。解いた人のコード見て、あぁ、こういう風に解けばいいのかと納得した。

ビットの部分集合を列挙するループの書き方はSigmarさんのブログを参考にしました。

http://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966

続きを読む

2011-06-06練習&一部本番

SRM 508 Div2 Easy CandyShop 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=11439&rd=14437:title=SRM 508 Div2 Easy CandyShop] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11439&rd=14437:title=SRM 508 Div2 Easy CandyShop] - shnyaの参戦記録

場所がわからなくなったキャンディショップを、記憶を頼りに探す問題。具体的には、過去に訪れた場所(x,y)と半径何m以内(マンハッタン距離)の場所にあったかという情報を、訪れた回数分与えられる。

キャンディショップの候補となる場所は、上記の情報で得られたポイント(整数の格子状の点)の積集合である。

候補となる場所の数を答えよ。

これほんとにDiv 2 Easy?という感じに難しかった。

ポイント
1 <= R <= 100なので、各回ごとに1万ポイントが候補としてあげられる。普通にO(n^2)で積集合をとるとTLE。

模範解答としては、先に300x300の地図の中から、条件に合致しない点(候補とならない点)にダメマークをつけていき、生き残った場所を数える。

下は単純にシミュレーションをした回答。

上記のTLEな問題(Div2 EASYでTLEが問題になるとは思わなかった)に加えてset_intersectionの前にsortを忘れて3回もサブミットしちまった。。。

続きを読む

SRM 508 Div2 Medium DivideAndShift 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=11434&rd=14437:title=SRM 508 Div2 Medium DivideAndShift] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=11434&rd=14437:title=SRM 508 Div2 Medium DivideAndShift] - shnyaの参戦記録

N個のポイント上のM個目の場所に目的の石がある。

これをなんとか1個目に持って行きたい。

ただし、行うことができる操作は全体を素数で割ること(目的の石が含まれる区間だけ抜き出される)と、左か右にシフトすることのみ。

最小の操作回数を答えよ。


最初は素数リストを作るところから始める。でも素数なんていらないやと思って全部消す。

なんだかんだやって、とりあえず約数で割ってから左右に移動しても答えは同じじゃないかと考える。要は、左右の移動と割る操作の順序が可換かどうかということだけど、自信は全くないもののいけそうかなと思ってとりあえず組む。答え合わない。試合終了。


方針は合ってたっぽいけど、バグが取れなかった。慌てちゃダメ。

続きを読む

SRM 449 Div2 Medium OddDivisors 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=1854:title=SRM 449 Div2 Medium OddDivisors] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=1854:title=SRM 449 Div2 Medium OddDivisors] - shnyaの参戦記録

ふと、知り合いの参加記録を読んでいて気になった問題。

f(x)はxの最大の奇数を返す関数とした時、Nが与えられた場合に、f(1)+f(2)+...+f(n-1)+f(n)の計算結果を返せ。

ただしNは1000,000,000とする。


Nが大きいので工夫がいる。

思いついた解き方は、

1,2,3,...Nまでの数字を奇数のものと偶数のものを分ける。

Nが奇数の場合は、

1,3,5...N
2,4,6....N-1

のように分けることができる。

下段のf(x)の値は以下と等価だから、これを2^k > Nとなるまで繰り返していけばOK。

f(1),f(2),f(3),...,f((N-1)/2)

実はループもなく解析的に解ける、というかまぁ各段階の合計値は階差数列になるはずなので、普通に計算するだけだろうけど、本番だとそれが正しいことを示す(具体的な値をいくつかいれて試す)のが面倒なのでやっぱり下のように解いてたと思う。

ただ、これも各回ごとの最後の値を求めるのに手間取った。

やっぱりこういう問題は紙とペンが欲しい。

続きを読む

SRM 463 Div1 Easy RabbitNumbering 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148:title=SRM 463 Div1 Easy RabbitNumbering] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10697&rd=14148:title=SRM 463 Div1 Easy RabbitNumbering] - shnyaの参戦記録

N匹のウサギがいて、それぞれのウサギを見分けるために数字を割り振ろうとしている。

ただし、ウサギは割り当てられる数字にこだわりがあって、各ウサギごとに最大a_i以下の数字(a_iはそれぞれ異なる)でなければならない。


数字の割り当て方は何通りか?

例を見るとなんとなく方針がわかる。

{5,8}が与えられた時の答えは35通り。

2番目のウサギは1-8までの候補があるが、1番目のウサギが1-5までの数のどれかを取るので実際は7通りしかない。

1番目のウサギは5通りのとり方があるので、7 * 5 = 35

つまり大きい方から順番に計算していけばいい。

続きを読む

SRM 463 Div1 Medium Nisoku 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148:title=SRM 463 Div1 Medium Nisoku] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148:title=SRM 463 Div1 Medium Nisoku] - shnyaの参戦記録

1.5 <= ai <= 10からなるN個の実数値からなる配列ある。

それらの中から2個のペアを取り出してそれぞれの和か積を計算し、結果を元の配列に戻す。

この操作を残り1個まで繰り返した場合に、残った数が最大となる時の値を答えよ。


むずかった。Eulerで全探索で解く似た問題があったが、1 <= N <= 50のため、それもできない。DPとかも考えたけど厳しい。


1.5という数字に着目して、足した時にかけた値よりも大きくなる場合はどういう場合か考えてみる。

a + b > abなので、1/a + 1/b > 1となる場合。a,bは大きければ大きいほど1/a + 1/bは小さくなるので、1/a + 1/b > 1が成り立つのは、a=1.5, b=3などの小さい値の時だけ。こういう数字は大きくて3, 小さくて1.5となる。

なので、足した方が大きくなる数字を先に計算。残った数字をかけていけばいいのかなーと思ったけどやっぱりダメだった。システムテスト通らず。一応努力の結果として下記に記す。


足した方が大きくなる数字はどの順番に足していく方がいいかわからなかったので、とりあえず最小の2つ、最大の2つを試すがサンプルは通らない。数字の差が開くような組み合わせを選んでやるとうまくいったので、このパターンでやってみた。

続きを読む

SRM 464 Div1 Easy ColorfulStrings 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149:title=SRM 464 Div1 Easy ColorfulStrings] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10724&rd=14149:title=SRM 464 Div1 Easy ColorfulStrings] - shnyaの参戦記録

"263"のような0-9の数字からなる文字列がある。

この時、全ての部分文字列を考えると、"2","6","3","26","63","263"があり、各文字列の各桁の積が全て異なるとき、Colorfulな文字列であるという。

文字列の長さNが与えられた時、長さNのColorfulな文字列を、辞書順に並べた場合に、K番目にくる文字列を答えよ。

入力のパラメータは、以下の範囲とする。

1 <= N <= 50

1 <= K <= 1,000,000,000


最近は、電車に乗っている間に携帯で問題見ながら考えたりするんだけど、この問題は22:58に問題を開いてから23:18にヒントが思いついたのを覚えている。黄色な人たちは3~5分ぐらいで思いつくと思うけど、やっぱ手間取った。。


とにかくNやKが大きいので、全探索は難しい。かといって、K番目にくる文字列ということでDPやGreedyといったアルゴリズムも使えない。


ちょうど20分間考えたら、各数字は1回しか出ないことに気づく。

それならカラフルな文字列は最長で8文字まで。

N>8の時は存在しないということで空文字列を返せばOK。

N<=8なら全探索で求めることができる、ので帰ってから書いた。

見事にN=1の場合にはまった。

続きを読む

SRM 465 Div1 Medium GreenWarfare 23:18  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium GreenWarfare] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium GreenWarfare] - shnyaの参戦記録

前回解いてなかった最大フローの問題。

プログラミングコンテストチャレンジブック読んで、最大フローを理解しながらちゃんと書いてみた。かなり高速に計算できて、すげーとか思った。

これでライブラリが1つ増えた。

続きを読む

SRM 271 Div2 Easy CheckFunction 23:43  [http://www.topcoder.com/stat?c=problem_statement&pm=4788&rd=8068:title=SRM 271 Div2 Easy CheckFunction] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=4788&rd=8068:title=SRM 271 Div2 Easy CheckFunction] - shnyaの参戦記録

"032"といった文字列をデジタル数字で表現した時に、何本の線が必要かを数える問題。

ただカウントするだけ。

続きを読む

SRM 271 Div2 Medium BlackWhitePlane 23:43  [http://www.topcoder.com/stat?c=problem_statement&pm=4497&rd=8068:title=SRM 271 Div2 Medium BlackWhitePlane] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=4497&rd=8068:title=SRM 271 Div2 Medium BlackWhitePlane] - shnyaの参戦記録

N個の円があり、いくつかの円は、さらに大きな円の内部に完全に内包されている。

最初の背景は黒で、その上にある円は白で塗られる。円の中にさらに円がふくまれている場合は、背景が白の場合は黒、背景が黒の場合は白で塗っていく。

白で塗られた面積を答えよ。


深さは最大2段だとばかり思っていて、System Test Failed。。。

続きを読む

2011-06-01練習

SRM 465 Div1 Easy 00:38  [http://www.topcoder.com/stat?c=problem_statement&pm=10840&rd=14182:title=SRM 465 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10840&rd=14182:title=SRM 465 Div1 Easy] - shnyaの参戦記録

二次元平面上にN個のポイントがある。

そのポイントの中から2個のポイントを選んで、それぞれに1辺kの正方形でできた見張り塔を建てる。それぞれの見張り塔の大きさは異なってもよいしそれぞれの角度も自由にしてよいとする。

ただし、見張り塔がそれぞれ重なってはいけないとする時、見張り塔の建方はいくつあるか、という問題。

2点間の距離が最大となるのは、それぞれが正面となる角度で向き合った時。距離をdとして、各見張り塔の1辺のサイズをa,bとすると、

  a/2 + b/2 <= d

となる建て方があり、これを満たすa,bのペア数は2d(2d-1)/2となる。


これを全ての点で求めれば良い。

続きを読む

SRM 465 Div1 Medium 00:38  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10792&rd=14182:title=SRM 465 Div1 Medium] - shnyaの参戦記録

まだ解けてないけど、覚えておくために。

DPは、(bitDP)のように全ての状態を覚えておく必要があるが、要素数が50のため無理。

うまく貪欲にできないかなーと思ったり、枝狩りした探索をしようとかいろいろ考えたけど、枝狩りの条件がわからない。


結局Editorialを見ると、最小カットで解く問題だったようだ。

正直最小カットを理解してなかったので、この問題で理解が進んだ。

コーディングも後でする。

SRM 466 Div1 Easy 00:38  [http://www.topcoder.com/stat?c=problem_statement&pm=10862&rd=14150:title=SRM 466 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10862&rd=14150:title=SRM 466 Div1 Easy] - shnyaの参戦記録

最大10桁の数字を書き換えて、奇数個の約数にできるかどうか、という問題。正直、約数の個数が奇数の場合、二乗の場合だけということを気づかなくて、かなり悩んだ。。。。


それさえわかれば答えはすぐに書ける。

続きを読む

2011-05-31練習

うーん・・・、今回は全体的に自力で解けてなくてよくない。。。

SRM 470 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153:title=SRM 470 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10735&rd=14153:title=SRM 470 Div1 Medium] - shnyaの参戦記録

上下にn個づつ点があり、上下の点同士をランダムに結んでいった時、直線の交わる数の期待値を求める問題。

一部の直線は最初から引かれている。

解き方わからなかった・・・。DPっぽくできるかな?と思ってたけど、そう甘くなかった。正解のひとつは上部の2点のペアを全て列挙し、各ペアごとに確率を計算、加算していく。

続きを読む

SRM 468 Div1 Easy 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10762&rd=14183:title=SRM 468 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10762&rd=14183:title=SRM 468 Div1 Easy] - shnyaの参戦記録

T9入力をシミュレートする問題。各文字入力ごとに候補を絞り込むように計算してSubmit、Failed System Test。。

#文字の入力があった時の挙動が間違えてた・・・。

続きを読む

SRM 468 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183:title=SRM 468 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10765&rd=14183:title=SRM 468 Div1 Medium] - shnyaの参戦記録

0 - N-1までの各都市をそれぞれ、自動車を使うか、飛行機を使うかを選択して、目的地に着く時間を最小にする問題。ただし飛行機を使えるのはk回まで。連続して飛行機を使う場合はkを消費しない。


DP・・・は、メモリ使用量的に厳しい。

差分配列を考えれば、その中で部分和が最大となる範囲は、珠玉のプログラミングに書かれている分割統治法で求められO(nlogn)*Kで間に合うはず、ということでプログラミング。

いくらやってもシステムテストが通らない・・・orz

で、結局あきらめて、通らなかったコードが下。

続きを読む

SRM 467 Div1 Easy 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10823&rd=14151:title=SRM 467 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10823&rd=14151:title=SRM 467 Div1 Easy] - shnyaの参戦記録

教授がくるのが遅いので、定期的に抜けだして遊んでいた場合、抜けだした時に運悪く教授がくる確率を求めよ、という問題。

問題自体は一見簡単。

でも引っ掛けがひどい。。。

この問題の正解率が低い理由がすごくわかる。。

でもまぁこの問題に限らず、練習でもSystem Test Failedばっかりなのでなんとかしていきたい。。

頑張れば条件分岐だけで、ループ使わずにいけると思うけど、ループ使った方が記述がシンプルになるので使ってみた。

続きを読む

SRM 467 Div1 Medium 00:35  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10239&rd=14151:title=SRM 467 Div1 Medium] - shnyaの参戦記録

下記の式で与えられるSuperSumを求める問題。

SuperSum(0 , n) = n, for all positive n.
SuperSum(k , n) = SuperSum(k-1 , 1) + SuperSum(k-1 , 2) + ... + SuperSum(k-1 , n), for all positive k, n.

1 <= k <= 50
1 <= n <= 1000000000

ノートに向かって1時間程悩むがギブアップ。Editorial見ると答えはパスカルの三角形になっているらしい。。。

こういう問題の場合、小さい集合で簡単にコード書いて計算してみるのがよさそうな気がしてきた。

剰余ライブラリは下記URLに書かれた先輩方から頂きました。

http://topcoder.g.hatena.ne.jp/n4_t/20100416/1271392320

http://topcoder.g.hatena.ne.jp/cafelier/20100416/1271391378

続きを読む

SRM 466 Div1 Medium 03:44  [http://www.topcoder.com/stat?c=problem_statement&pm=10863&rd=14150:title=SRM 466 Div1 Medium] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10863&rd=14150:title=SRM 466 Div1 Medium] - shnyaの参戦記録

N行5列の各セルごとに重複なく数字が書かれたくじがあり、ランダムに5個の1<k<5*Nとなる数字を選んだ際に、1行に3個以上選ばれた数字があった場合は当たりくじとなる。

Nが与えられた時、くじの当たる確率を求めよ。

この問題は、あまり確率系の問題が得意とはいえないのに一発でアクセプトされてちょっと嬉しかった。

くじが当たらない組み合わせは、

(1個の数字が選択された行数, 2個の数字が選択された行数) = (5,0)
(1個の数字が選択された行数, 2個の数字が選択された行数) = (3,1)
(1個の数字が選択された行数, 2個の数字が選択された行数) = (1,2)

の3通りだけ。ので状態数も少ない。

まだ1つも数字が選択されていない行から数字が選択された場合と、1個の数字が選択された行で再度選択された場合でそれぞれ再帰する。

全探索してもたかだがO(2^5)程度なので、全探索で解く。

続きを読む