読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 2402 Palindrome Numbers

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

POJ 1248 Safecracker

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

SRM 587 Div1 Easy JumpFurther

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

SRM 580 Div1 Easy EelAndRabbit

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

SRM 573 Div1 Easy TeamContest

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

SRM 568 Div1 Easy BallsSeparating

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

SRM 506 Div2 Hard SlimeXResidentSlime

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

SRM 490 Div2 Hard Hieroglyphs

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

Member SRM 485 Div2 Hard RectangleAvoidingColoringEasy

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

SRM 475 Div2 Hard RabbitJumping

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

SRM 516 Div2 Hard NetworkXMessageRecovery

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

SRM 513 Div2 Hard CutTheNumbers

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

SRM 504 Div2 Hard Algrid

問題 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…

SRM 498 Div2 Hard NinePuzzle

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

SRM 586 Div1 Easy PiecewiseLinearFunction

問題 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 =…

SRM 496 Div2 Hard PalindromefulString

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

SRM 495 Div2 Hard HexagonPuzzle

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

SRM 585 Div2 MediumTrafficCongestionDivTwo

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

POJ 2262 Goldbach's Conjecture

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

SRM 484 Div2 Hard CubeColoring

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

SRM 472 Div2 Hard RectangularIsland

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

SRM 469 Div2 Hard TheMoviesLevelThreeDivTwo

問題 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が映画を見終えた…

SRM 467 Div2 Hard MazeOnFire

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

SRM 466 Div2 Hard MatrixGame

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

SRM 463 Div2 Hard Nisoku

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

POJ 1455 Crazy tea party

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

SRM 458 Div2 Hard ProductTriplet

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

SRM 457 Div2 Hard TheHexagonsDivTwo

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

SRM 455 Div2 Hard DonutsOnTheGrid

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

POJ 1543 Perfect Cubes

問題文となる自然数の組を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…

しょげないでよBaby 眠れば治る