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


グラフ

POJ 1387 Labyrinth

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

POJ 2536 Gopher II

問題 n匹のネズミの位置と、m匹のネズミ穴の位置が与えられる。タカがネズミを狙っており、s秒たった時点で穴に隠れていないネズミは捕食される。すべてのネズミは速度vで動くことができ、一つの穴には一匹のネズミだけが隠れることができる。捕食されるネズ…

POJ 1975 Median Weight Bead

問題 1からNの数字が書かれたビーズがある。2つビーズについての重さの関係の情報がM個ある。N個のビーズのうち重さが中央値になりえないものの個数を求めよ。 やりかた 一種のトポロジカルソート。自分より重いビーズに辺を張って、重さの関係をグラフに置…

POJ 2513 Colored Sticks

問題 両端にそれぞれ色が塗られている棒が複数与えられ、色が同じ棒の端同士を連結して一本の棒にすることができる。与えられた棒をすべて連結することはできるか答えよ。 やりかた やっていることはしりとりと同じ。各色をグラフ上の頂点とみなし、棒を辺を…

POJ 2472 106 miles to Chicago

問題 無向グラフの情報が与えられる。始点から終点まで辺のコストをかけ合わせたものがパスのコストになる。コストを最大化せよ。 やりかた 辺のコストにlogをかければコストの積を和に変換できる。あとはただの最小経路問題。以下ソース。 //ダイクストラの…

POJ 1985 Cow Marathon

問題 無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。 やりかた 無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。…

POJ 1129 Channel Allocation

問題 頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。 やりかた 四色定理から必ず4以下になる。 色を数値で管理して、深さ優先探索でグラフを探索する。探索中に次に訪れる点に隣接している点の色で使っていない色のうち、最も値…

POJ 2253 Frogger

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

POJ 3660 Cow Contest

問題 1からNまでのラベルが付いたノードが与えられる。このグラフの有効辺がM個与えられる。トポロジカル順序が厳密に決まっているノード数を返せ。 やりかた トポロジカルソートできるグラフだとして、あるノードのトポロジカル順序が厳密に決まっている場…

POJ 1308 Is It A Tree?

問題 グラフ上のノード番号が2つずつ入力される。前者から後者のノードへは有向辺が伸びているものとする。このグラフがひとつの木になっているか判定せよ。なお入力は複数のテストケースからなり、0 0がそのケースの入力の終わりを表し、2つとも負の数が与…

SRM 353 Div1 Medium PlatformJumper

問題 足場をジャンプして渡り、コインを集めるゲームがある。足場の位置とそこにおいてあるコインの枚数が与えられる。 ゲームでは今いる足場からy座標上で下にある足場にしか移動はできない。足場は点として考えて良い。ジャンプには物理法則があり、ジャン…

SRM375 DateFieldCorrection

問題 QWERTYキーボードにおいてキーとキーの距離とは隣接するキーをいくつ隔てて到達できるかによる。ただしスペースキーと隣接するキーとの距離は3と数える。(詳細は問題文中の図)"month day"という形式で日付が与えられる。この日付はミスタイプされてい…

SRM 350 Div1 Medium StarsInGraphs

問題 やりかた 問題では頂点から出ている辺が3本以上の時を星として数えているが、2本の時、1本の時、0本の時もそれらを星と認めると、出次数がnの頂点で構成される星の総数はになる。このうち2本の星と1本の星と0本の星の総数はになるので2^nからこれらの数…

SRM 303 Div1 Medium Knights

問題 NxNのチェスボード上にいくつかのナイトが置かれておりそれらの位置がposで与えられる。(表記の仕方は問題文参照) 任意のナイトを一回だけ移動した時に、移動先に別のナイトがいないようにしたい。取り除かねばならない最小のナイトの数を求めよ。 や…

SRM 328 Div1 Medium BlockEnemy

問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである(要は閉路がない)。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征…

SRM 322 Div1 Medium ExtendedDominoes

問題 2x1セルのドミノが複数あり、各セルには0~9の数字が書かれている。ドミノの右側の数字とその隣のドミノの左側の数字が同じになるようにドミノをつなげていき、ドミノがループをなるようにする(最左のドミノの左セルと最右のドミノの右セルの数字がおな…

SRM 301 Div1 Medium EscapingJail

問題 各ノード間の距離が与えられる。任意の2点間の最短距離を求めた時、それらのなかで最長距離を求めよ。 やりかた Warshall-Floydして、最長のものを求める。 class EscapingJail { public: int p(char c){ if('0' <= c && c <= '9') return c - '0'; if(…

SRM 583 Div1 Easy TravelOnMars

問題 Nの都市が円状に存在している。i番目の都市は前後range[i]個の都市との間に一方向の道路が敷設されている。startCityからEndCityに訪れるために必要な最小の通過道路数を返せ。 やりかた N - 1と0番目の都市が隣り合っていることに注意しつつ、ただのグ…

SRM 576 Div1 Easy ArcadeManao

問題 2Dゲームの画面が与えられる。'X'で表されるセルが足場を示しており、最下段は全て足場になっている。垂直に位置する2つの足場は、その2つの間の距離以上の長さを持つはしごを使って行き来することができる。最下段から目的地(coinsColumn, coinsRow)ま…

SRM 531 Div2 Hard KingdomReorganization

http://community.topcoder.com/stat?c=problem_statement&pm=11282 問題 王国にはNの街があり、街と街の間がつながっているかがkingdom[i][j]で与えられる。また、街と街の間に新たに道路を作る費用がbuild[i][j]で、道路を壊す費用がdestroy[i][j]で与えら…

SRM 506 Div2 Hard SlimeXResidentSlime

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

SRM 489 Div2 Hard SolitaireChess

問題 http://community.topcoder.com/stat?c=problem_statement&pm=1118910x10チェスの盤面が2つ与えられる。コマはナイトとポーンの2種類がある。ポーンは最上段に移動するとナイトに変身できる。 盤面1から盤面2の状態にするためにコマを動かす回数の最小…

SRM 475 Div2 Hard RabbitJumping

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

Members SRM 461 Div2 Hard NameInput

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

SRM 550 Div2 Hard TopView

問題 グリッド上にタイルが敷かれており、タイルの色は数字かアルファベットで表される。タイルは必ずXY軸に平行な矩形の形で敷き詰められる。タイルは別のタイルの上に積み重ねていくことができ、各色のタイルは一度しか敷かれることがない。タイルを鳥瞰し…

SRM 549 Div2 Hard OrderOfTheHats

問題 http://apps.topcoder.com/wiki/display/tc/SRM+549あるグラフの隣接行列が与えられる。このグラフに辺を加えるか、すでにある辺を取り除くかしてacyclicにしたい。必要な手順の最小回数を求めよ。 やりかた Editorialを参考にしました。bitDP。 acycli…

SRM 537 Div2 Hard PrinceXToastbook

問題

SRM 593 Div1 Easy HexagonalBoard

問題 正六角形を組み合わせたボードがある(問題文図参照)。 このボードのタテヨコのサイズに対応したvector string boardが与えられる。board[i][j]が'X'の時、対応する正六角形に色を塗るとする。'-'の時は塗らないものとする。隣接する正六角形は異なる…

SRM 512 Div2 Hard DoubleRoshambo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11289&rd=14537 AとBが両手でじゃんけんをする。1.Aの右手がBの左手に勝ち、Aの右手もBの右手に勝つときAに2点入る 2.Aの右手がBの左手に勝ち、Aの右手がBの右手と引き分けるときAに1点入る 3.そ…

SRM 503 Div2 Hard KingdomXCitiesandVillagesAnother

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10835&rd=14432街と村が存在し、それらの位置が与えられる。最初、村には道が通っていない。街と村の間に道路を引くか、街に行くことのできる村とそうでない村の間に道路を引くことでどの村も少…

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