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

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


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街と村が存在し、それらの位置が与えられる。最初、村には道が通っていない。街と村の間に道路を引くか、街に行くことのできる村とそうでない村の間に道路を引くことでどの村も少…

SRM 492 Div2 Hard TimeTravellingSalesman

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11049&rd=14245N個の街があり、セールスマンが街0にいるとする。N個の街の間の道の情報がvector string で与えられる。これを一つのstringに結合した時に"a0,b0,cost0 a1,b1,cost1 ......"という…

SRM 584 Div1 Easy / Div2 Medium Egalitarianism

問題 N人の人間がいて、おのおの金を持っている。彼らの友好関係がvector string で与えられる。i番目の行のj番目が'Y'ならiとjは友人。'N'なら友人ではないとする。そして直接の友人間では持ち金の差は大きくともdとなるように調整されている。N人の持金の…

SRM 470 Div2 Hard ActivateGame

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10750&rd=14153数字が書かれたvector stringが与えられる。はじめは左上のみがアクチベートされている。毎ターンアクティブなセルとそれに隣接するアクティブでないセルをひとつずつ選んで、そこ…

SRM 460 Div2 Hard TheCitiesAndRoadsDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10774&rd=14146グラフが与えられる。これを全域木にするような辺の加え方の集合はいくつあるか。 やりかた (説明が間違っていそうです。) practice roomの回答を参考にしました。 全域木とする…

SRM 376 Div1 easy Trainyard

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

POJ 3230 Travel

問題文DP強化週間。街がN個あり、すべての街の間を移動するのに必要な交通費の情報が与えられる。またi日目にjの街にいたときにもらえる金額の情報が与えられる。M回移動するとしたときに得られる最大の金額を求めよ。という問題。dp[j][i]:=(i回移動した後…

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