コンテンツにスキップ

DP

タグ「DP」の記事 8 件

競プロキャンプ2026関西 F - Keep Far

NN 個の座席が一列に並んでいて、KK 人が順に 1 人ずつ座ります。各人は、左右の両隣に誰も座っていない空席があればその中から 1 つを選び、なければ空席から好きに 1 つを選んで座ります。最終的に座っている席が文字列 SS の # の位置と一致するような座り方の個数を、998244353998244353 で割った余りで求める問題です(1≤K≤N≤30001 \le K \le N \le 3000、# はちょうど KK 個)。

両隣に誰も座っていない空席を「よい席」と呼びます。座り方は 2 つの段階に分かれます。

  • 前半:よい席がある間は、よい席に座ります。前半に座る席の集合を II とすると、II のどの 2 席も隣り合いません。
  • 後半:よい席がなくなったら、残りの人は好きな空席に座ります。人が増えるとよい席は減る一方なので、後半によい席が復活することはありません。

前半が終わるのは、II に入っていないどの席にも、隣に II の席があるときです。

KK 人とも、座る時点で両隣が空いています。よって、どの順に座ってもルールに従っていて、答えは K!K! です。

隣り合う 2 席のうち後に座る人は、よい席でない席に座るので、後半に座っています。よって、前半は最後まで終わっていなければなりません。つまり II は次の条件を満たします。

  • II は # の席だけからなり、どの 2 席も隣り合わない。
  • II に入っていない席(. の席も含む)はすべて、隣に II の席がある。

特に、どの # とも隣り合わない . があれば、この条件を満たす II はないので答えは 00 です。

逆に、条件を満たす II を 1 つ決めて ∣I∣=i|I| = i とすると、前半の ii 人は II の席に好きな順で座れて i!i! 通り、後半の K−iK - i 人は残りの # の席に好きな順で座れて (K−i)!(K - i)! 通りです。したがって、条件を満たす II のうち ∣I∣=i|I| = i のものの個数を cic_i として、答えは

∑ii! (K−i)! ci\sum_{i} i! \, (K - i)! \, c_i

です。

II の席を左から p1<p2<⋯<pip_1 < p_2 < \dots < p_i とすると、条件は次のように言い換えられます。

  • どの pjp_j も # の席である。
  • pj+1−pjp_{j+1} - p_j は 22 か 33 である(隣り合わず、間の席はどれも II の席と隣り合う)。
  • p1p_1 は 11 か 22、pip_i は N−1N - 1 か NN である(両端の席も II の席と隣り合う)。

そこで、席を左から見ていき、「直前に選んだ席が何個前か」と「これまでに選んだ個数」を状態にして DP をします。計算量は O(N2)O(N^2) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/utility/container_func.hpp"
using mint = modint998244353;
using C = Combination<mint>;
void solve() {
LL(N, K);
STR(S);
ll full = true;
rep(i, N) {
if (S[i] == '#')
continue;
if (i > 0 && S[i - 1] == '#')
continue;
if (i < N - 1 && S[i + 1] == '#')
continue;
full = false;
}
rep(i, 1, N) {
if (S[i - 1] == '#' && S[i] == '#' && !full) {
print(0);
return;
}
}
if (not full) {
print(C::factorial(K));
return;
}
ary<vec<mint>, 3> dp = {vec<mint>(N + 1), vec<mint>(N + 1), vec<mint>(N + 1)};
dp[1][0] = 1;
for (char c : S) {
vec<mint> ndp(N + 1);
if (c == '#') {
rep(i, 1, N + 1) {
ndp[i] += dp[0][i - 1];
ndp[i] += dp[1][i - 1];
}
}
std::swap(dp[0], dp[1]);
std::swap(dp[1], dp[2]);
std::swap(dp[2], ndp);
}
mint ans = 0;
rep(i, K + 1) {
ans += C::factorial(K - i) * C::factorial(i) * (dp[1][i] + dp[2][i]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

full は「どの . の席も # の席と隣り合う」かどうかです。full でないときは、隣り合う # があれば 00、なければ K!K! を出力します。full のときは、隣り合う # がなくても DP に進みますが、そのときは II がすべての # の席になるしかないので、DP でも K!K! が求まります。

DP では、今の席を見る直前の時点で、dp[2][i] が「直前の席を選んだ」、dp[1][i] が「2 つ前の席を選んだ」、dp[0][i] が「3 つ前の席を選んだ」状態で、ii 個選んだときの場合の数です。今の席が # なら、dp[0] と dp[1] から今の席を選べます。そのあと 3 つの配列をずらして、次の席から見た状態にしています。はじめに dp[1][0] = 1 としているのは、席 11 の 2 つ左に仮の席が選ばれているとみなすためで、こうすると最初に選ぶ席は 11 か 22 になります。最後は、最後に選んだ席が NN か N−1N - 1 である dp[2] と dp[1] を使います。

modint998244353 は 998244353998244353 で割った余りで計算する整数型で、C::factorial(n) は n!n! を返します。場合の数は非常に大きくなるので、DP の配列も mint にしておく必要があります。

使用ライブラリ:cpp_include@9c33ee7

DOJ Beginner Contest 12 E - Shirogane Wants to Sing

長さ NN の非負整数列 AA が与えられます。次の条件をすべて満たす長さ NN の非負整数列 BB の個数を 109+710^9 + 7 で割った余りを求める問題です。

  • B1=0B_1 = 0。
  • すべての 1≤i<N1 \le i < N について ∣Bi−Bi+1∣≤K|B_i - B_{i+1}| \le K。
  • ∑i=1N∣Ai−Bi∣≤E\sum_{i=1}^{N} |A_i - B_i| \le E。

制約は 2≤N≤1002 \le N \le 100、0≤K≤200 \le K \le 20、0≤E≤500 \le E \le 50、0≤Ai≤500 \le A_i \le 50 です。

BB を前から 1 つずつ決めていく DP をします。次の値を決めるのに必要なのは、直前の値 BiB_i と、それまでの誤差の合計だけです。そこで

dpi[e][b]=(B1,…,Bi のうち、誤差の合計が e で Bi=b であるものの個数)\mathrm{dp}_i[e][b] = (B_1, \dots, B_i \text{ のうち、誤差の合計が } e \text{ で } B_i = b \text{ であるものの個数})

とします。dp1\mathrm{dp}_1 は dp1[A1][0]=1\mathrm{dp}_1[A_1][0] = 1 だけが 11 です(A1>EA_1 > E なら答えは 00 です)。dpi[e][b]\mathrm{dp}_i[e][b] から、∣b−b′∣≤K|b - b'| \le K を満たす各 b′b' について、e′=e+∣Ai+1−b′∣≤Ee' = e + |A_{i+1} - b'| \le E なら dpi+1[e′][b′]\mathrm{dp}_{i+1}[e'][b'] に足します。答えは dpN\mathrm{dp}_N の値の総和です。

BiB_i のとりうる範囲は有限です。∣Ai−Bi∣≤E|A_i - B_i| \le E なので、Bi≤Ai+E≤max⁡A+EB_i \le A_i + E \le \max A + E です。よって bb は 00 以上 M=max⁡A+E≤100M = \max A + E \le 100 以下だけを考えれば十分です。

計算量は O(NEMK)O(NEMK) で、最大でも 100×51×101×41≈2×107100 \times 51 \times 101 \times 41 \approx 2 \times 10^7 回程度です。

Python
MOD = 10**9 + 7
N, K, E = map(int, input().split())
A = list(map(int, input().split()))
if A[0] > E:
print(0)
exit(0)
M = max(A) + E
dp = [[0 for i in range(M + 1)] for j in range(E + 1)]
dp[A[0]][0] = 1
for a in A[1:]:
ndp = [[0 for i in range(M + 1)] for j in range(E + 1)]
for i in range(E + 1):
for j in range(M + 1):
for k in range(j - K, j + K + 1):
if k not in range(M + 1):
continue
if abs(a - k) + i > E:
continue
ndp[abs(a - k) + i][k] += dp[i][j]
ndp[abs(a - k) + i][k] %= MOD
dp = ndp
print(sum(sum(a) % MOD for a in dp) % MOD)

dp[i][j] が、誤差の合計が i で直前の値が j である数列の個数です。k が次の値 Bi+1B_{i+1} の候補で、範囲 [0,M][0, M] から外れるものと、誤差の合計が EE を超えるものを飛ばしています。

DOJ Beginner Contest 12 F - Half Shuffle

長さ 2N2N の順列 PP が与えられます。1 回の操作では、相異なる位置をちょうど NN 個選び、そこにある値を好きな順に並べ替えます。PP を昇順に並べるのに必要な操作回数の最小値を求める問題です(2≤N≤30002 \le N \le 3000、全テストケースの NN の総和は 30003000 以下)。

PP を巡回置換に分解し、長さが 22 以上のサイクルの長さを l1,…,lkl_1, \dots, l_k とします。正しい位置にない値の個数は s=l1+⋯+lks = l_1 + \dots + l_k です。答えは次のとおりです。

  • s=0s = 0 なら 00 回。
  • 1≤s≤N1 \le s \le N なら 11 回。
  • s>Ns > N で、「s<2Ns < 2N」または「いくつかのサイクルの長さの和をちょうど NN にできる」なら 22 回。
  • それ以外(s=2Ns = 2N で、和を NN にできない)なら 33 回。

1 回の操作で動かせるのは NN 個なので、1 回で済むのは s≤Ns \le N のときだけです。このときは、正しい位置にない位置をすべて選び、足りない分は正しい位置にある位置で埋めて、そのまま並べ直せば終わります。

s>Ns > N なら 2 回以上かかります。

いくつかのサイクルの長さの和がちょうど NN なら、1 回目にそれらのサイクルの位置を選んで正しく並べます。残りは s−N≤Ns - N \le N 個なので、2 回目で終わります。

s<2Ns < 2N のときも 2 回でできます。サイクルの一部を 1 回の操作で直す方法を考えます。サイクル x→Px→PPx→⋯x \to P_x \to P_{P_x} \to \cdots から、つながった rr 個の位置を選びます。そこに並ぶ値のうち r−1r - 1 個は、正しい位置が選んだ位置の中にあります。よって、この操作で r−1r - 1 個を正しい位置に置けて、サイクルの長さは r−1r - 1 だけ短くなります。1 回目では、サイクルを丸ごと選べるだけ選び、残りの rr 個の枠は次のサイクルの一部で埋めます。すると、正しい位置に置ける値は N−1N - 1 個以上になります。残りは s−(N−1)≤Ns - (N - 1) \le N 個なので、2 回目で終わります。

逆に s=2Ns = 2N のときに 2 回でできたとします。1 回目に選ばなかった NN 個の位置は、1 回目のあとも正しくないままです。2 回目で動かせるのは NN 個なので、1 回目に選んだ NN 個の位置は、1 回目ですべて正しくならなければいけません。そのためには、選んだ位置にある値の正しい位置が、すべて選んだ位置の中になければなりません。これは、選んだ位置がいくつかのサイクルの和集合であることを意味します。つまり、サイクルの長さの和をちょうど NN にできなければ、2 回ではできません。

上の「サイクルの一部を直す」方法で 1 回操作すると、残りは s−(N−1)≤N+1<2Ns - (N - 1) \le N + 1 < 2N 個になります(N≥2N \ge 2 です)。ここから 2 回で終わるので、どの場合も 3 回あれば十分です。

サイクルの長さの和を NN にできるか

Section titled “サイクルの長さの和を NNN にできるか”

部分和問題の DP で判定します。dp[j]\mathrm{dp}[j] を「いくつかのサイクルを選んで長さの和を jj にできるか」として、サイクルを 1 つずつ加えて更新します。サイクルは高々 NN 個なので、計算量は O(N2)O(N^2) です。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(lambda x: int(x) - 1, input().split()))
visited = [False] * (2 * N)
l = []
for i in range(2 * N):
if visited[i]:
continue
x = i
visited[x] = True
r = [x]
while i != P[x]:
x = P[x]
visited[x] = True
r.append(x)
if len(r) > 1:
l.append(len(r))
s = sum(l)
dp = [0] * (N + 1)
dp[0] = 1
for x in l:
for i in reversed(range(x, N + 1)):
dp[i] |= dp[i - x]
if s == 0:
print(0)
elif s <= N:
print(1)
elif dp[N] or s < 2 * N:
print(2)
else:
print(3)

前半では、まだ見ていない位置 i から P をたどってサイクルを取り出し、長さが 22 以上ならその長さを l に入れています。後半の dp は部分和問題の DP で、i を大きいほうから回すことで、同じサイクルを 2 回使わないようにしています。

ABC480 F - Cake Cutting

大きさ A1,…,ANA_1, \dots, A_N の NN 個のケーキを MM 人に配ります。大きさの総和を SS とし、SS は MM の倍数です。ケーキを 1 つ選んで自由に 2 つに切り分ける操作を何回か行ったあと、全員がもらう大きさの合計がちょうど S/MS / M になるように配りたいです。操作回数の最小値を求める問題です(1≤N≤201 \le N \le 20、1≤M≤1001 \le M \le 100、1≤Ai≤1091 \le A_i \le 10^9)。

t=S/Mt = S / M とします。

ケーキを cc 個のグループに分けて、どのグループも大きさの和が tt の倍数になるようにできたとします。このとき、操作回数 M−cM - c で配れます。グループを順に一列に並べて、先頭から長さ tt ずつ切っていけばよいからです。M−1M - 1 か所の切れ目のうち、グループの境目にある c−1c - 1 か所はケーキを切らずに済むので、切る回数は高々 (M−1)−(c−1)=M−c(M - 1) - (c - 1) = M - c です。

逆に、どんな配り方でも操作回数は M−cM - c 以上です。ケーキと人を頂点とし、人がケーキの一部をもらっているときにその 2 つを辺で結んだグラフを考えます。各辺は 1 つ以上の切れ端に対応するので、切れ端の個数は辺の本数 EE 以上です。1 回の操作で切れ端は 1 個増えるので、操作回数は E−NE - N 以上です。グラフの連結成分の個数を cc とすると、頂点は N+MN + M 個なので E≥N+M−cE \ge N + M - c で、操作回数は M−cM - c 以上になります。各連結成分のケーキの大きさの和は、そこに含まれる人数の tt 倍です。また、どの人もケーキをもらうので、どの連結成分にもケーキが含まれます。よって、連結成分ごとにケーキを分ければ、和が tt の倍数になる cc 個のグループができます。

したがって答えは、「ケーキを、大きさの和がどれも tt の倍数になるようにグループ分けするときのグループの個数の最大値」を cc として、M−cM - c です。

ケーキを一列に並べて、先頭からの和が tt の倍数になる位置で区切ると考えれば、グループ分けは並べ方と対応します。グループの個数は、先頭からの和が tt の倍数になる位置の個数(最後のケーキの後ろも含む)です。

そこで、ケーキの集合 UU に対して、dp[U]\mathrm{dp}[U] を「UU のケーキを先頭に並べるとき、UU の中で先頭からの和が tt の倍数になる位置の個数の最大値」とします。UU の最後に置くケーキ ii で場合分けすると、

dp[U]=max⁡i∈U(dp[U∖{i}]+[∑j∈UAj≡0(modt)])\mathrm{dp}[U] = \max_{i \in U} \left( \mathrm{dp}[U \setminus \{i\}] + [\textstyle\sum_{j \in U} A_j \equiv 0 \pmod t] \right)

です。[⋯ ][\cdots] は条件が成り立てば 11、成り立たなければ 00 を表します。答えは M−dp[{1,…,N}]M - \mathrm{dp}[\{1, \dots, N\}] です。

計算量は O(2NN)O(2^N N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/bit.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
VL(A, N);
ll t = sum(A) / M;
val<2> dp(1 << N, al<2>{-1, 0});
dp[0] = {0, 0};
rep(u, 1, 1 << N) {
for (auto [i, v] : remove_one(u)) {
ll y = (dp[v][1] + A[i]) % t;
chmax(dp[u], al<2>{dp[v][0] + (y == 0), y});
}
}
print(M - dp.back()[0]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dp[u] は 2 つの値の組で、dp[u][0] が上の dp[U]\mathrm{dp}[U]、dp[u][1] が UU のケーキの大きさの和を tt で割った余りです。余りは UU だけで決まるので、組を辞書順で chmax しても、dp[u][0] の最大値がとられます。remove_one(u) は、u に含まれる位置 i と、u から i を除いた集合 v の組を列挙します。

使用ライブラリ:cpp_include@9c33ee7

DOJ Beginner Contest 9 E - 67

長さ NN の十進数 SS が与えられます。SS からいくつかの文字を消し、残った文字をそのままの順で並べた数を 66 の倍数か 77 の倍数にしたい問題です。残す文字は 11 個以上で、先頭が 00 になってもかまいません(00 も 66 と 77 の倍数です)。消す文字の個数の最小値を求め、できなければ −1-1 を出力します。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

42=6×742 = 6 \times 7 は 66 でも 77 でも割り切れるので、ある数が 66 の倍数か 77 の倍数かは、その数を 4242 で割った余り mm だけで決まります。mm が 66 の倍数か 77 の倍数であれば条件を満たします。

SS を先頭から 1 文字ずつ見ていき、

dp[m]=残した文字が表す数を 42 で割った余りが m になるときの、消した文字数の最小値\mathrm{dp}[m] = \text{残した文字が表す数を } 42 \text{ で割った余りが } m \text{ になるときの、消した文字数の最小値}

を更新します。最初は何も残していないので、dp[0]=0\mathrm{dp}[0] = 0、それ以外は ∞\infty です。

次の文字が数字 xx のとき、各 mm について 2 通りの遷移があります。

  • 消す:余りは mm のままで、消した文字数が 11 増えます。
  • 残す:余りは (10m+x) mod 42(10m + x) \bmod 42 になり、消した文字数は変わりません。

最後に、mm が 66 の倍数か 77 の倍数であるものについて dp[m]\mathrm{dp}[m] の最小値をとります。

ただし、全部消した場合も「余り 00、消した文字数 NN」として dp[0]\mathrm{dp}[0] に含まれています。残す文字は 11 個以上という条件があるので、dp[m]<N\mathrm{dp}[m] < N のものだけを答えの候補にします。候補がなければ −1-1 です。

計算量は O(42∑N)O(42 \sum N) です。

Python
for _ in range(int(input())):
N = int(input())
S = input()
dp = [float("inf")] * 42
dp[0] = 0
for c in S:
x = int(c)
ndp = [float("inf")] * 42
for i in range(42):
ndp[i] = dp[i] + 1
for i in range(42):
j = (i * 10 + x) % 42
ndp[j] = min(ndp[j], dp[i])
dp = ndp
ans = float("inf")
for i in range(42):
if i % 6 == 0 or i % 7 == 0:
if dp[i] < N:
ans = min(ans, dp[i])
if ans == float("inf"):
ans = -1
print(ans)

yukicoder contest 517 D - Streaming Schedule

NN 日間、毎日「配信する」か「休む」かを選びます。ii 日目に配信するとファンが AiA_i 人増え、休むと何も起きません(1≤Ai≤1091 \le A_i \le 10^9)。

ただし、BB 日以上続けて休むことはできず、CC 日以上続けて配信することもできません(2≤B,C≤N+12 \le B, C \le N + 1)。増えるファンの人数の最大値を求めてください(N≤3×105N \le 3 \times 10^5)。

配信が続く区間を「配信区間」と呼びます。配信区間の長さは C−1C - 1 以下、休みが続く区間の長さは B−1B - 1 以下でなければなりません。

3 日以上続く休みは考えなくてよい

Section titled “3 日以上続く休みは考えなくてよい”

Ai≥1A_i \ge 1 なので、配信する日は多いほうが得です。3 日以上続く休みがあれば、その真ん中の 1 日を配信に変えられます。この日の両隣は休みのままなので、長さ 1 の配信区間ができるだけです。C≥2C \ge 2 なので長さ 1 の配信区間は必ず許され、休みの区間も短くなるだけなので、条件は崩れません。しかもファンは増えます。

したがって、最適解では休みは 2 日までしか続きません。B=2B = 2 なら連続休みは 1 日まで、B≥3B \ge 3 なら 2 日まで許されます。以下では、B≥3B \ge 3 のときは連続休みの長さに上限を設けずに計算します。上限を超える休み方は、真ん中を配信に変えたものより必ず悪いので、最大値は変わりません。

resti\mathrm{rest}_i を「ii 日目に休むときの、ii 日目までのファンの増加数の最大値」とします。ii 日目に休む直前の状況で場合分けします。

  • 前日も休み:resti−1\mathrm{rest}_{i-1}。B≥3B \ge 3 のときだけ選べます。
  • 前日まで配信区間:配信区間が jj 日目から i−1i - 1 日目までなら、j−1j - 1 日目は休みです。値は restj−1+(Aj+⋯+Ai−1)\mathrm{rest}_{j-1} + (A_j + \dots + A_{i-1}) で、配信区間の長さの制約から i−(C−1)≤j≤i−1i - (C - 1) \le j \le i - 1 です。
  • ii 日目が 1 日目:何もしていないので 00 です。

1 日目より前の日を「0 日目に休んだ」とみなして rest0=0\mathrm{rest}_0 = 0 とおくと、配信区間が 1 日目から始まる場合も 2 つ目の式で扱えます。ただし、1 日目に休むときに「前日も休み」の場合として扱うと、B=2B = 2 では選べなくなってしまいます。そこで 1 日目に休む場合は、BB によらず 00 とします(下の補足も参照)。

最終日に休む場合の答えは restN\mathrm{rest}_N、最終日まで配信する場合の答えは jj 日目から NN 日目までの配信区間を使った同じ式で求まります。

累積和 Si=A1+⋯+AiS_i = A_1 + \dots + A_i を使うと、2 つ目の式は

restj−1+Si−1−Sj−1=(restj−1−Sj−1)+Si−1\mathrm{rest}_{j-1} + S_{i-1} - S_{j-1} = (\mathrm{rest}_{j-1} - S_{j-1}) + S_{i-1}

と書けます。ii が 1 増えると、jj の範囲は 1 つずつ右にずれます。したがって、長さ C−1C - 1 の窓の中での restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} の最大値が分かればよく、これは deque を使ったスライド最大値で求まります。

計算量は O(N)O(N) です。

最初は 1 日目に休む場合も「前日も休み」として扱っていて、WA になりました。たとえば N=2,B=2,C=2,A=(8,9)N = 2, B = 2, C = 2, A = (8, 9) では、1 日目に休んで 2 日目に配信する 99 が正解です。しかし、1 日目の休みを「0 日目からの連続休み」とみなすと、B=2B = 2 で禁止されて 88 になってしまいます。0 日目は実際には休みではないので、1 日目だけは BB によらず休めるようにする必要があります。

Python
from collections import deque
N, B, C = map(int, input().split())
A = list(map(int, input().split()))
t = 0
k = 0
d = deque()
e = deque()
for i, a in enumerate(A):
if d:
u = e[0] + k
else:
u = -(10**18)
if B > 2 or i == 0:
u = max(u, t)
d.append(t - k)
e.append(t - k)
while len(e) >= 2 and e[-2] < e[-1]:
x = e.pop()
e.pop()
e.append(x)
k += a
while len(d) >= C:
x = d.popleft()
if len(e) > 0 and e[0] == x:
e.popleft()
t = u
print(max(t, max(d) + k))

変数の意味は次のとおりです。

  • t:前日に休んだときの最大値(resti−1\mathrm{rest}_{i-1})
  • k:前日までの累積和(Si−1S_{i-1})
  • u:その日に休んだときの最大値(resti\mathrm{rest}_i)
  • d:配信区間の始まりの候補 jj について、restj−1−Sj−1\mathrm{rest}_{j-1} - S_{j-1} を並べた窓。最大 C−1C - 1 個を持ちます。
  • e:d のうち、後ろにより大きい値がないものだけを残した deque。先頭が窓の中の最大値です。

d から要素を捨てるときは、その値が e の先頭と等しければ e からも捨てます。値しか比べていませんが、別の要素を取り違えることはありません。捨てる要素 xx が e から消えているなら、xx より後に xx より大きい値が窓の中にあります。そのため e の先頭(窓の最大値)は xx より大きく、等しくはなりません。最後の max(d) + k は、最終日まで配信する場合の値です。

SamCoding Round 7 (Div. 2) K - Blueprints Washed by the Rain

正の整数の列 b1,…,bnb_1, \dots, b_n に対して、g(b)ig(b)_i を「ii より左にあって bj<bib_j < b_i を満たす jj のうち最大のもの(なければ 00)」と定めます。ある bb によって y=g(b)y = g(b) と書ける列 yy を「復元可能」と呼びます。

長さ nn の列 xx が与えられます。xx のいくつかの要素は −1-1 です。−1-1 をそれぞれ 00 以上 nn 以下の整数に置き換えて xx を復元可能にする方法の数を、109+710^9 + 7 で割った余りで求めてください(nn の総和 ≤5000\le 5000)。

bb の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n1, \dots, n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。gg の定義が真の不等号 bj<bib_j < b_i なので、こうすると「bj<bib_j < b_i」と「jj のほうが小さい(j<ij < i のとき)」が一致します。

このとき、ii の左部分木はちょうど区間 [gi+1,i−1][g_i + 1, i - 1] になります。ii の左部分木は「ii から左へ、ii より大きい要素が続く範囲」で、その左端の外側が ii より左で最も近い小さい要素、つまり gig_i だからです。

gg とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。

  • 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
  • ii を追加するときは、bib_i より大きい要素をスタックから pop する。pop した部分が ii の左部分木になり、ii は残ったスタックの一番上の右の子になる。最後に ii を push する

pop し終わったときのスタックの一番上が、ちょうど gig_i です(空なら 00)。そのため、各ステップで何個 pop するかは gg から決まり、ツリーの形も gg から決まります。逆に、どんな形のツリーにも、それを作る bb が存在します(例えば、根からの深さをそのまま bb にすればよいです)。

まとめると、復元可能な yy と、nn 頂点の二分木の形は一対一に対応します。全部が −1-1 のときの答えは Catalan 数 CnC_n で、サンプル 3 の 132=C6132 = C_6 と一致します。

例えば g=[0,1,2,1,0,0,6]g = [0, 1, 2, 1, 0, 0, 6] に対応するツリーの親は、[5,4,2,1,6,−,6][5, 4, 2, 1, 6, -, 6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3][g_4 + 1, 3] = [2, 3] になっていることなどが確かめられます。

この対応を使うと、問題は次のように言い換えられます。

頂点 1,…,n1, \dots, n を中間順に並べた二分木のうち、xi≠−1x_i \ne -1 であるすべての ii について「ii の左部分木がちょうど [xi+1,i−1][x_i + 1, i - 1] である」ものを数える

xi≥ix_i \ge i のときは、そのような左部分木はありえないので答えは 00 です。

固定された左部分木は独立に数えられる

Section titled “固定された左部分木は独立に数えられる”

xi≠−1x_i \ne -1 のとき、ii の左部分木 [xi+1,i−1][x_i + 1, i - 1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと ii に潰してしまえば、ii は「左の子を持たない頂点」 として扱えます。

そこで、左から順に頂点を見ながら、次のように列を潰していきます。

  • xi=−1x_i = -1 のとき:ii を「自由な頂点」として列の末尾に加える
  • xi≠−1x_i \ne -1 のとき:列の中から xi+1x_i + 1 以降に始まる要素をすべて取り出す。それらが ii の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1x_i + 1 から ii までをまとめて「左の子を持たない頂点」1 個として末尾に加える

列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1x_i + 1 から始まる要素になっていないとき、つまり xi+1x_i + 1 がすでに潰された要素の内側にあるときは、答えは 00 です。ii の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。

最後に残った列全体の形の数も掛ければ、答えになります。

左の子を持たない頂点を含む二分木の数え上げ

Section titled “左の子を持たない頂点を含む二分木の数え上げ”

あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。

Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが hh のとき、次の頂点を追加する方法は次のとおりです。

  • 自由な頂点:00 個以上 hh 個以下を pop してから push するので、新しい高さは 11 以上 h+1h + 1 以下
  • 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1h + 1

pop の仕方とツリーの形は一対一に対応するので、dp[h]\mathrm{dp}[h] を「スタックの高さが hh になる方法の数」とする DP で数えられます。自由な頂点の遷移は

dp′[h′]=∑h≥h′−1dp[h]\mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h]

なので、後ろからの累積和で O(長さ)O(\text{長さ}) で計算できます。答えは最後の dp\mathrm{dp} の総和です。

各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ mm の列の DP は O(m2)O(m^2) なので、全体で O(n2)O(n^2) です。

Python
from bisect import bisect_left
from itertools import accumulate
MOD = 10**9 + 7
def count(flags):
dp = [1]
for f in flags:
if f:
dp = [0] + dp
else:
s = list(accumulate(reversed(dp)))
s.reverse()
dp = [0] + [v % MOD for v in s]
return sum(dp) % MOD
def solve(n, x):
ans = 1
starts = []
flags = []
for i in range(1, n + 1):
if x[i - 1] == -1:
starts.append(i)
flags.append(False)
continue
l = x[i - 1] + 1
if l > i:
return 0
k = bisect_left(starts, l)
if l < i and (k == len(starts) or starts[k] != l):
return 0
ans = ans * count(flags[k:]) % MOD
del starts[k:]
del flags[k:]
starts.append(l)
flags.append(True)
return ans * count(flags) % MOD
t = int(input())
for _ in range(t):
n = int(input())
x = list(map(int, input().split()))
print(solve(n, x))

starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、xi+1x_i + 1 から始まる要素を bisect_left で探しています。

count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。

Blitz Round #25 D - Shifting Sort

長さ nn の正整数列 a1,…,ana_1, \ldots, a_n があります。次の操作を好きな回数行えます。

  • 添字 ii を選ぶ。操作を始める前の aia_i の最上位ビットの位置を kk として、aia_i の下位 k+1k + 1 ビットを左に 1 つ巡回シフトする

たとえば 4=(100)24 = (100)_2 は (100)2→(001)2→(010)2→(100)2→⋯(100)_2 \to (001)_2 \to (010)_2 \to (100)_2 \to \cdots と変化します。

数列を広義単調増加にするのに必要な操作回数の最小値を求め、不可能なら −1-1 を出力する問題です。

  • 1≤n≤2⋅1051 \le n \le 2 \cdot 10^5、1≤ai≤2⋅1051 \le a_i \le 2 \cdot 10^5、テストケースの nn の総和は 2⋅1052 \cdot 10^5 以下

正確な問題文は元の問題ページを見てください。

aia_i のビット長を wiw_i とすると、操作は aia_i を wiw_i ビット幅で回転させるだけなので、aia_i がとりうる値は

ai を r 回回転させた値(0≤r<wi)a_i \text{ を } r \text{ 回回転させた値} \quad (0 \le r < w_i)

の wiw_i 通りで、そのときの操作回数は rr です。途中で最上位ビットが 00 になっても、回転の幅は操作前のビット長のまま変わらないことに注意します。

各要素の候補は高々 wiw_i 個しかないので、前から順に

dpi[v]=ai を値 v にしたときの、a1,…,ai を広義単調増加にする最小操作回数\mathrm{dp}_i[v] = a_i \text{ を値 } v \text{ にしたときの、} a_1, \ldots, a_i \text{ を広義単調増加にする最小操作回数}

を候補ごとに持つ DP ができます。遷移は

dpi[v]=r+min⁡u≤vdpi−1[u]\mathrm{dp}_i[v] = r + \min_{u \le v} \mathrm{dp}_{i-1}[u]

です。前の要素の候補と今の要素の候補をそれぞれ値でソートしておけば、min⁡u≤v\min_{u \le v} は尺取りで前から最小値を更新していくだけで求まります。

答えは min⁡vdpn[v]\min_v \mathrm{dp}_n[v] で、これが ∞\infty なら −1-1 です。

L=⌊log⁡2max⁡ai⌋+1L = \lfloor \log_2 \max a_i \rfloor + 1 とすると、候補は各要素で高々 LL 個なので、計算量はソートを含めて O(nLlog⁡L)O(n L \log L) です。

Python(upsolve)
INF = float("inf")
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
dp = [(0, 0)]
for a in A:
w = a.bit_length()
cand = []
x = a
for r in range(w):
cand.append((x, r))
x = (x << 1 | x >> (w - 1)) & ((1 << w) - 1)
cand.sort()
ndp = []
best = INF
p = 0
for q, r in cand:
while p < len(dp) and dp[p][0] <= q:
best = min(best, dp[p][1])
p += 1
ndp.append((q, best + r))
dp = ndp
ans = min(y for _, y in dp)
if ans == INF:
print(-1)
else:
print(ans)

dp は (値, 最小操作回数) の組を値の昇順に並べたもので、best が「値が q 以下の前の候補のうちの最小操作回数」です。