問題 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される。敵をすべて倒した時にもっとも…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10861&rd=14150'1'か'0'を要素に持つvector string が与えられる。行か列の交換を好きなだけ行なって辞書順最小のものを返せ。 やりかた まず列の入れ替え方を全順列で試してみて、その中で行の…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10760&rd=14148N枚のカードがあり、各カードには1.5から10.0までの数字が書かれている。このうちから2枚選んで取り出してカードに書いてある数字を足した数かかけた数を新しいカードに書いてその…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10747&rd=14181一列に文字が並んでおり、カーソルを左右に動かしてエンターを押すことで文字が入力できる。カーソルは文字列の右端から左端、左端から右端へ一回の移動で遷移する。入力したい文…

問題 http://poj.org/problem?id=1583 文章が与えられる。最も出現頻度が高い単語を列挙し、かつ頻度を求めよ。 やりかた 連想配列に放り込んでいき、最頻度のstringを保存していけばいい。 int main(){ string s, t; while(cin >> t) s += (t + " "); strin…

問題 http://poj.org/problem?id=1455 n人が車座になって座っている。一回の席交換で隣り合う二人が入れ替わる。はじめとは逆順に座るためには席交換を最小で何回行えばいいか。 やりかた n人を半分こしてそれらごとにひっくり返せばいい。 1234|5678 → 4321…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10774&rd=14146グラフが与えられる。これを全域木にするような辺の加え方の集合はいくつあるか。 やりかた （説明が間違っていそうです。） practice roomの回答を参考にしました。 全域木とする…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10723&rd=14145いくつか島がある。ある人がある島からスタートして、島と島を結ぶ道をK回通ってゴールとなる島へ行きたいとする。 vector landingsが与えられ、landings[i][j]が'1'のとき、島iか…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10698&rd=14180を満たすような自然数の組はいくつあるか。ただしこれらの数字の下限、上限はminx, miny, minz, maxx, maxy, maxz（～1000,000,000）で与えられる。 やりかた 一変数を固定すると…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10694&rd=14144正数n, kが与えられる。正六角形×6のハニカムのマス目に1～nまでの数字を埋めていく。隣り合うセルの数字a, bがa % k != b % kとなるように全てのセルに数字を埋める方法は何通り…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10563&rd=13909n本の棒の長さが与えられる。好きな棒を好きな長さにC回まで切ることができる。その時にK番目に長い棒の長さを最大化せよ。なおK本以上の棒が出来るまでは必ずカットを行う。 やり…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=10717'.'か'0'のどちらかの要素を持つグリッドをまず計算する。辺の長さが3以上で辺が全て'0'である長方形の数を求めよ。頻出問題っぽい。普通にするとO(n^4)で間に合わない。まずはある座…