JOI春合宿2020 ビルの飾り付け 4 解法

JOI春合宿2020 ビルの飾り付け 4
atcoder.jp
www.ioi-jp.org

問題

2つの数列 A, Bが与えられる。それぞれ長さは2N。
長さ2Nの文字列Sを S_i = 'A' or 'B' とする。
Sに対応して、長さ2Nの数列Cを、S_i = 'A' ならば C_i = A_i、S_i = 'B' ならば C_i = B_i とする。
次の条件をすべて満たすSが存在するならばSを出力せよ。

  • 'A'と'B'の出現回数はそれぞれN回
  • Cは広義単調増加、つまりC_i <= C_{i+1}

制約

1 <= N <= 500000

解法

S_i が'A'の場合は +1、'B'の場合は -1 として、Sの prefix の和の範囲、つまり最大値と最小値を求める。

  • low_a(i) := S_{0 ... i} の和の最小値：ただし C_{0 ... i} が広義単調増加で S_i = 'A' である
  • high_a(i) := S_{0 ... i} の和の最大値：ただし C_{0 ... i} が広義単調増加で S_i = 'A' である
  • low_b(i) := S_{0 ... i} の和の最小値：ただし C_{0 ... i} が広義単調増加で S_i = 'B' である
  • high_b(i) := S_{0 ... i} の和の最大値：ただし C_{0 ... i} が広義単調増加で S_i = 'B' である

この4つの数列は前から順番に計算することができる。条件を満たすことができない場合は low_x(i) = INF, high_x(i) = -INF とする。
'A'と'B'の出現回数は等しい必要があるので、Sの合計が0になるものが解となる。low_a(2N-1) <= 0 <= high_a(2N-1) ならば 末尾が'A'の解が存在する。low_b(2N-1) <= 0 <= high_b(2N-1) ならば、末尾が'B'の解が存在する。
それ以外ならば解は存在しない。

S_i が 'A' で S_{0 … i} の和が w の解が存在するならば、S_{0 … i-1} の和が w-1 の解が存在するはず。
S_i が 'B' で S_{0 … i} の和が w の解が存在するならば、S_{0 … i-1} の和が w+1 の解が存在するはず。

こうして、high, lowを利用して末尾から復元する。

コード

https://atcoder.jp/contests/joisc2020/submissions/15229449

const int MAXN = 1000011;
void update(pair<int, int> &dst, const pair<int, int> &src, int add) {
    amin(dst.first, src.first + add);
    amax(dst.second, src.second+ add);
}

int N;
int A[MAXN];
int B[MAXN];

const int INF = 1<<29;
pair<int, int> PA[MAXN], PB[MAXN];
char ans[MAXN];

void MAIN() {
    scanf("%d", &N);
    N += N;
    REP (i, N) scanf("%d", A+i);
    REP (i, N) scanf("%d", B+i);

    REP (i, N) PA[i] = PB[i] = make_pair(INF, -INF);
    PA[0] = make_pair(1, 1);
    PB[0] = make_pair(-1, -1);
    REP (i, N-1) {
	if (A[i] <= A[i+1]) update(PA[i+1], PA[i], 1);
	if (B[i] <= A[i+1]) update(PA[i+1], PB[i], 1);
	if (A[i] <= B[i+1]) update(PB[i+1], PA[i], -1);
	if (B[i] <= B[i+1]) update(PB[i+1], PB[i], -1);
    }

    int idx = N-1;
    char c = 0;
    if (PA[N-1].first <= 0 && 0 <= PA[N-1].second) c = 'A';
    else if (PB[N-1].first <= 0 && 0 <= PB[N-1].second) c = 'B';

    if (c) {
	int w = 0;
	while (1) {
	    ans[idx] = c;
	    if (idx == 0) break;
	    int val;
	    if (c == 'A') { w--; val = A[idx]; }
	    else { w++; val = B[idx]; }
	    idx--;
	    if (PA[idx].first <= w && w <= PA[idx].second && A[idx] <= val) c = 'A';
	    else c = 'B';
	}
	puts(ans);
    } else {
	puts("-1");
    }
}

終わりに

解説スライドが無かったので書いた。