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


幅優先探索

POJ 1387 Labyrinth

問題 やりかた 木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。 メモリ量、制限時間ともにシビア。グラフは隣接リストで持たずに、ある頂点に対する4方向の連結情報を…

POJ 1376 Robot

問題 グリッド上の格子点を直径1.6mの円形のロボットがスタート地点からゴール地点まで移動する。グリッドの一部に障害物があり、ロボットを障害物にぶつけてはいけない。ロボットは一回の移動で左右に向きを変えるか、1~3つ分の格子点を直進することができ…

POJ 2253 Frogger

問題 x,y座標が幾つか与えられる。0番目の点から1番目の点に向かって、直接、もしくはその他の点を経由しながら移動する。点から点へのジャンプにかかるコストは点と点のユークリッド距離で表される。移動中にかかる最長のコストを最小化せよ。 やりかた 二…

POJ 3126 Prime Path

問題 素数が2つ与えられる。素数のいずれかの桁の数字を一つ書き換えて別の素数に変える操作を、与えられるひとつ目の素数から始めて、ふたつ目の素数に到達するまで行う。最短の操作回数を求めよ。ただし与えられる素数はともに4桁の素数で、経由する素数も…

SRM 308 Div1 Medium CornersGame

問題 6x6のチェス盤があり、セルには石と旗の2種類の障害物がある。右下の4セルにコインが置かれており、これらのコインは隣接する空白のセルに移動できる。また、隣接するセルに別のコインが置いてある、もしくは石が置いてある場合で、更に隣のセルが開い…

SRM 340 Div1 Medium CsCourses

問題 CSの授業がいくつか用意されており、i番目の授業にはtheoreticalValue[i]とpracticalValue[i]とexpire[i]という3つの数値が与えられている。各授業の履修期間は一ヶ月で、あなたはひと月に授業を一つだけ取ることができる。そしてあなたは理論スキルと…

SRM 578 Div1 Easy GooseInZooDivOne

問題 2次元グリッドが与えられる。'v'で与えられるセルにはガチョウかアヒルがいる。これらの鳥の配置には以下のようなルールがある。 少なくとも1羽は必ずガチョウであり、必ず偶数羽いる 互いにマンハッタン距離でdist以内にいる鳥はガチョウである ガチョ…

SRM 506 Div2 Hard SlimeXResidentSlime

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

Member SRM 468 Div2 Hard Gifts

問題 グリッド状の迷路が与えられる。各グリッドはいくつかのタイプが有り、各タイプは以下のようになっている。'.' 通過できる '#' 壁。通過できない 'K' スタート地点 'Q' ゴール地点 'G' 宝物スタートから初めて宝物をなるべく多く集めながらゴールにたど…

SRM 464 Div2 Hard ColorfulMazeTwo

問題 グリッド状の迷路が与えられる。各グリッドはいくつかのタイプが有り、各タイプは以下のようになっている。'.' 通過できる '#' 壁。通過できない '$' スタート地点 '!' ゴール地点 'A ~ G' 罠の仕掛けられているグリッド AからGまで7種類あるスタート…

Members SRM 461 Div2 Hard NameInput

問題 これは入力カーソルを使用して文字列を入力する問題である。 文字列を含んだvector predictionSequence と name が与えられる。 これらをそれぞれについて結合した文字列をS,Tとする。入力カーソルが最初Sの先頭に来ているものとして、カーソルはSの文…

SRM 541 Div2 Hard NonXorLife

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11890&rd=14733 'o'か'.'かで埋められたグリッドが与えられる。'o'のマスは毎ターンごとに隣接する上下左右のマスを'o'に塗り替えていく。Kターン後の'o'のマス数を求めよ。 K やりかた 単純な幅…

SRM 509 Div2 Hard NumberLabyrinthDiv2

問題 R*Cのグリッドで区切られたボードを(c1, r1)の座標から(c2, r2)まで移動することを考える。各セルは0~9までの数字が書いてあるかもしくはemptyを示す'.'が書いてある。数字dが書いてあるセル(x, y)からは(x - d, y)、(x + d, y)、(x, y - d)、(x, y + d…

SRM 507 Div2 Hard CubeRoll

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11322&rd=14436 数直線上に落とし穴があり、落とし穴の位置はholePos[i]で与えられる。最初initPosにある石をgoalPosに動かすことを考える。一回の移動で数直線上で平方数移動することができる。…

POJ 1338 Ugly Numbers

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

Get up! 明日のSUPER ST@R!