はまやんはまやんはまやん

hamayanhamayan's blog

AtCoder Beginner Contest 056 / AtCoder Beginner Contest 070 解説

http://abc056.contest.atcoder.jp
http://arc070.contest.atcoder.jp

以下、解説


























A. HonestOrDishonest

http://abc056.contest.atcoder.jp/submissions/1171493
場合分けをして、同じ文字なら正直、そうでないなら嘘つき

B. NarrowRectanglesEasy

http://abc056.contest.atcoder.jp/submissions/1171495
まず、A<Bにしておく。
ダブっているならば0で、ダブっていないならばAの右端(A+W)とBの左端(B)の差が答えになる

C. Go Home

http://abc056.contest.atcoder.jp/submissions/1171500
点数を見て、この解法にした。
1+2+3+...をして和が初めてX以上となる日にちが答え。
Xを超えてしまっても、上手いこと調整してぴったりにできる

D. No Need

http://arc070.contest.atcoder.jp/submissions/1172088

解説にもありますが、条件の読み替えから。
https://atcoder.jp/img/arc070/editorial.pdf
「カードiが不必要」⇔「A[i]以外で総和がK-A[i]以上K未満の集合が取れる」

まずNaive解法から。
配列は1-indexedとする。
L[i][j] := [1,i]の範囲の数を使ってjを作れるか(0or1)
R[i][j] := [i,N]の範囲を使ってjを作れるか(0or1)
として、DPをしておく(pre関数)
「配列L,Rのそれぞれでjを作る、kを作る」というのを全探索すると、「K-A[i] <= j+k < K」を満たすパターンがあるかを探すので、O(NK^2)となる(部分点)。

正答は、判定検索を高速化することを考える。
「配列L,Rのそれぞれでjを作る、kを作る」というのを全探索する代わりに「配列Lでjを作る」ことだけ全探索する。
配列Lでjを作ると、配列Rで必要なkの条件は、上記の式を変形すると、「K-j-A[i] <= k < K - j」である。
つまり、配列Rのこの範囲に1つでも1があれば作れることになるため、これを高速に判定する。
このために配列Rを累積和的な定義に変える。
R[i][j] := sum{k=i,...,N}([k,N]の範囲を使ってjを作れるか(0or1))
こうすると、この範囲での配列Rの和が、R[i+1][K-j-1]-R[i+1][K-j-A[i]-1]で取れるので、これでO(NK)まで落せて答え。

戻すDPでも解けるようです。
hamayanhamayan.hatenablog.jp