問題 自然数N, Kが与えられる。 {1, 2, ..., 2*N}の集合を互いに素なN個ずつの集合A, Bにわける。 A, Bの要素を小さい順に並べたとき、どのiについても|A[i] - B[i]| ≧ KとなるようなA, Bの選び方は何通りあるか、mod 10^9 + 7で求めよ。 制約条件 N≦50 K≦10

問題 ハノイの塔がある。 通常のルールに加えて、軸iにささっている円盤を軸jに移動するときにcost[i][j]がかかる。 最初軸0にささっているn枚の円盤を、軸2に全て移動させるのにかかるコストの最小値を求めよ。 制約条件 n≦40 0≦cost[i][j]≦10000

問題 木が与えられる。 それぞれの頂点には最大１匹のきつねがいる。 きつねは、最終的に以下の条件を満たすように移動したい。 きつねがいる町が連結になっている 一つの町には最大一匹のきつねしかいない このとき、きつねの移動距離の総和の最小値を求め…

問題 Typocoderにn回参加する。 初期のレーティングはXで、i回目のコンテストで本気を出すとD[i]レーティングが上がり、 本気を出さないとD[i]レーティングが下がる。 ただし、レーティングが0未満になったときは、0になるとする。 レーティングが2200以上の…

問題 {1, 2, ..., N}の部分集合Aを選ぶ {1, 2, ..., M}の部分集合Bを選ぶ。このとき、AとBの積集合が空かつ、（Aの要素全てのxor）＜（Bの要素全てのxor）となる集合の選び方は何通りあるか。 mod 10^9 + 7で求めよ。 制約条件 N, M≦2000

問題 各成分が0または1の行列Aが与えられる。 Aの行のうちrowCount個以上の行が回文であり、 Aの列のうちcolumnCount個以上の列が回文になるように、 Aの成分をいくつか書き換える。書き換えなければならない最小の個数はいくつか、求めよ。 制約条件 Aの行…

問題 動物がn匹いて、2チームに振り分けてリレーをする。 それぞれの動物は、自分の区間をA[i]秒以上B[i]秒以下のどれかの時間で走る。 二つのチームの走行時間の差の最大値が最小になるようなチーム分けにおける、 走行時間の差の最大値を求めよ。 制約条件…

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_number

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_dice

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_tournament

問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_game

rng_58さんの主催したTypical DP Contestの問題の解法の記事を書いていきます。 コンテストのURLはhttp://tdpc.contest.atcoder.jp/で、問題文などもそこを参照。 問題 http://tdpc.contest.atcoder.jp/tasks/tdpc_contest

問題 長さnの01からなる文字列が与えられる。 この文字列に大して以下の操作を行うことができる。 任意の1文字の0,1を反転する 先頭からk*m文字の0,1を反転する（ただしkは任意の自然数） 操作を終えたあと、文字列の先頭からn-m文字の部分文字列と、末尾か…

新環境のテストも兼ねて出てました。がDの誤読で酷いことになった。 問題 1〜10までの重さの錘のうち、使うことができる種類のものが与えられる。 個数に制限はなく、無限に使える。 これをm回天秤に以下のルールで乗せる。 交互に違う皿に置く。 2回連続で…

問題 問題文中の擬似コードにしたがって(m+1)x(m+1)の行列を埋めたとき、 最後の行に現れる1の数がtに等しいようなmのうち、 m≦nを満たすものはいくつあるか求めよ。 行列の埋め方は要約すると以下の通り。 1行目は右上だけを1にする。 a[i][j] = a[i-1][j-1…

問題 n頂点からなる無向完全グラフで表される都市と道がある。 ここに雨がふって、それぞれの道がroads[i][j] / 8の確率で残り、 それ以外の確率で破壊される。 残った道が、木になっている確率を求めよ。 制約条件 n≦16

問題 正の整数a, b, cが与えられる。 a + b = cが成り立つように、それぞれの数字を 数字を一つ削除するごとにコストdelCost 数字を一つ挿入するごとにコストinsCost 数字を一つ置換するごとにコストrepCostで、 何回でも削除、挿入、置換ができる。 ただし…

問題 相異なる2以上のn個の整数a[i]を全て含むようなdivisor treeのうち、頂点数が最小のものの頂点数を求めよ。 ただしdivisor treeとは以下のような木である。 各頂点には整数が書かれている 葉の頂点の整数は素数 そうでない頂点の整数は、その子の頂点の…

問題 長さnの英小文字からなる文字列が与えられる。 この文字列の（必ずしも連続しない）部分文字列で、長さがちょうど100の回文は存在するか。 存在するならそれをどれか一つ、存在しないなら、部分文字列の回文のうち最も長いものをどれか一つ出力せよ。 …

問題 n人が一隻のボートを使って河を渡りたい。 ボートにはwKgまでの人が乗れる。i番目の人の重さはa[i]で、全て50または100kgのどちらかである。 ボートは一人以上の人間が乗っていないと動かせない。全員が向こう岸に最短回数のボートの移動で移るような移…

問題 n個のドアがある。 i番目のドアを開けるのに、赤の鍵がdoorR[i]個、緑の鍵がdoorG[i]個必要である。 i番目のドアを開けると、（最初の一回だけ） 赤の鍵がroomR[i]個、緑の鍵がroomG[i]個、白の鍵がroomW[i]個得られる。 一度使った鍵は壊れるのですぐ…

問題 n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。 Tの時間のうちに異なる歌をできるだけ多く歌いたい。 トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。 最大でいくつの歌を歌え…

問題 n人の人がいて、それぞれの人の大きさはa[i]である。 n人はn!通りの並び方を等しい確率で選んで並ぶ。 大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。 入る人が、入れない人を飛ばすことはできない。 レストランに入れ…

問題 長さnの数列a[i]が与えられる。 a[i]の空でない、（必ずしも連続しない）非減少部分列のうち、異なるものを全て取り出す。 それぞれに対して、それより"小さな"列の個数を求め、足し合わせる。 個数の総和はいくつか。 ただし、列xiよりyiが小さいであ…

問題 n個の町がn^2本の道でつながっている。 車がm個あり、それぞれの車で町iからjまで行くのにかかるコストが与えられる。 ここでr回のレースをする。 i回目のレースではsiからtiまで移動する。 この際、車をki回まで乗り換えてよい。 車は任意の町で、時間…

問題 n桁の正整数であって、 0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。 leading zeroは許されない。 制約条件 n≦100

問題 nxnのそれぞれのマスに数字a[i][j]が書かれたグリッドがある。 Aさんがグリッドの左上から右下まで、右か下だけに移動しながら移動する Bさんがグリッドの右下から左上まで、左か上だけに移動しながら移動する このとき、「二人の少なくともどちらかが…

問題 うさぎがn匹いて、それぞれs[i]からt[i]の間部屋にいた。 部屋にいた時間の区間が長さ0以上の共通部分をもつうさぎは友達になった。 うさぎが全員twitter的なサービスで自己紹介を、他の全てのうさぎに見せたい。 友達の自己紹介は直接見られるが、友達…

問題 n個の単語を、幅wのフィールドに、好きな行数にわけて書く。 一つの単語は、間をあけずに、行をまたがずに書く。 単語と単語の間は一つ以上のスペースを空けて書く 行の先頭および末尾にはスペースを空けずに書く。 ただし、最後の1行の末尾はスペース…