SRM 548 DIV2 Hard: KingdomAndPassword

解法

oldPasswordが新しいパスワードにもなる場合がコーナーケース。

そうでない場合を考える。

先頭からi桁が等しいとする。つまり、新しいパスワードがoldPasswordと異なる最上位の桁をi(0-indexed)とする。この桁の値によって新しいパスワードがoldPasswordより大きいか小さいかが確定する。

(1)新しいパスワードのほうが大きい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最小値

(2)新しいパスワードのほうが小さい場合

dp[mask] = 使用した値がmaskであるときの新しいパスの最大値

の2種類のDPを解けば答えが求まる。

iは総当たりで固定。各iについてビットDPするので全体で

O(2^n＊n^2)

 

ミス

1<=oldPassword<=10^16-1

なのでoldPasswordは最大16桁ある。

配列を1<<15のサイズしか確保してなかった。

AtCoder AGC010 C - Cleaning

エディトリアルの判定

L>=min(max(c[i]), Σ(c[i])/2)
がよくわからなかった。

以下、条件判定の考察のみ
変数名はエディトリアルのものを踏襲

葉ではない頂点をv、
m = max(c[i])
とする。

T >= 0 (1)
は自明。

A[v]が最大になるのは
子供=>v=>親　を含む経路がすべてで
子供x=>v=>子供y (x!=y) を含む経路が１つもない場合であり、
A[v] <= Σ(c[i]) (2)
が成り立つ。

m = c[u] を満たす頂点uについて
u=>v=>x (xはvの親またはuでないvの子供)
を含む経路がc[u]個あるので
vを含む経路の数A[v]は
m<=A[v] (3)
を満たす。

逆に(1)～(3)が成り立つと仮定する。
T + (Σc[i]-T)/2 = A[v]
を整理すると
T = 2A[v] - Σc[i]
よって
L
= (Σc[i]-T)/2
= (Σc[i]-(2A[v]-Σc[i]))/2
= (2Σc[i]-2A[v])/2
= Σc[i]-A[v]
L個以上のペアが作れるかどうか判定したいのだった。
これは
ペアとならないものがH=Σc[i]-2L　個以下である
ことと同値。
H
= Σc[i]-2L
= Σc[i]-2*(Σc[i]-A[v])
= 2A[v]-Σc[i]
ここで
(2),(3)より
m<=Σ(c[i])
なので
H<=2A[v]-m (4)

ペアとならないものは
H' = m
個以下にすることができる。
vの子をc[i]の昇順に見ていく。
簡単のためi<jならばc[i]<=c[j]とする。
l個まで子を見たとき、子i<=lについてペアとならないものがc[l]個以下となるようにペアを作れる
これは帰納法で示せる。
よってすべての(k個の)子供を全部見たとき
ペアとならないものをH'個以下にできている。

H'<=H
を示す。
H-H'
= (2A[v]-m) - m
= 2(A[v]-m)
>= 2(m-m) // (3)より
= 0
∴ H>=H'
ペアとならないものをH個以下にできた。

以上から、条件判定は(1)～(3)だけでよい。

 

解法まとめ

根付き木にして各頂点とその親をつなぐ辺を頂点ごとに処理する。根の処理だけ特殊なので注意。

AtCoder AGC010 A - Addition

解法

偶奇だけみればいい。

操作は以下の2種類だけ。

(偶数)+(偶数) = (偶数)

(奇数)+(奇数) = (偶数)

奇数が奇数個あるとき、奇数同士を全部くっつけていっても、最後に奇数が1個に対して偶数が1個以上となり、詰む。

そうでないとき、つまり奇数が偶数個ならば、奇数同士を全部くっつけて0個以上の偶数になる。あとは、もともとの偶数ともくっつけていけばいい。

 

まとめなど

値は偶奇しか見なくていい。

AtCoder AGC010 B - Boxes

解法

N=1のときは明らかにYES

 

以下、N>=2とする。

1回の操作で合計

b=1+2+...+N = N*(N+1)/2

足される。なので

Σ(A[i])がbで割り切れないときはNOとする。

操作回数をtとすると

t = Σ(A[i])/b

ここで数列cを以下のように定める

c[i] = b[(i+1) mod n] - b[i] (0<=i<=n-1)

仮にN=5として

a[i]に

-3, -4, -5, -1, -2

の操作をしたとすると

c[i]の増減は

-1, -1, +4, -1, -1

となる。

一般化してc[i]の増減は

-1, -1, ..., +(N-1), ...,-1, -1

のように表せる。

このc[i]の増減を分解すると

-1, -1, ..., -1, -1 (①)

0, 0, ..., +N, ..., 0, 0 (②)

(②の操作は任意の1箇所で＋N)

このように

①の操作と②の操作を別々にすると簡単。

数列cに①の操作をt回すると

d[i] = c[i] - t

が得られる。

あとは②の操作をdに対してt回適用して

すべて0にできればYES

 

まとめなど

必要条件を詰めていって、それが十分条件であることが直感的にわかればいい。階差数列の増減が単純。1回の操作を分解する。