DPL_1 E Edit Distance (Levenshtein Distance)
dp[i][j] = (s1のi文字目まででs2のj文字目までを作る最小コスト) としてDPします。
各文字列に対する操作についてDPの遷移を考えると
- 挿入 dp[i][j] = dp[i][j-1] + 1
- 削除 dp[i][j] = dp[i-1][j] + 1
- 置換 dp[i][j] = dp[i-1][j-1] + 1
となります。さらにs1[i]とs2[j]が等しいときは置換を行う必要がありません。そのため、置換の代わりに
dp[i][j] = dp[i-1][j-1]
と遷移できます。
SRM 710 div2
Writerの方の解説
codeforces.com
Easy
問題概要
n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる。
解法
一番最初を選ぶ場合はマイナスのものだけを選択することで最大となり、選ばない場合はプラスのものだけを選択することで最大となる。この両パターンで大きい方を返す。
Med
問題概要
n要素の配列Aが与えられる。i番目の要素を選択するとA[i]を0にした後、i+1番目からA[i]個の要素に+1する。このときn-1番目の要素の次の要素は0番目の要素である。要素1つのみが正の数になるように要素を選択していく。このとき、どのように要素を選択していけば条件を達成することができるのか出力する。
解法
0でないもっとも先頭の要素を選択することを繰り返し、要素の遷移をシミュレートしていく。
Hard
問題概要
n頂点m辺の連結な無向グラフが与えられる。各頂点には0からn-1のラベルがつけられる。自己ループや二重辺がないことが保証されている。各辺および各頂点にコストが定められており、頂点iから頂点jのパスのうち最大の辺のコストと最大の頂点のコストの積がパスのコストとして定められる。d(i, j)を頂点iと頂点jを結ぶ経路の最小のコストとする。0 <= i < j <= n-1 の全てのi,jの組についてのd(i, j)の和を出力する。
解法
Writerの方の解説のapproach1の方法についてです。頂点、辺をコストの小さい順に見ていき矛盾する点がなく暫定の最短コストよりも小さければ最短コストを更新します。正直ちゃんと理解できているか怪しいので嘘が含まれているかも…
AGC011 A, B, C, D
A問題
早い時間に到着する乗客をバスに乗せずに待たせて置くほうがいいパターンは存在しません。したがって到着時間をあらかじめソートしておくと、条件を満たすぎりぎりの乗客まで乗せて出発するを繰り返すことで答えを求められます。
B問題
色の順序等は答えに影響しないことからあらかじめ、大きさ順にソートしておいても問題ありません。a[i]番目の生物がa[i+1]番目の生物を吸収できる条件は、a[i]以下の大きさの和の2倍がa[i+1]以上であることです。したがって、累積和をとって、k番目以降が全て条件を満たしているならばn-k+1色が存在可能です。
C問題
二つの連結グラフA, Bが存在するときこれらのグラフから作られるグラフの連結成分の個数を考えます。
- A, Bどちらかが孤立点のとき
頂点数の積
- A, Bどちらかが二部グラフでない
二部グラフでない場合奇数長のサイクルが存在するため各頂点間に偶数と奇数のパスが両方存在する。したがって全ての頂点が連結になるため連結成分の数は1
- A, Bともに二部グラフ
奇数長のパスの組と偶数長のパスの組でそれぞれ連結成分がつくられるため連結成分の個数は2
与えられたグラフの孤立点の個数をa個、二部グラフの個数をb個、二部グラフでないグラフの個数をc個とすると、
個の連結成分となります。二部グラフの判定はdfsでO(|V|+|E|)で可能なので2秒以内に答えが求まる。
codeforces #393 div2 A, B, C
問題A
問題概要
月とその月が何曜日から開始するかが与えられる。この月で1週間ごとに列が切り替わるカレンダーを作成する際、カレンダーは何列になるか。
解法
1, 3, 5, 7, 8, 10, 12月は31日、2月は28日、4, 6, 9, 11月は30日である。1列目に書く日数を1ヶ月の日数から引いた後、7で割った数の天井関数が答えになる。
問題B
問題概要
n個の要素から成り和がmの数列を考える。数列の隣り合う要素の差が2以上にならないようしたい。このとき、最大となるk番目の要素の大きさを求めよ。
解法
まず、差が2以上にならないことからk番目の要素が最も大きくその隣の要素が1小さい数、その隣の要素がさらに1小さい数…となっていく。
例としてn=4, m=7, k=1のときを考える。まず、全ての要素が1以上であることから全ての要素に1を加え、mからnを引く。その後、k番目の要素をプラス1したいときは階段状になるように各要素に数を加えて、加えた分mを引いていく。
（丸の数が各要素の値、丸の中の数が加える順番）
この加算を行った後もmがまだ残っている場合、各要素に（残っているm）/nを足すことが可能である。(図でいうと底上げするようなイメージ）
問題C
問題概要
n頂点n辺の有向グラフが与えられる。このときすべての頂点について入次数と出次数は共に1である。各頂点に2状態を持つ物体が置かれている。辺に重みがついていて、重みが1の辺を移動すると状態が反転する。重みの変更、辺の繋ぎ変えを行うことで全ての物体が各頂点を両方の状態で通過するようにしたい。変更を行う最小の回数を求めよ。
解法
条件から考えて有向な閉路が1個または複数個存在する。
状態の変化について考える。重みが1の辺が偶数個のとき一周回って同じ頂点に戻ってくる際も出発したときと同じ状態であり、両方の状態で各頂点を通過することは不可能である。逆に重みが1の辺が奇数個のとき両方の状態で各頂点を通過することができる。したがって、重みが1の辺が偶数個であれば1回変更する必要がある。
次に辺の繋ぎ変えを考える。閉路がn個存在するとき、n個の辺をつなぎ替えることで全ての閉路をつなげることが可能である。閉路の個数はUnionFind木を用いることでO(nα(n))で求めることができる。
問題文の読解に時間を取られた…
codeforces #403 Div2 A, B, C
A問題
問題概要
n組の靴下が袋の中に入っておりそれぞれペアごとに揃えたんすにしまいたい。袋の中から1つずつ取り出して机に並べる。そして、靴下が組になった時点でたんすにしまう。袋から取り出す順番が与えられる。机に並ぶ最大の靴下の数を求めよ。
解法
実際にシミュレーションを行う。すでに机に並んでいる靴下を袋から取り出した場合、机に並んでいる枚数は1枚減る。逆に机の上には存在しない靴下を袋から取り出した場合、机に並ぶ枚数は1枚増える。O(n)で n <= 10^5なので実行時間は間に合う。
B問題
問題概要
1次元座標上にn(n <= 60000)人の人が存在する。i番目の人は座標x[i](1 <= x[i] <= 10^9)に存在し最高速度v[i](1 <= v[i] <= 10^9)で動くすることができる。n人の人が一点に集まるときにかかる最短時間を求めよ。
解法
ある時間tのときにn人の人が一点に集まることが可能か判定することを考える。i番目の人はx[i]-v[i]*tからx[i]+v[i]*tの範囲へと動くことができる。n人の範囲に共通部分が存在すれば可能であり、存在しなければ不可能である。ぎりぎりで可能なtが求めるべき最短時間となる。よって二分探索でtの範囲を狭めて行くことで求めることができる。二分探索を一回行うごとに範囲は1/2になるため、二分探索をn回行ったとき1/(2^n)に範囲が狭まる。200回行うと1/(2^200) ≒ 1/(10^3)^20 = 10^-60 に範囲が狭まる。この問題で許容される誤差は10^-6なため、十分正確な範囲で求まると考えられる。
C問題
問題概要
n頂点の木が与えられる。各頂点に色を塗っていく。頂点a, b, cが接続されているとき頂点a, b, cは異なる色で塗らなければならない。このとき最小の色数で塗り分ける方法を示せ。
解法
頂点vの子を塗ることを考える。このとき、頂点vおよび頂点vの親の色では塗ることができない。これら以外の色で小さい数の色から順に塗っていくことで条件にあった塗り分けが可能である。木の根から各頂点に順番に深さ優先探索していくことで答えを求めることができる。
codeforces #402 div2 A, B, C, D
問題A
問題概要
n人の生徒が属する2つのグループA, Bがある。各生徒は1から5の5段階の成績がつけられている。グループ間で生徒を交換することでそれぞれのグループで同じ成績の生徒の人数が等しくなるようにしたい。必要な最小の交換回数を求めろ。不可能であれば-1を返せ。
解法
まず、ある成績の生徒の人数が奇数人であればこのようなことは不可能なため-1を出力します。各成績の合計人数の半分の人数がそれぞれのグループにいる状態になれば条件が達成されるため、この人数との過不足から必要な回数を求めます。
成績 1 2 3 4 5 1 2 3 4 5 グループA 2 2 0 0 0 +1 0 -1 0 0 グループB 0 2 2 0 0 -1 0 +1 0 0
上記のような例を考えます。グループAは成績1の生徒が1人多く、成績3の生徒が1人少なく、グループBはその逆です。よってグループAの成績1の生徒とグループBの成績3の生徒を交換すればよく"1"を出力するべきです。このように各グループの過剰分の半分が求める結果になります。
成績 1 2 3 4 5 1 2 3 4 5 グループA 4 2 0 0 0 +2 0 -1 0 0 グループB 0 2 2 0 0 -1 0 +1 0 0
次の例のように過剰分の和が奇数のときどのように交換しても条件を満たすことはありえないため、-1を出力します。
問題B
問題概要
整数n, kが与えられる。nのある桁の数を消去することで、nを10^kで割り切れるようにしたい。条件を満たす最小の消去数を出力せよ。
解法
i(1 <= i < |s|)桁を消去するときのパターンを深さ優先探索で全列挙し、条件を満たした最小の消去数を出力しました。
最初、10*kで割り切れるようにする最小の消去数と勘違いしていたので、全列挙で解きました…後ろから見ていって0の数を数える方が単純に解けそう。
問題C
問題概要
n個の品物が存在し、現在の値段A[i]と一週間後の値段B[i]が与えられる。現在少なくともk個の品物を買う必要があり、残りは一週間後に買う。（現在k個以上の品物を買うことも可能）このとき、品物の購入にかかる最小の費用を求めろ。
解法
現在より一週間後の値段のほうが高い品物がk個以上ある場合、それらの品物を全て買い、一週間後に残りの品物を買うのが最善となる。
値段が上がる品物がk個より少ない場合は、b[i]-a[i]が大きいk個の品物を現在に買い、残りの品物を一週間後に買うのが最善となる。したがって、a[i]-b[i]をキーにソートし最初からk個の品物を現在に買う。
問題D
問題概要
単語tと単語pが与えられる。i回目の消去では単語tからa[i]番目の文字を消去する。単語tに部分文字列として単語pが含まれる最大のiを求めよ。
解法
答えとして求めるのがk回目の消去のとき、1回目からk回目までの全ての消去で条件が成り立っており、k回目以降の消去では条件が成り立っていない。したがって、二分探索を行うことで答えkを求めることができる。消去を行った後の単語tに単語pが含まれているかの判定はO(|t|)、二分探索はO(log|t|)なため、O(|t|log|t|)で答えを求めることができる。
Codeforces #401 A, B, C, D
A問題
問題概要
3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位置を求めてください。箱の位置を左から0, 1, 2と表します。
解法
ボールがどのように移動するのか実験してみます。
0 1 2 0 1 2 0 1 2 0 o o o 1 o o o 2 o o o 3 o o o 4 o o o 5 o o o 6 o o o 7 o o o 8 o o o 9 o o o
周期6で位置が変化しているため、移動させた回数nを6で割った余りからボールの初期位置を一意に求められます。
B問題
問題概要
AくんとBくんはN桁の数字を持っています。二人はこの数字を使ってある勝負をします。左の桁から1桁ずつ数の大小を比べ、相手より小さければ負けになります。しかしBくんは勝ちたいので不正をし、決まった順序と違う順番で数を提示します。Bくんが負ける数を最も少なくしたときの負ける数、Aくんが負ける数を最も多くしたときのAくんが負ける数を示してください。
解法
Aくんが出す数に対してBくんが出す数の適切な組み合わせさえ分かればいいため、AくんとBくんの持っている数の順番は関係ありません。
まず、負ける数を最も少なくするときのことを考えます。Aくんが提示する数以上の数を出せば勝負に負けません。そこで、勝負に負けないギリギリの数を出し続けることを考えます。AくんとBくんが持っている数をそれぞれソートし、最も小さい勝負に負けない数を順番に決めていきます。n-(負けない数)とすることで最小の敗北数を求めることができます。
次に、Aくんが負ける数を最も多くすることを考えます。同じ数では勝てないためAくんが出す数よりも大きい、最小の数を順に当てはめていくことで最大の勝利数を求められます。
これらの貪欲法でO(N)で求められます。
C問題
問題概要
n行m列（1<=n*m<=10^5）の表があります。この表の各マスには1つの整数(<=10^9)が書かれています。l行目からr行目(1<=l<=r<=n)が降順でない列が存在するかのクエリにk回(k<=10^5)答えてください。
解法
dp[i] =（i行目から最も長く降順でない数列が続いている行）を求めておくことで各クエリに対しO(1)で答えることができます。各列について上から順に降順でない部分列が何行から何行にかけてあるのかを求めます。全てのマスについて1回ずつ探索するため計算量はO(n*m)です。
D問題
問題概要
n個の文字列が与えられる。接尾字を消去することで文字列が降順に並ぶようにしたい。消去する文字数を最も少なくしたときの消去後の文字列を求めてください。
解法
後ろから順番に降順になるような最も消去する文字数が少ない消し方をすることで求めることができます。n番目の文字列はn+1番目の文字列に対し降順となるように文字を消去する。そして、n-1番目の文字列は消去した後のn番目の文字列に対し降順となるように文字を消去する必要がある。したがって後ろから順番に処理していくことで求められる。
