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


DP

POJ 2342 Anniversary party

問題 N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。(つまり、ある一人にたいして上司はせいぜい一人しかおらず、上司のいない人間はただ一人である) パーティには部下とその直属の上司が…

POJ 1384 Piggy-Bank

問題 複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。 やりかた dp[i]:=(重みの和がiであるときの価値の最小値)でDP。硬貨j…

POJ 1606 Jugs

問題 ビーカーAとBの容量Ca、Cbが与えられる。ビーカーに水を入れる操作を行って、どちらかのビーカーに入っている水がNになるようにしたい。行ってよい操作は以下の6種類である。 Aいっぱいに水を入れる Bいっぱいに水を入れる Aを空にする Bを空にする Aの…

POJ 2626 Chess

問題 チェス大会のチーム編成を考えたい。各チェスプレーヤについて、白チームとして戦った場合の強さと黒チームとして戦った場合の強さの2つが与えられる。30人以上のプレーヤの強さが与えられる。これらプレーヤから選抜で白チーム15人、黒チーム15人の編…

POJ 2033 Alphacode

問題 アルファベット大文字からなる平文に対し、A=1、B=2、…、Z=26と置き換える暗号化を行う。この暗号文は一意に復号化できない可能性がある。暗号文が与えられるので何通りの復号化があるか求めよ。 やりかた DP。 dp[i]:=(i桁目までの復号化パターン数)…

POJ 2537 Tight words

問題 [0...k](0 やりかた DP。 dp[i][j]:=(長さiの文字列で最後の文字がjであるようなtightな文字列が発生する割合(百分率))とする。dpでtightな文字列の総パターン数を求めて(k+1)^nで割ることもできるが、C++では多倍長整数を使わないとできないのでこ…

POJ 3670 Eating Together

問題 1~3の数字からなる数列がある。この数列を単調非減少もしくは単調非増加にするために書き換える必要のある数字は最小でいくつか求めよ。なお数字は1~3にしか書き換えられない。 やりかた DPでやった。 数列のうちの単調非減少なLISの長さをもとめると…

SRM 414 Div1 Medium InfiniteSequence2

問題 i i >= 1 の場合、 で定義される数列がある。はxの床関数である。 を返せ。 やりかた 単純なメモ化再帰で通る。ただしすべてメモするとMLEなので100万くらいまでメモっておいてそれ以上大きい場合は、再帰を繰り返して計算するようにすると通る。以下ソ…

SRM 398 Div1 Medium CountPaths

問題 高さr、幅cの長方形の盤面がある。(1,1)のコマから右隣か上に移動を繰り返してゴールの(r,c)まで行きたい。盤面には特別なコマがいくつかありそれらの位置はfieldrow、fieldcolで与えられる。ゴールに行くまでに特別なコマをx個通る手順数を1000007で割…

SRM 386 Div1 Medium PolygonCover

問題 XY座標上で点が与えられる。全ての点が少なくとも1つ以上の多角形に属するように多角形を配置する。それらの面積の和が最小となるように配置し、その和を返せ。多角形の頂点は常に与えられた点の上にしか置くことはできない。与えられた点は多角形の辺…

SRM 383 Div1 Medium FloorBoards

問題 1x1のタイル、もしくは1x1の障害物で構成されたサイズが10x10以下の部屋が与えられる。この部屋を1xNの棒で敷き詰めたい(Nは任意の正整数)。棒は部屋の幅もしくは奥行きに対して平行にしか置くことができず、一つのタイルに対して重複して置くことは…

SRM 354 Div1 Medium RemissiveSwaps

問題 整数Nが与えられる。好きな桁を2つ選んで、それらの数字を1つずつ減らしてそれらを交換するというゲームを行う。このゲームでとりうる最も大きい数字を求めよ。なおLeading Zeroができてはいけない。 やりかた ゲーム中に桁が増えるようなことはなく、…

SRM 399 Div1 Medium BinarySum

問題 3つの自然数a,b,cが与えられる。これらを2進数表記にした際に、最も大きい桁数を持つ数字と桁数が同じになるように残りの2つにleading zeroを足す。これらの数字について2進数上で1と0の順番を好きに入れ替えることで新たな数字a',b',c'を作る。なおlea…

SRM 395 Div1 Medium Skyscrapers

問題 1からNまでの高さを持つ、N棟の建物が一直線上に並んでいる。これらを左端から眺めた時に、i番目の建物が見えるというのは、0〜i-1番目の建物がi番目の建物より低い時である。右端から眺めた時に見える場合はi+1〜N-1番目の建物がi番目の建物より低い時…

SRM 384 Div1 Medium SchoolTrip

問題 何人かが円状に位置しており、一つのボールを互いに当て合うゲームをする。プレイヤーはボールを持っている時、自分以外の人を狙うものとし、i番目のプレイヤーがボールをもっている時に、このプレーヤーが狙った相手に当てることのできる確率はprobabi…

SRM 371 Div1 Medium ChessMatchUp

問題 チェスの団体戦を行う。自チームと相手チームの各人の強さが数値で与えられる。勝てば2ポイント、引き分けで1ポイント得点が入るとする。相手チームとの組み合わせを好きにできるとき、自チームの最大の得点を求めよ。 やりかた 強さでソートした上でDP…

SRM 330 Div1 Medium PrefixFreeSubsets

問題 どの要素も互いの接頭辞にならないような文字列の集合をprefixfreeな集合と言う。与えられた文字列の集合のうちprefixfreeとなるような部分集合の数を求めよ。空集合も含める。 やりかた メモ化再帰による。 文字列をソートするとprefixfreeとならない…

SRM 304 Div1 Medium Conditional

問題 面数がmaxSideのサイコロをnDice個ふる。少なくとも1つがvの目を出す条件のもと、出た目の和がtheSum以上になる確率を求めよ。 やりかた 条件付き確率を求める問題。まずvの目が一回は出つつ、合計がtheSum以上になる同時確率をdpで求める。 dp[k][i][j…

SRM 349 Div1 Medium DiceGames

問題 目の数が異なるサイコロが複数与えられる。各サイコロの目の数はsides[]である。サイコロを一斉に降った時に、サイコロを区別しないとして出る目のパターン数を求めよ。 やりかた サイコロを目の数でソートしてDP。 dp[i][j]:=(サイコロを目の数の小さ…

SRM 338 Div1 Medium RandomSwaps

問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=(i回スワップした後にbに移動している確率…

SRM 320 Div1 Medium ContestSchedule

問題 プログラミングコンテストがいくつか開かれ、それらの開始時間、終了時間、勝率が空白で区切られた1つの文字列"s t p"の形式で与えられる。あるコンテストに出場している間は他のコンテストには出場できない。最適な出場の仕方をした時に、勝てるコン…

SRM 316 Div1 Medium PlacingPieces

問題 直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が1つも置けないようになったら終了とする…

SRM 314 Div1 Medium GrasslandFencer

問題 フェンスが複数あり、それらの長さが与えられる。フェンスを使って三角形をいくつか作るとき、できた三角形の面積の総和を最大化せよ。ただし、複数のフェンスを使って1辺とすることや、1つのフェンスを複数に分割することはできない。 やりかた bitDP…

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

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

Member SRM 468 Div2 Hard Gifts

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

SRM 462 Div2 Hard SteeplechaseTrack

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

Members SRM 461 Div2 Hard NameInput

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

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 549 Div2 Hard OrderOfTheHats

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

SRM 544 Div2 Hard AliceBobShuffle

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

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 517 Div2 Hard CuttingGrass

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

SRM 508 Div2 Hard YetAnotherORProblem2

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

SRM 504.5 Div2 Hard TheTicketsDivTwo

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

SRM 502 Div2 Hard TheCowDivTwo

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=11352&rd=144310〜N-1の数字からK個選んだものの和がNで割り切れるような選び方の総数をもとめよ。 やりかた Writer解を参考にしました。DP。 dp[i][j][k]:=(i番目の数字まででk個選んだ時の和の…

SRM 497 Div2 Hard MakeSquare

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=8681&rd=14426同じ文字列を2つ結合してできた文字列をSquareな文字列という。文字列Sから好きな文字を取り除く、変更する、挿入するという操作を行うことでSquareな文字列にするための最小の操…

SRM 584 Div1 Easy / Div2 Medium Egalitarianism

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

SRM 477 Div2 Hard RandomAppleEasy

問題 http://community.topcoder.com/stat?c=problem_statement&pm=10562 箱がN個あり、箱iにある赤りんごの数と青りんごの数がそれぞれred[i], green[i]で与えられる。この複数の箱から空集合を除く箱の部分集合を選んで、それらの選ばれた箱にあるすべての…

SRM 476 Div2 Hard SubAnagrams

問題 http://apps.topcoder.com/wiki/display/tc/SRM+476YのあるsubstringのアナグラムがXになるとき文字列Xが文字列Yのsubanagramであるという。いくつかの文字列がvector stringで与えられる。これらの文字列を結合した文字列Sをn個に分割したい。ただしS1…

SRM 474 Div2 Hard SquaresCovering

問題 2次元平面上に点が複数あり、それらの位置x[i], y[i]が与えられる。この点を複数種類の正方形で全て覆うことを考える。正方形jの幅はsides[j]で与えられる。正方形jを一つ配置するコストはcost[j]である。正方形はどの種類も無尽蔵にあるとする。全て…

SRM 459 Div2 Hard ParkAmusement

問題 http://apps.topcoder.com/stat?c=problem_statement&pm=10723&rd=14145いくつか島がある。ある人がある島からスタートして、島と島を結ぶ道をK回通ってゴールとなる島へ行きたいとする。 vector landingsが与えられ、landings[i][j]が'1'のとき、島iか…

POJ 3735 Training little cats

問題文DP強化週間。猫がN匹いる。3種類の命令が存在し、それが「g i」ならi番目の猫の持つピーナツをひとつ増やす。「e i」ならi番目の猫が持つピーナツの数をゼロにする。「s i j」ならi番目とj番目の猫が所有するピーナツを交換する。これらの命令が1セッ…

POJ 3230 Travel

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

POJ 3186 Treats for the Cows

問題文DP強化週間。配列が与えられ、毎ターン配列の先頭か最後尾から数字を取り出せる。Tターン目に取り出した数字がaだとすると得点T * a が得られる。全ての数字を取り出したときの最大の得点を求める問題。下の図のように dp[i][j]:=(配列の左からi個、右…

POJ 2184 Cow Exhibition

問題文DP強化週間。整数の数列SとFが与えられる。S+Fの部分和の最大値を計算する。しかしそのときのSの部分和、Fの部分和ともに0以上でなくてはならない。という問題。dp[i+1][j]:=(数列のi番目まででSの部分和がjである時のFの部分和の最大値)でDP。メモリ…

POJ 3356 AGTC

問題文DP強化週間。文字列が2つ与えられる。それらの文字列の適切な位置に文字を挟む、消去する、文字を変えるなどして、2つの文字列を同じにしたい。そのために必要な処理の回数を求める問題。要は編集距離。 dp[i+1][j+1]:=(文字列1のi番目と文字列2のj番…

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