NoiminのNoise

競技プログラミング (多め) とWeb (たまに) ,自然言語処理 (ブログではまだ)。

Educational Codeforces Round 65 (Rated for Div. 2) E. Range Deleting

問題: https://codeforces.com/contest/1167/problem/E

公式解説: https://codeforces.com/blog/entry/67017

問題概要

長さが {\displaystyle n (\leq 10^6) } の数列 {\displaystyle a = a_1, a_2, \dots a_n (1 \leq a_i \leq 10^6) } がある.このとき,

{\displaystyle f(l, r) = } {\displaystyle a } から {\displaystyle l \leq a_i \leq r } となるような {\displaystyle a_i } を全て取り除いたもの (ただし,{\displaystyle 1 \leq l,r \leq x } )

とする.

{\displaystyle f(l, r) } が非減少列となる {\displaystyle l,r } の選び方が何通りあるかを求めよ.

解法概要

まず初めに,{\displaystyle a } に 1 から{\displaystyle x } までの整数が全て含まれる場合を考える.

{\displaystyle a_i } の出現するインデックスの最小値と最大値をそれぞれ {\displaystyle \mathit{maxidx}(a_i) }{\displaystyle \mathit{minidx}(a_i) } とする.

f:id:noimin:20190518164442p:plain

{\displaystyle f(l, r) } が非減少列のとき,{\displaystyle f(l, r+1) }{\displaystyle f(l-1, r) } も非減少列である (非減少列から特定の数のみを取り除いても他の隣り合う要素の大小が逆転することはないため) .

このことを利用して, {\displaystyle l } を固定したときの {\displaystyle r } をいい感じに求めて,{\displaystyle l } を増やしながら {\displaystyle r } もそれに合わせて増やしていくことを考える. (いわゆる尺取り法)

{\displaystyle l } の値ごとに可能な {\displaystyle r } の選び方を答えに加算していきたいので,{\displaystyle r } は「{\displaystyle l } がその値のとき, {\displaystyle f(l, r) } が非減少列となる最小の数」とする.

{\displaystyle l = 1 } のとき, {\displaystyle f(1, x-1) } は絶対に非減少列になる (値が 1 種類しか含まれないため) .ただし今求めたい {\displaystyle r } は非減少列となる最小の数なので,r をできる限り小さくしたい.したがって,{\displaystyle \mathit{maxidx}(r) > \mathit{minidx}(r+1) } となるような (つまり,{\displaystyle r } を残してしまったら非減少にならなくなるような) r まで r を減らす.

{\displaystyle f(l, r) } が非減少列のとき,{\displaystyle f(l, r+1) } も非減少列なのだから,「{\displaystyle l } がその値のとき, {\displaystyle f(l, r) } が非減少列となる最小の数」としての {\displaystyle r } が求められたら,{\displaystyle l = 1 } である {\displaystyle l,r } の選び方は {\displaystyle x-r+1 } である.

{\displaystyle l = 2 } 以降では {\displaystyle l - 1 } に対応する {\displaystyle r } から始めて,{\displaystyle r } を適切に増やしていく必要がある.これは,1 から {\displaystyle l-1 } までの値と {\displaystyle r+1 } から {\displaystyle x } までの値で非減少列を作る必要がある.そのため,{\displaystyle \mathit{minidx}(r+1) }{\displaystyle \mathit{maxidx}(l-1) } を超えるまで (もしくは {\displaystyle r = x } まで) {\displaystyle r } を増やさなければならない.

{\displaystyle r } が求められたら,{\displaystyle l = 1 } のときと同様に {\displaystyle x-r+1 } を答えに加算する.

ただし,{\displaystyle l  } をこれ以上増やせない場合がある.上図でいう {\displaystyle l = 3 } のとき, 1 と 2 は 数列に残されるが,1 と 2を残している地点で非減少にはなり得ない.そのため,これ以上大きな {\displaystyle l  } を試す必要はない.

ここまで {\displaystyle a } に 1 から {\displaystyle x } までの整数が全て含まれる場合を考えた.実際のテストケースでは 1 から{\displaystyle x } までの整数が全て含まれるとは限らないので面倒くさくなる.例えば,上図の例でいう 4 が抜けた場合,

8 5
5 1 2 2 3 3 5 1

を考えてみよう.このとき,元の数列に 4 が含まれなくても {\displaystyle f(1, 4) } のような場合を考慮に入れて数え上げなければならないため注意が必要である.

このような「抜け」は,例えば {\displaystyle \mathit{maxidx}(a_i) }{\displaystyle \mathit{minidx}(a_i) } に -1 を入れて特別な場合として場合分けするなどで対処できる.

ソースコード

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    int n, x, a;
    scanf("%d%d", &n, &x);
    vector<int> min_idx(x+2, -1), max_idx(x+2, -1);
    for(int i=0;i<n;++i){
        scanf("%d", &a);
        if(min_idx[a] == -1) {
            min_idx[a] = i;
        }
        max_idx[a] = i;
    }

    vector<int> numbers;
    numbers.push_back(0);
    for(int i=1;i<=x;++i) {
        if(min_idx[i] != -1) numbers.push_back(i);
    }
    numbers.push_back(x+1);
    int nn = numbers.size();

    int l = 1, r = max(1, numbers[nn-3]), r_prev_i = nn-4, r_next_i = nn-2;
    while(r > l && (min_idx[numbers[r_next_i]] == -1 || max_idx[r] < min_idx[numbers[r_next_i]])) {
        --r;
        if(r == numbers[r_prev_i]) {
            --r_prev_i;
            --r_next_i;
        }
    }
    ll ans = ll(x-r+1);

    int l_prev_i = distance(numbers.begin(), lower_bound(numbers.begin(), numbers.end(), l+1)) - 1;
    while(++l <= x) {
        if(l >= r) r = l;
        if(l > numbers[l_prev_i+1]) ++l_prev_i;
        if(r == numbers[r_next_i]) ++r_next_i;

        while(r < numbers[nn-2] && max_idx[numbers[l_prev_i]] > min_idx[numbers[r_next_i]]) {
            ++r;
            if(r == numbers[r_next_i]) ++r_next_i;
        }

        ans += ll(x-r+1);
        if(min_idx[l] != -1 && max_idx[numbers[l_prev_i]] > min_idx[l]) break;
    }

    printf("%lld\n", ans);
    
}

所感

解法概要での扱いは小さめだけど,1 から x までの値に抜けがある場合の場合分け処理がなかなか書けなかった…….

Educational DP Contest W - Intervals

W - Intervals

問題概要

長さ {\displaystyle N (\leq 2 \times 10^5) } の '0' と '1' のみからなる文字列を考える.

{\displaystyle i (1 \leq i \leq M) } について,{\displaystyle l_i } 文字目から {\displaystyle r_i } 文字目までに '1' が ひとつでも含まれるならば,スコアに {\displaystyle a_i } を加算するとき,取りうるスコアの最大値を求めよ.

解法概要

{\displaystyle dp_{i} = } 最右の '1' が i 文字目である場合のスコアの最大値

という DP を考える (まず私の場合この発想がなかなか出てこなかったが,思い返してみれば一番端の状態を固定して DP を考える問題は時々見かける気がする).

すると,{\displaystyle dp_{i} } を考えるとき, 1文字目から (i-1) 文字目まではスコアが最大になるように決めて良いことになる (i 文字目は定義の通り固定で, (i+1) 文字目以降は同じく定義よりすべて '0') .最右の '1' が i 文字目である場合のスコアの最大値

という DP を考える (まず私の場合この発想がなかなか出てこなかったが,思い返してみれば一番端の状態を固定して DP を考える問題は時々見かける気がする).つまり,{\displaystyle j \lt i } という制約のもとで最大の {\displaystyle dp_{j} } に,i 文字目を '1' にしたときに加算されるスコアを足したものが {\displaystyle dp_{i} } の値となる.

なので,{\displaystyle dp_{i} } を考える番になったら,最初に {\displaystyle dp_{j} (1 \leq j \lt i) } の最大値を {\displaystyle dp_{i} } に入れておく.次に,区間の右端が i であるようなスコア加算クエリを適用していく. j 番目のクエリを適用するとき {\displaystyle dp_{l_j} } から {\displaystyle dp_{r_j} } までに {\displaystyle a_i } を加算すればよい.

最終的に,DP テーブル全体での最大値がこの問題の解となる.

なお,N の制約的に時間計算量が {\displaystyle O(N^2) } だと厳しそうなので,遅延評価セグメントツリーを使うことで {\displaystyle O(N\log N) } に抑える.遅延評価セグメントツリーを使うことで高速化ができる部分は上記の太字の部分である.

(以下画像 + 2 つの段落は自分がしそうになった勘違いについてメモっているだけなので読み飛ばしていただいて構いません)

f:id:noimin:20190507223618p:plain

例えば上図の状況では, {\displaystyle dp_{4} } を考えようとしている.{\displaystyle dp_{3} } 考えたところで,点線より上のクエリはすでに DP テーブルに適用されている.これまでの最大値は 4 なので, {\displaystyle dp_{4} = 4} としておく.次に,{\displaystyle dp_{5} } を考える前に右端のインデックスが 4 のクエリを適用しておく.

ひょっとしたら,「最終的な {\displaystyle dp_{4} } の値には点線より下のクエリも関係するのだから,点線より下のクエリも考慮すべきでは?」と私と同じことを思った人がいるかもしれない.{\displaystyle dp_{4} } に対応する 01 文字列は 4 文字目が '1',5 文字目以降が '0' と決まっているので,4文字目を区間に含むようなクエリはすべて適用しなければならないし,そうでないクエリは 1 つも適用してはならない.つまり {\displaystyle dp_{4} } の値を考えるにあたって,点線より下のクエリを適用するかしないかについては選択の余地がない.そのため,ここでは3文字目までを最適に決めるため {\displaystyle dp_{3} } までの最大値をとるだけにし,今後クエリを適用する際には問答無用で {\displaystyle dp_{l_j} } から {\displaystyle dp_{r_j} } までに {\displaystyle a_i } を加算していく.

ソースコード

#include <iostream>
#include <climits>
#include <vector>

using namespace std;

typedef long long ll;

const int MAX_N = 200000;

template<typename T> class LazyRMQ {
    public:
    int n;
    T inf = INT_MAX;
    vector<T> data, lazy;
    
    LazyRMQ(int m, T init_value=INT_MAX){
        // 2のべき乗にする
        n = 1;
        while(n < m) n <<= 1;
        data.assign(2*n-1, init_value);
        lazy.assign(2*n-1, 0);
        inf = init_value;
    }

    void eval(int k, int kl, int kr){
        if(data[k] == inf) data[k] = 0;
        if(lazy[k] == 0) return;
        data[k] += lazy[k];
        if(kr - kl > 1){
            lazy[2*k+1] += lazy[k];
            lazy[2*k+2] += lazy[k];
        }
        lazy[k] = 0;
    }

    // [s,t)
    void add(int s, int t, T x, int k, int kl, int kr){
        eval(k, kl, kr);
        if(kr <= s || t <= kl) return;
        if(s <= kl && kr <= t){
            lazy[k] += x;
            eval(k, kl, kr);
            return;
        }
        int kc = (kl+kr)/2;
        add(s, t, x, 2*k+1, kl, kc);
        add(s, t, x, 2*k+2, kc, kr);
        data[k] = max(data[2*k+1], data[2*k+2]);
    }

    void add(int s, int t, T x) {
        add(s, t, x, 0, 0, n);
    }

    // [s,t)
    T find(int s, int t, int k, int kl, int kr){
        eval(k, kl, kr);
        if(kr <= s || t <= kl) return inf;
        if(s <= kl && kr <= t) return data[k];
        int kc = (kl+kr)/2;
        T vl = find(s, t, 2*k+1, kl, kc);
        T vr = find(s, t, 2*k+2, kc, kr);
        return max(vl, vr);
    }

    T find(int s, int t) {
        return find(s, t, 0, 0, n);
    }
};

int main() {
    int n,m,l,r; ll a;
    cin >> n >> m;
    vector<pair<int, ll>> ranges[n+1];
    for(int i=0;i<m;++i) {
        cin >> l >> r >> a;
        ranges[r].emplace_back(l, a);
    }

    LazyRMQ<ll> tree(n+2, -(1<<30));
    for(int i=1;i<=n;++i) {
        ll opt = tree.find(0, i);
        tree.add(i, i+1, opt);
        for(pair<int, ll> p: ranges[i]) {
            tree.add(p.first, i+1, p.second);
        }
    }

    cout << tree.find(0, n+1) << endl;
}

所感

やっと Educational DP Contest 全完できた!

ただ,解法概要がまともな日本語になっている自信がない.

Google Code Jam 2019 Round 1B Draupnir

問題 / 公式解説: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122837

問題概要

(インタラクティブ問題)

"X-day ring" ( {\displaystyle 1 \leq X \leq 6 } ) というものがある.X-day ring は X 日ごとにもう 1 つの X-day ring を生成する.例えば 0 日目に 3-day ring が 1 つあったら,3 日目,6 日目の 3-day ring の数はそれぞれ 2 つ,4 つになる.

0日目に存在する 1-day ring, 2-day ring, ..., 6-day ring の数を {\displaystyle R_1, R_2, \dots, R_6 } (ただし {\displaystyle 1 \leq i \leq 6, 0 \leq R_i \leq 100 } )を求めよ.ただし,そのために以下の質問を W 回 (Visible では {\displaystyle W = 6}, Hidden では {\displaystyle W = 2}) まで行うことができる.

入力: D ( {\displaystyle 1 \leq D \leq 500 } )

出力: D 日目に存在する ring の数の総計を {\displaystyle 2^{63} } で割ったあまり

解法概要

Hidden の場合,{\displaystyle W = 2} なので1回の質問で 6 種類中 3 種類の ring の個数を特定することを考えてみる.

ring の増え方に着目すると,D 日目の i-day ring の個数は {\displaystyle R_i \times 2^\frac{D}{i} } の形で表すことができる.また,{\displaystyle R_i } の最大値は 10 進数で 100,つまり7bit の値 (1100100) であることから,{\displaystyle \frac{D}{i-1} - \frac{D}{i} \geq 7 } となるような D を入力すれば,返ってきた値の {\displaystyle \frac{D}{i} } bit 目から 7bit ぶんのみを取り出した値が {\displaystyle R_i } である.

63bit を超えた値は {\displaystyle 2^{63} } で割ったあまりには影響しないが {\displaystyle R_i } を特定する計算には使えなくなってしまうことと, {\displaystyle \frac{D}{i-1} - \frac{D}{i} \geq 7 } という条件に注意しながら,{\displaystyle 1 \leq i \leq 3 }{\displaystyle R_i } を特定するための質問(私のソースコードでは {\displaystyle D = 50 }) と {\displaystyle 4 \leq i \leq 6 }{\displaystyle R_i } を特定するための質問 (私のソースコードでは {\displaystyle D = 220 }) の {\displaystyle R_i } を特定するための質問を 1 回ずつすれば,2回の質問で全ての種類の ring の個数を特定することができる.

ただし {\displaystyle R_3 } を求める時だけ注意が必要である. {\displaystyle D = 50 } のとき,

{\displaystyle i = 1 } なら {\displaystyle \frac{D}{i} = 50 }

{\displaystyle i = 2 } なら {\displaystyle \frac{D}{i} = 25 }

{\displaystyle i = 3 } なら {\displaystyle \frac{D}{i} = 16 }

{\displaystyle i = 4 } なら {\displaystyle \frac{D}{i} = 12 }

{\displaystyle i = 5 } なら {\displaystyle \frac{D}{i} = 10 }

{\displaystyle i = 6 } なら {\displaystyle \frac{D}{i} = 8 }

となっている.つまり,ただ 7bit ぶんマスクするだけでは {\displaystyle R_3 } を求めることはできない.例えば 16bit 目には {\displaystyle i = 3, 4, 5 } のときの {\displaystyle R_i } の情報が混ざってしまっているためである.そのため,{\displaystyle R_3 } を求める際には,D日目の ring の個数もともとの値から{\displaystyle R_4 } のぶんと {\displaystyle R_5 } のぶんを引いておく必要がある.

ソースコード

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned long long ull;

const int Q1 = 220;
const int Q2 = 50;

int T, W;

void solve() {
    vector<ull> rings(6, 0);
    ull ret, mask = (1uLL << 7) - 1uLL;
    cout << Q1 << endl;
    cin >> ret;
    for(int i=3;i<6;++i) {
        rings[i] = (ret >> (Q1/(i+1))) & mask;
    }

    cout << Q2 << endl;
    cin >> ret;
    for(int i=0;i<2;++i) {
        rings[i] = (ret >> (Q2/(i+1))) & mask;
    }
    rings[2] = ((ret - (rings[3] << (Q2/4)) - (rings[4] << (Q2/5))) >> (Q2/3)) & mask;

    for(int i=0;i<5;++i) cout << rings[i] << " ";
    cout << rings[5] << endl;
    cin >> ret;
    if(ret == -1) exit(0);
}

int main() {
    cin >> T >> W;
    for(int t=0;t<T;++t) {
        solve();
    }
    
    return 0;
}

所感

{\displaystyle R_3 } 以外は比較的すぐわかったけど {\displaystyle R_3 } の求め方に気づくまでかなり時間を要してしまった.

Tenka1 Programmer Contest 2019 D - Three Colors

問題: D - Three Colors

公式解説: https://img.atcoder.jp/tenka1-2019/editorial.pdf

問題概要

N 個の整数 {\displaystyle a_1, a_2, \dots a_N } が与えられる.これらの整数を赤,緑,青で塗り分ける.

赤,緑,青で塗られた整数の和を R, G, B とするとき, 3辺の長さが R, G, B であるような正の面積の三角形が存在するような塗り分け方の数を 998244353 で割ったあまりを求めよ.

解法概要

{\displaystyle \sum_{i=1}^{N} a_i = S } とする.

正の面積の三角形が存在する条件は,{\displaystyle R+G > B }{\displaystyle G+B > R }{\displaystyle B+R > G } の全てが成り立つことである.すなわち,一番長い辺の長さが{\displaystyle \frac{S}{2} } 以上の場合,正の面積の三角形は存在しない.一番長い辺の長さが{\displaystyle \frac{S}{2} } 未満の場合には,正の面積の三角形が存在する (一番長い辺の長さが{\displaystyle \frac{S}{2} } 未満ということは他の辺の長さもそれ以下にしなければならず,いずれの辺の長さも 0 にはならないため) .

ここで {\displaystyle R \geq G, B } の場合だけを考えてみる.

{\displaystyle R \geq \frac{S}{2}} のとき (すなわち,正の面積の三角形が存在しないとき) {\displaystyle B,G \leq \frac{S}{2}} なので, {\displaystyle R \geq B,G } が必ず成り立っている.つまり,

{\displaystyle \mathit{dp}_{i, r} = a_i }まで見て, 赤に塗った棒の長さの合計が r の場合の塗り方の通り数

{\displaystyle \mathit{dp}_{i+1, r} = \mathit{dp}_{i+1, r}  + \mathit{dp}_{i,r} * 2 } (今見ている整数を青または緑に塗る場合に対応)

{\displaystyle \mathit{dp}_{i+1, r+a_i} = \mathit{dp}_{i+1, r+a_i}  + \mathit{dp}_{i,r}  } (今見ている整数を赤に塗る場合に対応)

というような DP をして最後に {\displaystyle \sum_{r=\frac{S}{2}}^{S} \mathit{dp}_{n,r} } を求めれば,R が最も長くかつ正の面積の三角形が存在しない塗り方の通り数が求められる.

あとは,緑が最も長い場合と青が最も長い場合が存在するので,解は全ての塗り分け方の通り数から {\displaystyle 3 \sum_{r=\frac{S}{2}}^{S} \mathit{dp}_{n,r} } を引いたもの……といきたいところであるが,ここは注意が必要.「赤が最も長い」「緑が最も長い」「青が最も長い」は排他的な条件ではなく,例えば,「赤が最も長い」かつ「緑が最も長い」というような状態が存在する.S が偶数のとき,単純に 3 倍してしまうと, {\displaystyle R = G = \frac{S}{2}, B = 0 } というような 2色だけで色分けを行なっていて,かつ和が等しいような場合を 2 回引いてしまうことになる.そのため, S が偶数の場合は 2 色に色分けをしてそれぞれの長さが {\displaystyle \frac{S}{2} } となるような塗り分け方の数を数えておかなければならない.これも,例えば赤と緑だけを使うと仮定すると

{\displaystyle \mathit{dp2}_{i, r} = a_i }まで見て, 赤に塗った棒の長さの合計が r の場合の塗り方の通り数

{\displaystyle \mathit{dp2}_{i+1, r} = \mathit{dp2}_{i+1, r}  + \mathit{dp2}_{i,r}} (今見ている整数を緑に塗る場合に対応)

{\displaystyle \mathit{dp2}_{i+1, r+a_i} = \mathit{dp2}_{i+1, r+a_i}  + \mathit{dp2}_{i,r}  } (今見ている整数を赤に塗る場合に対応)

という,先ほどと似た DP で求められる.

全ての塗り分け方は {\displaystyle 3^N } 通りなので,求めるべき解は

{\displaystyle 3^N - 3 \sum_{r=\frac{S}{2}}^{S} \mathit{dp}_{n,r} } (N が奇数のとき)

{\displaystyle 3^N - (3 \sum_{r=\frac{S}{2}}^{S} \mathit{dp}_{n,r} - 3\mathit{dp2}_{n, \frac{r}{2}} ) } (N が偶数のとき)

となる.

ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

typedef long long ll;

const ll MOD = 998244353;
const int N_MAX = 300;
const int A_MAX = 300;

vector<vector<ll>> dp(N_MAX+1, vector<ll>(N_MAX*A_MAX+1, 0)), dp2(N_MAX+1, vector<ll>(N_MAX*A_MAX+1, 0));

ll modpow(ll a, ll t) {
    ll ret = 1LL;
    while(t){
        if(t & 1LL){
            ret *= a;
            ret %= MOD;
        }
        a *= a;
        a %= MOD;
        t >>= 1;
    }
    return ret;
}

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i=0;i<n;++i){
        cin >> a[i];
    }
    ll s = accumulate(a.begin(), a.end(), 0LL);

    dp[0][0] = 1;
    dp2[0][0] = 1;
    for(int i=0;i<n;++i) {
        for(int r=0;r<=s;++r) {
            if(!dp[i][r]) continue;
            dp[i+1][r] += 2 * dp[i][r];
            dp[i+1][r] %= MOD;
            dp[i+1][r+a[i]] += dp[i][r];
            dp[i+1][r] %= MOD;
            dp2[i+1][r+a[i]] += dp2[i][r];
            dp2[i+1][r+a[i]] %= MOD;
            dp2[i+1][r] += dp2[i][r];
            dp2[i+1][r] %= MOD;
        }
    }

    ll ans = 0LL;
    for(int r=(s+1)/2;r<=s;++r) {
        ans += dp[n][r];
        ans %= MOD;
    }
    if(s % 2 == 0) ans += MOD - dp2[n][s/2];
    ans = (3 * ans) % MOD;
    ans = (modpow(3LL, n) + MOD - ans) % MOD;

    cout << ans << endl;
}

所感

余事象を数えるぞ! ってところまでしか本番は思いつかなかった.ずっと「赤に塗った整数の集合の大きさがわからないと……」とか寝ぼけたこと言ってましたね.

(2019/04/24 追記) 肝心の「求めるべき解は〜」が余事象の個数のままになっていたので直しました

AtCoder Grand Contest 008 D - K-th K

D - K-th K

問題概要

長さ {\displaystyle N (\leq 500) } の数列 {\displaystyle x} が与えられるとき,次の 2 つの条件を満たす数列 {\displaystyle a} が与えられるか判定し,与えられるならば 1 つ構成せよ.

  • {\displaystyle a} の長さは {\displaystyle N^2}であり,整数 {\displaystyle 1, 2, \dots, N}をちょうど {\displaystyle N} 個ずつ含む.
  • {\displaystyle 1 \leq i \leq N} について,{\displaystyle a} に含まれる整数 {\displaystyle i} のうち左から {\displaystyle i} 番目に位置するものは、{\displaystyle a} 全体では左から {\displaystyle x_i} 番目に位置する。

解法概要

以下,この例を使って解法を考える.また,いつもの 0-indexed ではなく 1-indexed で考える.

f:id:noimin:20190416134638p:plain

まずは Yes/No 判定.これは取りうる全てのインデックス {\displaystyle 1 \leq i \leq N} について,「あるインデックス i よりも絶対に前にないといけない要素数が,iを超えてしまう」または「あるインデックス i よりも絶対に後にないといけない要素数が N2-i+1 を超えてしまう」と No となる.そうでなければ,条件に当てはまるような数列 a が存在する.

a の構成の仕方は以下の 3 つに分けて考える.

  1. 整数 {\displaystyle i} のうち前から {\displaystyle i} 番目に位置するもの (入力の {\displaystyle x_i} .上の図で言うインデックス 3, 5, 8)
  2. 整数 {\displaystyle i} のうち前から {\displaystyle (i-1)} 番目以前に位置するもの (上の図で言うインデックス 1, 2, 4)
  3. 整数 {\displaystyle i} のうち前から {\displaystyle (i+1)} 番目以降に位置するもの (上の図で言うインデックス 6, 7, 9)

1 は入力から直接与えられるので,{\displaystyle x_i} の通りに配置すれば良い.

2 は,各{\displaystyle i} について,{\displaystyle x_i} より前に配置しなければならない.あらかじめ Yes/No 判定でそもそも条件に当てはまる数列 a が構成できない場合を弾いているとすると,数列 a を前から順番に見ていき,埋まっていないインデックスについて, {\displaystyle x_i} の小さい {\displaystyle i} から貪欲に埋めていけば良い.2 に当てはまる要素というのはインデックス {\displaystyle x_i} よりも前に消費していなければならないので, {\displaystyle x_i} が小さいものほど入れられる場所が少ないためである.上の図の場合,{\displaystyle i = 3} から順番に消費していくことになる.ただし 2 の段階で埋めるべきなのは各 {\displaystyle i} について {\displaystyle (i-1)} 個ぶんであることに気をつける.

3 は 2 とほぼ同じ.2 とは逆で {\displaystyle x_i} が大きいほど入れられる場所が少ないので, {\displaystyle x_i} の小さい {\displaystyle i} については早めに消費して損はない.3 で配置するべきは, 1 と 2 で配置されていない残りの各 {\displaystyle i} について {\displaystyle (i-1)} 個ぶんであることに気をつける.

ソースコード

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>

using namespace std;

typedef pair<int, int> Pii;

const int N_MAX = 500;

vector<Pii> v(N_MAX+1, Pii(0, 0));
 
bool check(int n) {
    // それぞれ [1, i], [i, n] に含まれるべきことが確定している要素の数
    vector<int> cnt_l(n*n+1, 0), cnt_r(n*n+2, 0);
    for(int i=1;i<=n;++i) {
        cnt_l[v[i].first] += i;
        cnt_r[v[i].first] += n-i+1;
    }
    for(int i=1;i<=n*n;++i) cnt_l[i] += cnt_l[i-1];
    for(int i=n*n;i>=1;--i) cnt_r[i] += cnt_r[i+1];

    for(int i=1;i<=n*n;++i) {
        if(i < cnt_l[i] || n*n-i+1 < cnt_r[i]) {
            return false;
        }
    }
    return true;
}

vector<int> construct(int n) {
    vector<int> ret(n*n+1, 0);
    sort(v.begin(), v.begin()+n+1);

    // x_i にしたがって数値を入れる
    for(int j=1;j<=n;++j) {
        int idx = v[j].first;
        int num = v[j].second;
        ret[idx] = num;
    }

    // x_i で指定されたインデックスより前の部分を埋める
    int j = 1;
    int num = v[j].second;
    int num_cnt = num - 1;
    for(int i=1;i<=n*n;++i) {
        if(ret[i]) continue;
        while(j < n && !num_cnt) {
            ++j;
            num = v[j].second;
            num_cnt = num - 1;
        }
        if(j == n && !num_cnt) break;
        ret[i] = num;
        --num_cnt;
    }
    
    // x_i で指定されたインデックスより後の部分を埋める
    j = 1;
    num = v[j].second;
    num_cnt = n - num;
    for(int i=1;i<=n*n;++i) {
        if(ret[i]) continue;
        while(j < n && !num_cnt) {
            ++j;
            num = v[j].second;
            num_cnt = n - num;
        }
        if(j == n && !num_cnt) break;
        ret[i] = num;
        --num_cnt;
    }

    return ret;
}

int main() {
    int n, x;
    cin >> n;
    for(int i=1;i<=n;++i){
        cin >> x;
        v[i] = {x, i};
    }

    if(check(n)) {
        cout << "Yes" << endl;
        vector<int> ans = construct(n);
        for(int i=1;i<=n*n;++i) {
            cout << ans[i] << " ";
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }

}

所感

バタフライシーカー にはまりすぎて競プロすら手につかなくなっていたところ,主人公と同じ名前の問題を見つけたので解きました.圭介くん大好きなので自力 AC できて嬉しいです.プレイ可能な年齢の方はぜひプレイしてみてください (ダイナミック布教)

競プロの実力は完全に鈍っているので天下一コンまでに少しでも取り戻さなければ.

Educational Codeforces Round 42 (Rated for Div. 2) E. Byteland, Berland and Disputed Cities

問題: https://codeforces.com/contest/962/problem/E

公式解説: https://codeforces.com/blog/entry/58869

問題概要

1次元の座標軸の上に n 個の街が並んでいる.街の座標は整数で,昇順に与えられる.街は 3 つの種類があり,それぞれ

  • Byteland の街 (B)
  • Berland の街 (R)
  • 紛争中の街 (P)

である.

これらの街をネットワークで結びたい.ただし,2 つの街を結ぶにはそれらの街の間の距離だけコストがかかる.以下の 2 つの条件を両方満たすように街を結ぶとき,最小コストを求めよ.

  • B の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.
  • R の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.

解法概要

まず,比較的簡単なのが P がない場合.ただ R の街たちと B の街たちを順番に繋げばOK.

以下,P がある場合を考える.毎度のごとく考察ノートの抜粋で恐縮だが, P を軸に以下の 2 パターンの結び方を考えてコストの小さい方を取れば良い.

f:id:noimin:20190404215322j:plain

type 1 は隣り合う P 同士を結んで,その間に入っている R と B も R 同士や B 同士で結ぶ結び方である.ただし, R と B それぞれについて最も間が空いているところだけは結ばないことで,コストを最小に抑える.

type 2 は P 同士を直接は結ばず, R を通るルートと B を通るルートの 2 つを作る結び方である.ただしこの結び方は P 同士の間に R と B の両方がある場合しかできない.片方しかない場合にこの結び方をやろうとすると,与えられた 2 つの条件のうち片方しか満たせなくなってしまう.

また,両端の P よりも端に出てくる B と R を考慮するのを忘れないように注意する.

ちなみに私が引っかかった点の 1 つに,「R か B のどちらかがあり,もう片方がない場合」に満たすべき条件が挙げられる.例えば, R と P だけがあり, Bがない場合に満たすべき条件は

  • R の街と P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.
  • P の街の集合について,集合内の街だけを辿って任意の街から任意の街に行ける.

の 2 つである.

B がない場合について,ずっと 2 番目の条件を考慮しないまま考察を進めていた.

ソースコード

#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>

#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

const int MAX_N = 200000;
const ll INF = (1LL << 60);

int main() {
    int n;
    cin >> n;

    vector<Pll> cities;
    ll x, y;
    char c;
    bool exists_P = false;
    for(int i=0;i<n;++i) {
        cin >> x >> c;
        y = (c == 'R')?2:((c == 'B')?1:0);
        if(y == 0) exists_P = true;
        cities.emplace_back(x, y);
    }

    ll ans = 0LL;

    // P がないので R 同士 B 同士を繋ぐ
    if(!exists_P) {
        ll prev[3] = {-1, -1, -1};
        for(int i=0;i<n;++i) {
            if(prev[cities[i].second] != -1) {
                ans += cities[i].first - cities[prev[cities[i].second]].first;
            }
            prev[cities[i].second] = i;
        }
        cout << ans << endl;
        return 0;
    }

    // Pがある
    vector<Pll> prev(3, {-1, -1});
    ll max_gap[3] = {0, 0, 0};
    for(int i=0;i<n;++i) {
        // 見ている街が P のときだけ答えを増やすようにしたら見通しが良くなった気がする
        if(cities[i].second == 0) {
            if(prev[0].first == -1) {
                for(int j=1;j<=2;++j) {
                    if(prev[j].first != -1) ans += cities[i].first - cities[prev[j].first].first;
                }
            } else {
                // 繋ぎ方パターン 1 (P同士を繋ぐ)
                ll tmp1 = cities[i].first - cities[prev[0].first].first;
                for(int j=1;j<=2;++j) {
                    if(prev[1].first != -1) {
                        max_gap[1] = max(max_gap[1], cities[i].first - cities[prev[1].second].first);
                        tmp1 += cities[i].first - cities[prev[0].first].first - max_gap[1];
                    }
                }
                // 繋ぎ方パターン 2 (P同士を繋がない)
                // この繋ぎ方は P と P の間に R と B の両方がないとやっちゃダメ
                ll tmp2 = INF;
                if(prev[1].first != -1 && prev[2].first != -1) {
                    tmp2 = 2 * (cities[i].first - cities[prev[0].first].first);
                }
                // 小さい方を採用
                ans += min(tmp1, tmp2);
            }
            for(int j=0;j<=2;++j) {
                prev[j] = {-1, -1};
                max_gap[j] = 0;
            }
            prev[0].first = i;
        } else {
            if(max(prev[0].first, prev[cities[i].second].second) != -1) {
                max_gap[cities[i].second] = max(
                    max_gap[cities[i].second], 
                    cities[i].first - cities[max(prev[0].first, prev[cities[i].second].second)].first
                );
            }
            if(prev[cities[i].second].first == -1) prev[cities[i].second].first = i;
            prev[cities[i].second].second = i;
        }
    }
    for(int j=1;j<=2;++j) {
        if(prev[0].first < prev[j].first) ans += cities[prev[j].second].first - cities[prev[0].first].first;
    }

    cout << ans << endl;
}

所感

WA と RE を計 23 回出しながら頑張りました.

Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 2) D. Destruction of a Tree

問題: https://codeforces.com/contest/964/problem/D

公式解説: https://codeforces.com/blog/entry/58991

問題概要

n ノードの木が与えられる.木の中で,次数が偶数の頂点を destroy できる.頂点を destroy すると,その頂点につながっている辺は全て消える.全ての頂点を destroy することは可能か答えよ.もし可能なら,頂点を destroy する順番を答えよ.

解法概要

WA を自力で解決できず解説をチラ見.

nの偶奇だけで YES/NO が決まってしまうらしい. destroy できるのは次数が偶数の頂点だけなので,1 頂点を destroy することで減る辺も偶数本である.そのため,辺が奇数本だと全部の辺を消し切ることができない.偶数本だとできる.木の辺が奇数本あるということは木の頂点が偶数個あるということだから,n が奇数ならば YES,偶数ならば NO である.

ここで,destroy の順番くらいは自分で考えるぞと意気込むもこちらも結局は公式解説とkmjpさんのブログでの解説 に頼ることに.

結局各頂点において

  1. . SubTree内の頂点数が偶数個の子頂点を探索する
  2. . 見ている頂点を消す
  3. . SubTree内の頂点数が奇数個の子頂点を探索する

の順を取ればよい。

(出典: Codeforces #475 B. Destruction of a Tree - kmjp's blog)

とのこと.

なるほど.これを自分の中で消化してみる.

部分木 の頂点数が偶数の子ノードは 今見ているノード v を消さなくても消せる.頂点数が偶数の部分木は辺の数が奇数で,そのsubtree の頂点から v に生えている辺を入れると辺の数が偶数になるため.

v を根とする 部分木を考えたときに,頂点数が偶数個の部分木の根となっている子ノードとその子孫を全部消したとき,残る頂点の数は奇数となる (全体の頂点数は奇数であるため) .そのため, v に「頂点数が奇数個の部分木」が偶数個ぶら下がっている状態になる.つまり v は次数が偶数となっており,destroy 可能である. v を消去すると次数が奇数だった子ノードたちの次数が偶数となり, destroy できるようになる.

このようにすると,全てのノードを destroy できる.ノード数が奇数ならば全てのノードが destroy できることから,ノード数が奇数 / 偶数の部分木の destroy 方法を再帰的に考えられるか がミソっぽい.

ソースコード

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 200000;

vector<int> graph[MAX_N];
vector<int> node_num(MAX_N, 0);
int n;

void destroy(int i) {
    cout << i+1 << endl;
}

int count_dfs(int node, int par) {
    node_num[node] = 1;
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        node_num[node] += count_dfs(nxt, node);
    }
    return node_num[node];
}

void destroy_dfs(int node, int par) {
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        if(node_num[nxt] % 2 == 0) destroy_dfs(nxt, node);
    }
    destroy(node);
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        if(node_num[nxt] % 2 == 1) destroy_dfs(nxt, node);
    }
}

int main() {
    cin >> n;
    int x;
    for(int i=0;i<n;++i) {
        cin >> x;
        if(x) {
            --x;
            graph[x].push_back(i);
            graph[i].push_back(x);
        }
    }

    if(n % 2 == 0) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    
    count_dfs(0, -1);
    destroy_dfs(0, -1);
}

所感

今回の記事,ほぼ "解説" をしていないな