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


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…

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