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


DP

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番…

POJ 2081 Recaman's Sequence

問題文DP強化週間。問題概要は簡単なので略。問題も小さい方からメモ化して計算していくだけ。 以下ソース。 int a[500001]; int main(int argc, char **argv){ a[0] = 0; set<int> rec; for(int i = 1; i <= 500000; i++){ int t = a[i - 1] - i; int u = a[i - </int>…

POJ 2250 Compromise

問題文DP強化週間。2つのテキストが与えられる。LCSを求めよ。という問題。LCS長のdp表をジグザグと左上に進んでいき、その添字i,jのときに2つに単語s[i],t[j]が等しければ出力。そうでなければdp長が短くなる方向に移動。 こちらを参考にさせていただいた。…

POJ 2392 Space Elevator

問題文DP強化週間。K種類のブロックがある。種類iのブロックは高さhi、個数ci個ある。 そして様々なブロックを下から積み上げて行った時、この種類のブロックは 必ずai以下に置かれていなくてはならない。積み上げることのできるブロックの 最長の長さを答え…

POJ 1745 Divisibility

問題文DP強化週間。長さNの数列が与えられる。数字間を+か-で計算していき、 その結果がKで割り切れるか調べよ、という問題。いかにもなDP。雪だるま式に書くより、メモ化再帰の方が直感的だった。他の人は雪だるま式に書いてるとこが多いみたい。 dp[i+1][j…

POJ 1836 Alignment

問題文DP強化週間。一列に兵が並んでおり、ここから何人か除いた時に、 残りの兵いずれもが少なくとも隊列の左右のどちらかの 端(端の兵ではない)が見通せるようにしたい。端が見通せる条件は 端までに自分より同じか背の高い兵が一人もいない時とする。 取…

POJ 1458 Common Subsequence

問題文DP強化週間。stringが2つ与えられる。LCS長を求めよ。dp[i + 1][j + 1]:=(文字列1のi番目までと文字列2のj番目までのLCS長)でDP。以下ソース。 int dp[1001][1001]; int main(){ string s, t; while(cin >> s >> t){ memset(dp, 0, sizeof(dp)); int N…

POJ 1157 LITTLE SHOP OF FLOWERS

問題文DP強化週間。花がF種類あって、一列に並んだ花瓶がV個ある。 花iは花i+1より左側の花瓶に活ける必要がある。 花の種類と各花瓶に対応した点数が与えられる。 点数を最大化せよ。という問題。dp[i + 1][j + 1]:=(花iまでを花瓶jまでにいけた時の最大の…

POJ 3046 Ant Counting

問題文DP強化週間。蟻の家族がいくつか与えられる。家族iはa[i]匹からなる。 この蟻の群れからS ~ B匹選ぶときの(順番を区別しない)集合の数を数えよ。重複組み合わせ。蟻本にまったく同じものがあったので参考にした。 dp[i][j]:=(家族i - 1まででj匹選ぶ…

POJ 2479 Maximum Sum

問題文DP強化週間。 問題・コードともにPOJ 2593にほぼ同じ。入力形式が違うだけ。ソースは略。

POJ 2593 Max sequence

問題文DP強化週間。要素数Nの配列a[]が与えられた時、 のSを求める。N dp[i]:=(i番目までで最大の区間和)とする。これを配列の左端から計算したものdp_lと 右端から計算したdp_rを求め、iを走査してmax(dp_l[i] + dp_r[i + 1])を求めれば良い。 int l[1000…

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