問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11348&rd=14433最初にH*Wの盤面が黒（'B'）か白（'W'）で塗られており、下の処理を経た局面がvector stringで与えられる。 For i = 0 to H-2: For j = 0 to W-2: //Get the current colors of ce…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10835&rd=14432街と村が存在し、それらの位置が与えられる。最初、村には道が通っていない。街と村の間に道路を引くか、街に行くことのできる村とそうでない村の間に道路を引くことでどの村も少…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11352&rd=144310〜N-1の数字からK個選んだものの和がNで割り切れるような選び方の総数をもとめよ。 やりかた Writer解を参考にしました。DP。 dp[i][j][k]:=(i番目の数字まででk個選んだ時の和の…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11331&rd=14428vector string が与えられる。各文字列の長さは等しい。各文字列には点数が割り当てられており、この文字列から複数を取り出してそれらを任意の順で結合した文字列がもし回文とな…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11225&rd=14427ピラミッド型の8パズルの初期局面とゴールとなる局面が与えられる。任意のピースを任意の回数動かして初期局面からゴールとなる最終局面まで遷移したい。遷移できないときは初期局…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426同じ文字列を２つ結合してできた文字列をSquareな文字列という。文字列Sから好きな文字を取り除く、変更する、挿入するという操作を行うことでSquareな文字列にするための最小の操…

問題 http://community.topcoder.com/stat?c=problem_solution&rm=318227&rd=15698&pm=12691&cr=23058389 (y[0], 1) (y[1], 2) (y[3], 3)・・・となるようなvector int yが与えられる。これらの点を順につないでいき、直線の関数のつなぎあわせをつくる。y =…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11296&rd=14425大文字アルファベットからなる長さNの文字列を想定する。この文字列中に回文となる長さMの部分文字列がK個以上あるとき、この文字列をPalindromefulな文字列という。N、M、Kが与え…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11303&rd=14424正六角形を組み合わせた三角の形をしたタイルがある。このうちのいくつかの正六角形はlocked、死んだ状態にあり、それ以外の正六角形は各々ことなる色で塗られている。同じ頂点を…

問題 http://www.topcoder.com/stat?c=problem_statement&pm=11309 やりかた 木の高さはそれぞれ独立なので、隣合う木の高さの差の期待値を足していけばいい。独立なら和の期待値は期待値の和。以下ソース。 class AlternatingLane { public: double sum(int…

問題 完全２分木がある。すべての頂点を一度だけ通るような最小パス被覆のサイズを求めよ。木の高さは60以下 やりかた という感じで3つのノードでひとつのパスというふうにした時パス数は最小となる。 なのでceil(頂点数/3)。以下ソース。 class TrafficCong…

問題 http://poj.org/problem?id=1338 2,3,5のみが素因数の数をUgly number という。便宜上１もUgly number とする。n番目のUgly number を求めよ。n やりかた プライオリティキューに生成した数を入れていきながら幅優先探索。要long long。 setに発見した…

問題 http://poj.org/problem?id=2262４以上の偶数は２つの奇素数の和で表せるという予想をゴールドバッハ予想という。入力nに対しそのような２つの奇素数を返せ。複数ある場合は絶対値の差が最大になるペアを返せ。 やりかた エラトステネスの篩をしたあと…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11049&rd=14245N個の街があり、セールスマンが街0にいるとする。N個の街の間の道の情報がvector string で与えられる。これを一つのstringに結合した時に"a0,b0,cost0 a1,b1,cost1 ......"という…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=11008１〜Nまでの間でleft[i]〜right[i]の間の数字の内、damage[i]で割り切れる数字を消去する。全部で消去される数はいくつか？ やりかた 包除原理。まずは1~Nの整数に中でdamage中の少な…

問題 N人の人間がいて、おのおの金を持っている。彼らの友好関係がvector string で与えられる。i番目の行のj番目が'Y'ならiとjは友人。'N'なら友人ではないとする。そして直接の友人間では持ち金の差は大きくともdとなるように調整されている。N人の持金の…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10746&rd=14240 自然数z, nが与えられる。 xを入力として、x + y^2 + z^3 = n (mod n)となるようなyを出力する機械がある。ただしyは1からnまでの間の数で、複数ありうる場合は任意のものを出力…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11130&rd=14237互いに区別できる立方体の頂点に色を塗りたい。良い塗りとは隣あう頂点が異なる色で、かつそれぞれの頂点にふさわしい色が塗られている時である。ふさわしい色はvector colorsで与…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11073&rd=142361未満の小数numberが与えられる。A / Bとnumberの、整数部から連続して一致する桁数がもっとも長くなるような自然数A、Bを探せ。ただし分母の最大値はmaxDen以下で、答えが複数あ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10808&rd=14234バッチシステムであるジョブiをこなすのに必要な時間duration[i]とこの仕事をおこなう者の名前user[i]が与えられる。user[i]が与えられた仕事を終えるまでに待たねばならない時間…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11059&rd=14159vector int numbersが与えられ、ここからある文字列を作る。numbers[i]を文字列に組み込むとは、文字列の2のべき乗番目から連続してnumbers[i]個の1を組み込むという行為になる。…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=10562 箱がN個あり、箱iにある赤りんごの数と青りんごの数がそれぞれred[i], green[i]で与えられる。この複数の箱から空集合を除く箱の部分集合を選んで、それらの選ばれた箱にあるすべての…

問題 http://apps.topcoder.com/wiki/display/tc/SRM+476YのあるsubstringのアナグラムがXになるとき文字列Xが文字列Yのsubanagramであるという。いくつかの文字列がvector stringで与えられる。これらの文字列を結合した文字列Sをn個に分割したい。ただしS1…

問題 ２次元平面上に点が複数あり、それらの位置x[i], y[i]が与えられる。この点を複数種類の正方形で全て覆うことを考える。正方形jの幅はsides[j]で与えられる。正方形jを一つ配置するコストはcost[j]である。正方形はどの種類も無尽蔵にあるとする。全て…

問題 http://apps.topcoder.com/wiki/display/tc/SRM+473自然数Xの桁ごとの数の和をD(X)とする。X / D(X)が割りきれる時これをYとし、YはXの親、XはYの子と呼ぶことにする。自然数AからBの間に子のない自然数はいくつあるか。 やりかた 制約にB - A A ~ Bの…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10945&rd=14154width * height のグリッド上の(x,y)にあなたが立っている。一回の移動で上下左右のセルに同じ確率で動ける。steps回移動した後にグリッドから落ちていない確率を求めよ。 制約はw…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153数字が書かれたvector stringが与えられる。はじめは左上のみがアクチベートされている。毎ターンアクティブなセルとそれに隣接するアクティブでないセルをひとつずつ選んで、そこ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10903&rd=14152JohnとBrusはN本の映画をレビューする。JohnとBrusが映画iを視聴するのにかかる時間はそれぞれtimeJ[i]、timeB[i]とする。まずN本の映画をJohnとBrusに配り、Johnが映画を見終えた…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10695&rd=14151 迷路が与えられる。'#'は壁で、'F'は火、'.'は何もないセル、'$'がプレイヤーのスタート地点である。プレイヤーはスタート地点から出発して毎ターン上下左右の隣接セルで壁か火の…

問題 魔法少女たちがおり、彼女らの力がvector int で与えられる。敵が複数おり、強さenemyStrength[i]の敵がenemyCount[i]匹いる。魔法少女達は自分と同じか自分より弱い敵を倒すことができ、一体倒すにつき疲労度が+1される。敵をすべて倒した時にもっとも…