問題 ２次元平面上に点が複数あり、それらの位置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=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)で間に合わない。まずはある座…

問題 http://community.topcoder.com/stat?c=problem_statement&pm=6555各マスについて右と下のセルと連結しているか調べ、連結していれば距離は1、そうでなければINFとする。あとはWarshall-Floydで最短距離を求めて開始点Sからの距離がfuel以下のセルを数…

持ち上げられるクレーンの重さでソートし、荷物を持ち上げることのできるクレーンで使用回数（秒数）がもっとも少ないものに順繰りに荷物を割り振っていく。最終的にもっとも使用したクレーンの回数が答え。 int minimumTime(vector <int> cranes, vector <string> boxes)</string></int>…