AtCoder Beginner Contest 307 G - Approximate Equalization
メモ
差分だけが重要なので、各Aiについて Ai -= min(A)としていい
すると任意の値が0以上の整数になる。
また、この操作において合計は不変であるため
最終的なすべての合計はsa := sigma(A)になる
最終的な数列としてあらわれる物を考える
saがNで割り切れるときはすべての要素はsa / Nになり
それ以外の場合、sa/N(切り捨て)と sa/N(切り上げ)になる
切り捨ての小さい数が最終的に数列に含まれる個数をa
切り上げの大きい数が最終的に数列に含まれる個数をbとしたときに
b = sa % Nで、a = n - bになり、他の選択肢はない
よって大きい数をどこに置くかをdpで解く問題になる。
dp[i][j] := iの前まで見て、iより左で大きい数をj個置いたときの最小手数
とすると、操作が終わった部分について、切り上げと切り捨てが何個使われているか分かるため、iより左の合計が操作後どうなったかがdpの添え字i, jから一意に特定することができる。
また、数列の合計は操作の前後で不変でありi-1までしか操作をしていないことから
iの前までの操作が終わった段階で
(A0 ~ Ai)の合計は変わっていない
よってdpの添え字i, jについて現在のAiの値は sum(A0~Ai) - 左の現在の合計
として求められる
あとは自然に遷移する
不変量って感じの問題だった
AtCoder Beginner Contest 299 G - Minimum Permutation
メモ
Li(v) := vが現れるインデックスの内最も左
Ri(v) := vが現れるインデックスの内最も右
とする
辞書順最小なので、次の数にできる物の内最小のものを貪欲に決めていきたい。
値vを先頭にできるかの判定を考える。
l = Li(v)として[l+1, N)にv以外の値が全てあれば可能である
この問題は種類数を求めるクエリの下位互換だ
種類数のクエリについては以下の記事で触れられている
与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱
種類数を求めるには各要素の内、最も右にある場所のインデックスに1を入れたような配列について、区間の和を求めればいいことが分かる。
ある物が重複して数えられないように、それを数えるものを一つのものに対応させる際に、その決め方をgreedyにすると上手くいくというのは
greedyからの帰着に近いところがある...?
AtCoder Regular Contest 164 D - 1D Coulomb
メモ
以後以下のように言葉を定義する
S[i] := iの電荷(+か-)
R(s) := sと逆の電荷, R(+) == -, R(-) == +
cnt(i, s) := [0, i)にある符号sの数(つまりiより左にあるsの個数)
まず各iがどちらに動くかを考える
iが+の場合、i以外の合計は-1になり
iが-の場合、i以外の合計は+1になる
よって左右どちらかの合計が0の時、電荷は逆方向に動くため
以後同様に考えると、各電荷は括弧列の対応のように動くことが分かる。
具体的には
cnt(i, s[i]) >= cnt(i, R(S[i]))ならs[i]は左括弧として働き、そうでなければ右括弧として働く
そして最終的に作った括弧列が良い括弧列(すべての括弧について対応する括弧があるもの)である場合、対応する括弧同士の距離の総和が、あるTの決め方に対する答えになる。
よって良い括弧列のつくり方について、その距離の総和が求められれば
似たように問題を解くことができる
実際はiの符号についてcnt(i, +) == cnt(i, -)の時に、iには+をおいても-をおいても左括弧として扱えるため、答えは異なるが
総和を解く方法はいくつかある
解1
左括弧を置いたときに、その括弧が総和にどう寄与するかを考える
1 : ()
4 : (())
9 : ((()))
上のようにいくつか、距離の総和と括弧列の対応を書いてみると、
左括弧を置く際に、自分より左の閉じていない左括弧の数をocとして
距離の総和がoc * 2 + 1増えることが分かるため、
dp[i][j] := iまででj個左括弧が閉じていないものが残っているときの
(距離、場合の数)というペアを持つと解ける
(しつこいが実際は左括弧として+, -の両方の場合があるため
元の問題を解く際は、dp[p][m] := 左にある+の数をp, -の数をmとしたときのー
という風に扱ってそのp, mの数によって今おこうとしている電荷が左右どちらの括弧になるかを考えて実装する必要がある
)
解2
左括弧から右括弧への距離を、二つの数字の和で考える
例えば以下のように、_の部分には何かしらの括弧が入っていて
下に書かれている(と)が対応している場合
二つの距離は5だが、これは二つのインデックス2, 7について
-2, +7と計算しても同じものが導ける
__(____)__
よって左括弧があるインデックス集合をP, 右括弧があるインデックス集合をMとして
sigma(-Pi) + sigma(Mi)を求めれば、Tのある決め方についての総和が分かる
これは先ほどと同様に、dpに場合の数と距離の総和を持たせておけば解ける
AtCoder Regular Contest 164
メモ
まずai = ai - min(ai, bi), bi = bi - min(ai, bi)と置き換えて、sigma(min(ai, bi))を最初から得点している問題と考える。
すると、すべてのカードは0と整数が書かれたものになる
お互いに貪欲にやる事を考えてみると、表が0でないカードが偶数の場合、すべての大きい方が取れて
それ以外の場合一つ以外はうまく取れることが分かる
AtCoder Regular Contest 159 C - Permutation Addition
メモ
不変量について考えたい。
こういう時(何かを足していってそれぞれの値を合わせる時とか)は
全体の合計に注目するといいことが多い気がする。
どういう操作をしても不変なものを考えると
どう足しても一回で増える和は同じである
全体の合計はNの倍数になる必要がある。
N2 = (N(N+1))/2として
k回足すと合計が以下のようになり
sigma(A) + N2 * K = 0(mod N)
mod Nで0になる必要がある
ここでN2 * 2 = 0(mod N)なので
sigma(A)=0 (mod N)か sigma(A) + N2 = 0(mod N)が成り立つ必要がある
これが成り立つ場合必ずできる。
一回Aの合計がNの倍数になるように順列を高々一回足してやる
このNの倍数という良い性質を満たしたまま操作をしていきたいため、順列を毎回二回ずつ足すことを考える。
結論から言うと
1, 2, 3, 4, 5, 6, 7
7, 6, 5, 4, 3, 2, 1
と足すと全体の差分に0が足されるので
上手くswapしてやると
1, 2, 3, 4, 5, 6, 7
6, 7, 5, 4, 3, 2, 1
などで
-1, +1,+0+0+0+0
のようにできる
この問題の操作はこの+1, -1だけを足す操作に言い換えても答えが変わらない。
現状の合計はNで割り切れることが確定しており、一回の操作で合計が変わらないため
+1, -1を繰り返すことですべての値を同じに出来る
類題
0,1,2を足して同じ数を作る問題を
-1, 0, -1を足す問題と言い換え、合計を不変にする操作が同じ
AtCoder Beginner Contest 309 G - Ban Permutation
メモ
制約的に箱根駅伝dpを考える
from(1~N)からto(1~N)の全単射について、fromからtoへ辺を貼っていく問題だと考えると
箱根dpの性質から、まだ行き先が決まってないfromと元が決まっていないtoの数が一致する。この決まってない数をnとする
i個目について考えている際に、必要な情報は直前X-1個のfrom, toが決まっているかだけであるまる
これらをfx, txとして
dp[i][n][fx][tx] := iまで見た時、n個決まっていなくて 直近のfromの空きをfx, toの空きをtxとしたときの場合の数
とすると、遷移できる
fxをマスクで表現する際に、下位のbitに行くほど左の点であるようにすると
一つずれるときに>>1をするだけで済むのでわかりやすい
012...x-2, i
AtCoder Regular Contest 155 C - Even Sum Triplet
考えたこと
各操作についてその操作を打ち消すような逆の操作ができるため
A, Bをそれぞれ操作して同じ列を作れるか判定する問題だと思っていい
まず、ABをソートしても一致させられない場合はNo
1が2個か、0が3つの時に並び変えられるので
00100のように1が孤立しているとつらそう
1をまとめたい
1をまとめられるかを考える。
どちらも1についての操作ができない場合は、長さが3以上の0の列についてA, Bをsortして一致するかを判定。
どちらか片方だけ1の操作が出来る場合はおかしいのでNo(1の操作は途中で出来なくなることはない)
どちらも1の操作ができる場合、
1を二つ並べて近くの1のところまで動かしていくと111が作れる
111は工夫することでスライドさせていく事が出来、またその中の一つを切り離すことができる。
よって以下の方法で中央に1をまとめることができる
11を左右に動かして111の状態を作り、111の状態で真ん中まで戻る。
以後同様に左右の1を11を使って取りに行き111の状態で真ん中まで戻る
あとは、中央にまとまった1を左に動かしてやることで1をすべて左に寄せることができる。
また、1が2つ以上並んでいて、0が一つ以上列に存在する場合
1をソートすることができる
例えば、i, i+1をソートしたい場合、iの近くに0を持ってきてやればいい。
0については個数が3以上の場合ソートでき、二つの場合はソートできない
よって0が3つ以上ある場合は、一致させることができ
0が2つ以下の場合は0の順序があっていれば一致させられる