2010-02-07
SRM460 DIV2 Level One(250pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=10769&rd=14146
『Yes/Noで答えられる質問のリストがある。リストには全く同じ質問が複数含まれる可能性がある。リストの順に質問をするとき、答え手の解答が何通り考えられるか。同じ質問には常に同じ解答を返すものとする。』
質問の数nをカウントし、2^nを返すだけです。質問はcase sensitiveなので、JavaならSetによる自然順序付けを利用すればコンパクトに解答できます。
SRM460 DIV2 Level Two(500pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=10772&rd=14146
『世界的に有名なJohnとBrusが都市を訪れてファンと会う。JohnとBrusは1つの都市だけを訪れることが許され、都市ごとに会えるファンの期待値が一様分布で与えられている。このとき、JohnとBrusが同じ数のファンに会う確率を求めよ。』
「Johnがi人のファンに会う確率Ji」「Brusがi人のファンに会う確率Bi」をそれぞれ求めることで、2人がi人のファンに会う確率Si=(Ji*Bi)を求めることができます。最後に[1,50]の範囲でSiの和をとり、解答とします。
SRM460 DIV1 Level One(250pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=10768&rd=14146
『インタビュアーが質問の順番を記録したリストを紛失してしまい、回答のリストと質問の個数、質問の内容だけが残っている。インタビュアーは同じ質問を何度かする可能性があり、同じ質問に対しては常に同じ答えが返ることが保証されている。質問リストの順序が取りうる組み合わせを求めよ。』
Yesと答える質問の個数をyQuestion、Noと答える質問の個数をnQuestion、Yesという回答の個数をyes、Noという回答の個数をnoとすると、その組み合わせは「yes個の回答をyQuestions個の質問に割り当てる組み合わせ」×「no個の回答をnQuestions個の質問に割り当てる組み合わせ」×「質問の並べ方」で表現できます。
先月読んでいた離散数学「数え上げ理論」の6章で出てきた「おみやげを必ず1つはもらえるように配る」考え方を流用し、スターリング数を用いて実装しました。
2010-02-06
SRM410 DIV1 Level Three(1000pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=9733&rd=12182
AWTを使い、低速だが簡潔なコードを実装。x,yがそれぞれ10^9に到達することから考えても、単純な数えあげでは実装できないようです。ビット演算を使うべき？
2010-01-31
SRM410 DIV1 Level One(250pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=8817&rd=12182
『電子回路のノードとその相互接続状況が与えられる。ノードのうちいくつかは電力網（electrical grid）に接続されている。電力網に接続されたノード同士が直接・間接的に接続しないという条件下で、追加できる最大の配線数を求めよ。』
電力網に接続されているノードから接続を伝って到達可能なノードを「ノードグループ」と名づけ、同じノードグループに属するノードは相互接続して良いことから総数を求めました。どのノードグループにも属していないノードは最大のノードグループに属させることで、求められている「最大の配線数を求める」ことを可能にしています。
2010-01-28
SRM411 DIV1 Level Three(1000pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=7620&rd=12183
時間切れで解答失敗。TopSubmissionも存在しないため、自力で到達したコードを残しておきます。
2010-01-25
SRM411 DIV1 Level Two(500pt.)
http://www.topcoder.com/stat?c=problem_statement&pm=9752&rd=12183
『中央に四角い穴が開いた四角いケーキがある。これをX軸・Y軸それぞれに平行な線で切るとき、いくつのケーキ片ができるか求めよ。』
穴の存在によってパターンがやや複雑になっています。穴にかかる2本の平行線を引くと、その線と穴によって2つのケーキ片ができるためです（穴がなければ1つ）。はじめに実行している配列変数の初期化がややこしく見えますが、渡された配列にケーキの端を表す座標を追加した上でソートしているだけです。