問題 自然数Nが与えられる。N 1から数えてN番目に出現する回文形式の整数を返せ。 やりかた ある桁数の整数中に回文整数がいくつあるかというと、 1桁：1 ～ 9 9個 2桁：11 ～ 99 9個 3桁：101 ～ 999 90個 4桁：1001 ～9999 90個 5桁：10001 ～ 99999 900個…

問題 やりかた 与えられる文字列の長さはせいぜい12文字なので、全探索でも1ケースあたり程度の計算でOKなので全探索で。 ただvectorやstringを引数に関数の値渡しをすると簡単にTLEしてしまった。参照渡しにしたら簡単に通った。以下ソース。 vector<ll> c(5); </ll>…

問題 無限に続く階段があり、あなたはその0段目にいる。あなたはN回行動を起こし、i回目(1-indexed)の行動では+i段上に進むか動かないかを選べる。しかしbadStep段目が壊れていて、この段に立つことはできない。到達できる最上段を求めよ。 やりかた 毎回上…

問題 うなぎが複数匹おり、i番目のうなぎは狐の眼前をt[i]秒からt[i] + l[i]秒にかけて通過していく。狐は2回うなぎを獲ろうとし、1回の試行で眼前を通過しているうなぎを好きなだけ獲得できる。最大獲得数を求めよ。 やりかた 調べるべきポイントは各うなぎ…

問題 3*Nの要素を持つ配列strengthが与えられる。この要素を3つずつN個のグループに分ける。最初の3つの要素をまとめたものがあなたの所属するグループである。グループの強さはグループのstrengthがx,y,zだとすると max(x,y,z) + min(x,y,z) で決まる。残り…

問題 箱がN個あり、i番目の箱には赤色のボールがred[i]個、緑色のボールがgreen[i]個、青色のボールがblue[i]個入っている。すべての箱に対して、それぞれの箱に入っているボールの色数が必ず１色以下になるようにボールを他の箱に移動したい。動かす最小の…

問題 グリッドが与えられる。各セルは以下のようになっている。 # ： 壁。通過できない。 $ ： スタート地点。 1～9 ： スライムがいる地点。あなたはグリッド上のスライムを殺して回ることが仕事である。あなたは1ターンごとに上下左右のセルに移動するもの…

問題 x軸かy軸に平行な線分をいくつかくみあわせたヒエログリフが2つ与えられる。ヒエログリフは線分同士が交差したり、接触することはあるが、重なることはないとする。また線分は限りなく細いものとし、交差点の大きさは無限小とする。 2つのヒエログリフ…

問題 グリッドが与えられる。各セルは白'W'か黒'B'か何も塗られていない'?'のいずれかである。'?'のセルを白か黒で塗っていきグリッドがRectangleAvoidingになるようにしたい。RectangleAvoidingとはグリッド中のいかなる長方形（各辺がXY軸に平行なもの）を…

問題 うさぎが数直線上でx=0の位置からジャンプを始めて、ゴール地点のx=1000000001に行こうとしている。うさぎは2種類のジャンプが出来、一回のジャンプで(x - 2)か(x + 2)に移動できるスモールジャンプと、(x - largeJump)か(x + largeJump)に移動できるラ…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11239&rd=14541 文字列message[i]を部分列として持つような最短の文字列を返せ。複数ある場合は辞書式最小のものを返せ。なお各message[i]の文字はすべて異なる。 やりかた Editorialを参考にし…

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11501&rd=14538 N*Mの盤面に0~9の数字が書かれている。この盤面を垂直方向か、水平方向の断片に分ける（問題文中の図参照）。この断片一つ一つを、垂直な断片なら上から、水平な断片なら左から10…

問題 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=11225&rd=14427ピラミッド型の8パズルの初期局面とゴールとなる局面が与えられる。任意のピースを任意の回数動かして初期局面からゴールとなる最終局面まで遷移したい。遷移できないときは初期局…

問題 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、死んだ状態にあり、それ以外の正六角形は各々ことなる色で塗られている。同じ頂点を…

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

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

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

問題 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=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'は火、'.'は何もないセル、'$'がプレイヤーのスタート地点である。プレイヤーはスタート地点から出発して毎ターン上下左右の隣接セルで壁か火の…

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

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

問題文となる自然数の組をa 単純に探索すればいい。TLEが怖かったのでなるべく外側ループで探索を少なくした。 int main(int argc, char **argv){ int n; scanf("%d", &n); for(int d = 2; d <= n; d++){ for(int a = 2; a < n; a++){ if(a > d) continue; f…