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

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


SRM

SRM 578 Div1 Easy GooseInZooDivOne

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

SRM 576 Div1 Easy ArcadeManao

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

SRM 574 Div1 Easy TheNumberGame

問題 プレーヤーが二人いて各々が数字をひとつ持っている。この数字は10進数表記で0を含んでいない。1ターンごとに交互の順番で以下の2つの操作のうち好きな方を選んで行う。 数字を逆順にする 数字を10で割る 先方のプレーヤーが1000ターン以内に後方の持つ…

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 570 Div1 Easy RobotHerb

SRM

問題 ロボットが2次元座標上に位置している。ロボットの一連の動作が数列aで与えられており、これによるとロボットのi番目の動作は a[i]前進し、a[i]回右に90度回転する である。 この一連の動作をT回行った後の到達点と出発点の間のマンハッタン距離を求め…

SRM 569 Div1 Easy TheDevice

SRM

問題 長さの同じN個の文字列がある。文字列は0か1で構成されている。ある機械があり、これはN個の文字列のうちの2枚を入力とし、各桁に対してANDかORかXORを行った(桁ごとにAND, OR, XORのどれを行うかは異なる。)結果を出力する機械である。各桁が行う処…

Div2 Hard 455~554 までの100問の2周目が終了

http://area.hateblo.jp/entry/2013/12/31/015531できなかったもののみやりなおした。といってもほとんどだけど。 そのおかげかも知れないが、Div2 Hardは本番でも解けるということが何回かでてきた。それでもDiv1Easyを落っことすのですぐDiv2に落ちてくる…

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 520 Div2 Hard SRMSystemTestPhase

問題 SRMというオンラインプログラミングコンテストがあり、コンテストでは3問出題される。複数人のコンテスタントの結果が与えられる。この結果は成績上位から順に並べられたものであるものの、その表記が曖昧で、各人がどの問題を提出したかの情報しか与え…

SRM 506 Div2 Hard SlimeXResidentSlime

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

SRM 490 Div2 Hard Hieroglyphs

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

SRM 489 Div2 Hard SolitaireChess

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

Member SRM 485 Div2 Hard RectangleAvoidingColoringEasy

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

SRM 477 Div2 Hard CarelessSecretary

問題 カードがN枚あり、各カードはそれぞれの袋に入っている。このカードをシャッフルして袋に入れなおし、この内K枚を取り出したときにK枚全てがもともとの袋にはいっていたものではなかった。このようなシャッフルの数はいくらか? やりかた いくつかの解…

SRM 475 Div2 Hard RabbitJumping

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

Member SRM 468 Div2 Hard Gifts

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

SRM 464 Div2 Hard ColorfulMazeTwo

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

SRM 462 Div2 Hard SteeplechaseTrack

問題 馬がフェンスを飛び越えてコースを走りまわるレースが行われる。あなたはこのレースを出来るだけ難しい物にしたい。 vector fenceが与えられ、各string の最初の1文字がスタート地点からそのフェンス手前に行くまでの難しさ、次の1文字がそのフェンスを…

SRM Div1 605 Easy AlienAndHamburgers

SRM

問題 ハンバーガーが複数あり、種類と味の良さがtype[i], taste[i]で与えられる。同じ種類のハンバーガが異なる味の良さを持つことはある。 食べたハンバーガーの種類数 × 食べたハンバーガーの味の良さの合計 が最大になるようにハンバーガーを選んで食べた…

Members SRM 461 Div2 Hard NameInput

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

Div2 Hard 455~554 までの100問が終了

SRM

SRM Div2 Hard 455~554までの100問が終わった。6月の頭から初めて12月の終わりまでかかったためほぼ7ヶ月でやり通したことになる。平均して2日に1問以下で明らかに遅いペースだと思う。やはりDiv2 Hard級は一問一問に時間がかかる。Div2 Medium / Div1 Easy…

SRM 554 Div2 Hard TheBrickTowerHardDivTwo

問題 C種類の色のブロック(1x1x1のサイズ)が各色無尽蔵にあり、これらのブロックを積み上げていき、2x2xHのタワーを作りたい。隣接するブロックが同色であるというのををK個以下に抑えるようにタワーを作る方法は何通りあるか。1234567891で割った余りを返…

SRM 553 Div2 Hard SafeRemoval

問題 数列が与えられる。この数列から1つずつ数字を取り除きたい。数字を取り除くとき、残りの数列の和が4の倍数にならないように取り除く。このようにしてK個の数字を取り除くとき、残った数列の和が最大になるようにしたい。最大値を求めよ。 やりかた E…

SRM 602 Div1 Easy TypoCoderDiv1

やりかた DP。 dp[i][j] :=(i番目までで、レートjの時のレート色の変化した回数の最大値)(0)次のコンテストが最終コンテストでそれに勝てばbrown coderになれるとき次コンテストが最終コンテストではないとき (1)現状がciel coderで次のコンテストで…

SRM 551 Div2 Hard ColorfulCupcakesDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=12138&rd=15173 複数のカップケーキがあり、'A', 'B', 'C'のいずれかの色がついている。これらのカップケーキを円形に並べたい。隣合うカップケーキが同じ色にならないように並べるとき、何通り…

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 545 Div2 Hard SpacetskE

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=12030&rd=14737 xy座標のX軸上を原点から座標(L,0)までの整数座標上において、ロケット任意の方向に1つだけ発射される。放たれたロケットはその方向に直線で進行し、0 やりかた XY座標における…

SRM 544 Div2 Hard AliceBobShuffle

問題 正数が書かれたカードのデッキが2つあり、2つのデッキの上からカードを任意の枚数ずつ取り出して場に積み上げていき、これを2つのデッキからカードが無くなるまで繰り返す。続いて場に積み上がったカードの上から任意枚数ずつ2つのデッキに積み戻してい…

SRM 542 Div2 Hard StrangeDictionary

問題 http://apps.topcoder.com/wiki/display/tc/SRM+542 長さが等しい文字列が複数与えられる。文字列中のランダムな2箇所を置換するのをランダムな回数行う処理をすべての文字列について行う。処理後の文字列をソートした時に当初の文字列が何番目に置かれ…

SRM 540 Div2 Hard FractionInDifferentBases

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11135&rd=14732 P / Q(既約とは限らない)をX進数で表現した時に割り切れないとする。AからBの間にこのようなXはいくつ存在するか。 やりかた Editorialを参考にしました。まずP、Qをこれらの最…

SRM 541 Div2 Hard NonXorLife

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

SRM 537 Div2 Hard PrinceXToastbook

問題

SRM 593 Div1 Easy HexagonalBoard

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

SRM Div2 528 Hard Mosquitoes

SRM

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11654&rd=14553 蚊が数直線上でxInit[i]の初期位置におり、毎秒v[i]の速度で移動する。あなたは前後R以下にいる蚊を殺傷できる爆弾を持っており、任意の時刻に任意の位置で爆発させることができ…

SRM 526.5 Div2 Hard MagicNaming

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11674&rd=14762 文字列がn個存在し、これらを辞書式最小になるように結合したものがSとなる。このnを最大化せよ。 やりかた DP。 dp[j][i] := (文字列Sのj文字目まででS[i...j]を1つの文字列と…

SRM 522 Div2 Hard CorrectMultiplicationTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11609&rd=14547 a * b = cという等式が与えられる。しかしこの等式は成り立っていないのでa,b,cをA,B,Cに書き換えてA * B = Cが成り立つようにしたい。の最小値はいくつか。1 やりかた Aを1から1…

SRM 519 Div2 Hard BinaryCards

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11552&rd=14544 カードが複数枚あり、2^0, 2^1, 2^3, ...というように各々に2のべき乗のいずれかが書かれている。このカードを表にすることでそのカードを使用するということをあらわす。自然数…

SRM 518 Div2 Hard CoinReversing

問題 http://community.topcoder.com/stat?c=problem_statement&pm=11473&rd=14543 表向きに置かれたN枚のコインと要素数Kの配列a[]が与えられる。ターンi(0-indexed)ではコインをa[i]枚ランダムに選んで裏表をひっくり返す、という動作をKターンまで行っ…

SRM 517 Div2 Hard CuttingGrass

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11536&rd=14542 複数の木があり、それらの高さはinit[i]である。毎ターンそれぞれの木はgrow[i]だけ成長する。そしてあなたは毎ターンどれかの木を切る。切るとその木は高さが0になる。 木の高さ…

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 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 510 Div2 Hard TheLuckyBasesDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11466&rd=14439 自然数nが与えられる。これをb進数で表した時に各桁に4か7しか現れないようなb進数(ただしb >= 2)はいくつか(つまりbはいくつの値を取りうるか)。 やりかた 全探索ではもちろ…

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 508 Div2 Hard YetAnotherORProblem2

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11435&rd=14437 N、Rが与えられる。 かつとなる数列の個数を求めよ。 やりかた N個の項のある桁のビットを取り出した時に、それらのビットが1であるのが高々1以下であり、これがすべての桁につい…

SRM 507 Div2 Hard CubeRoll

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

SRM 504.5 Div2 Hard TheTicketsDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11433&rd=14514n人の人間が一列に並んでいる。サイコロをふり、4が出たら列の先頭に並んでいる人を選んでおしまい。それ以外の偶数が出たら先頭の人を列から外して、もう一回サイコロを振る。奇…

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…

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