問題 nxnのグリッドに白石'o'と黒石'x'が置かれている。 何も置かれていない場所は'.' 辺を共有する白石はひとかたまりとみなす。 ひとかたまりの白石が、何も置かれていない場所に隣接していない状態になると、 その白石は全て'.'に変わる。黒石を好きなだ…

問題 数列a[i]が与えられる。 それぞれの項から、引いた後0以下にならないように最大kを引くことができる。 なるべく出来た数列の最大公約数を大きくしたい。 最大値を求めよ。 制約条件 a[i]≦10^6 n≦3*10^5

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

問題 Hex格子上の図形が与えられる。 隣り合う格子を必ず違う色で塗るとき、図形のすべての格子に色をつけるためには何色必要か求めよ。 制約条件 図形は50x50に収まる

問題 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文字の部分文字列と、末尾か…

問題 R, G, Bのどれかの色をした歯車がn個ある。 同じ色をした歯車は、すべて同じ向きに回転している。 歯車のうち、いくつかは噛み合っていて、噛み合っている歯車は必ず反対向きの回転をしている。 同じ色をした歯車同士が噛み合っていることはない。 この…

問題 英小文字からなる文字列が与えられる。 文字列に対して、文字x, yを選び、文字列に現れるすべてのxをyに置換することができる。 このときにかかるコストはxが現れている回数である。 この操作を繰り返し行い、文字列を回文になるようにしたい。 かかる…

問題 長さがnの数列 1 2 3 4 ... n-1 nがある。 この数列に対して3回以下、以下のような操作を行った。 l, rを選びaの区間[l, r]の順番を反転させる。 結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。 制約条件 n≦1000

問題 長さが2^nの配列が与えられる。 配列に対する値vを以下のように計算する。 (a[0] or a[1]), (a[2] or a[3]), (a[4] or a[5]) ...を新たな数列aとする (a[0] xor a[1]), (a[2] xor a[3]), (a[4] xor a[5]) ...を新たな数列aとする というように、隣接す…

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

問題 nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。 1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。 全体でc個以上のマスに色がつくのにかかる時間を求めよ。 制約条件 n≦10^9

問題 nxmのアルファベット小文字の書かれたグリッドがある。 このグリッドの部分長方形うち、四隅のアルファベットが同じで、含まれている'a'の個数がk個であるようなものの個数を求めよ。 制約条件 n, m≦400 k≦nm

問題 問題文中の擬似コードにしたがって(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頂点からなる木のうち、m個の頂点から被害が出ている。 頂点のうち1箇所に悪霊がいて、被害の出ている頂点は全て、悪霊のいる頂点からの距離がd以内である。 このとき、悪霊のいる頂点としてありうる頂点の個数を求めよ。 制約条件 n, m, d≦10^5

問題 n問のクイズをやって、ちょうどm問正解した。 このクイズは正解すると1問につき1点で、 k回連続で正解すると、（1点が加えられた後で）現在の得点が倍になる。 （その後、連続正解数のカウントは０に戻る） 得られた得点の最小値を求め、mod 10^9+9で出…

問題 n頂点からなる木が与えられる。 木のそれぞれの頂点に、以下のような条件を満たすように'A'から'Z'の一文字のラベルを割り当てる。 同じラベルを持つ任意の頂点u, vについて、uからvへのパス上に、uのラベルよりも 小さいアルファベットのラベルを持つ…

問題 黒板に二行に数字を書く。 最初、上の行に0, 下の行に1を書いた後で次の操作を繰り返す。 Tの操作 上の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 Bの操作 下の行の数字 := 上の行の数字 + 下の行の数字 と書き換える。 これをn回行った…

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

問題 n個の数列がある。 この中からk個以下の数字を削除して、連続する同一の数字の長さを最大にしたい。 その最大値を求めよ。 制約条件 n≦2 * 10^5

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

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