hogecoder

tsutaj 競技プログラミングの記録

Codeforces Round #416 (Div. 2) C: Vladik and Memorable Trip

Codeforces 動的計画法

本番出てた回。ようやく復習できました。

問題概要

原文 → Problem - C - Codeforces

長さ N の数列があり、 i 番目の要素を a_{i} と書く。

次のルールに従って区間を選ぶ (複数でも良い、数列全体を被覆するような選び方でなくても良い) とき、選んだ区間の重みの合計を最大化せよ。

  • 区間内に登場する要素 val それぞれについて、 val と同じ値を持つ全ての要素が必ず同一の区間内に含まれていなければならない。
  • 区間の重みは、区間内に登場した数字の集合の XOR である (例えば、 \left[ 2, 5, 2, 3 \right] という区間であれば、区間の重みは 2 \oplus 5 \oplus 3 = 4 となる。)

解説

まず、各値について最左、及び最右のインデックスを覚えておき、これを l_{val}, r_{val} と表記することにします。

取りたい区間の左端 L を固定して、dp[i] = [0, i) の範囲での重み合計の最大値 なる DP を解くことを考えます。問題文の条件より、取りたい区間の中にある要素のうち、最左のインデックス l_{a_{cur}} が L より左であるものがあれば、その区間は invalid です。逆にそうでない場合、区間の右端 R を \max ( R, r_{a_{cur}} ) に伸ばす、すなわち今まで出てきた要素と同じ値をもつ全ての要素を同一の区間内に入れられるまで区間を伸ばしたあと、 DP 配列を更新します。

ソースコード

実装はとても楽です。大正義半開区間。

int N, a[5010];
int l[5010], r[5010], dp[5010];

signed main() {
    cin >> N;
    rep(i,0,5010) l[i] = INF, r[i] = -1;
    rep(i,0,N) {
        int p; cin >> p;
        a[i] = p;
        chmin(l[p], i);
        chmax(r[p], i+1);
    }

    rep(i,0,N) {
        chmax(dp[i+1], dp[i]);
        if(l[ a[i] ] == i) {
            int ub = r[ a[i] ], cur = i, val = 0;
            bool ng = false;
            while(cur < ub) {
                if(l[ a[cur] ] < i) ng = true;
                if(l[ a[cur] ] == cur) val ^= a[cur];
                chmax(ub, r[ a[cur++] ]);
            }
            if(!ng) dp[ub] = dp[i] + val;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

問題で要求されている条件のわりに実装が簡単で面白いですね。

AtCoder Beginner Contest 020 D: LCM Rush

AtCoder 数学

もう 7 月かあ・・・。

問題概要

\sum_{i=1}^{N} lcm(i, K) \mod 1,000,000,007 を求めよ。ただし lcm(a, b) は a と b の最小公倍数を指す。

制約: 1 \leq N, K \leq 10^{9}

解説

愚直にやるのは無理なので、数学をします。

まず、 lcm(a, b) = a \times b / gcd(a, b) なる関係があります。これを使って与式を変形すると

\sum_{i=1}^{n} i \times K/gcd(i, K) が求めたいものになります。

ここで、 gcd(i, K) の取りうる値の数は K の約数の数ぶんしかないことに注目します。この制約下では最大 1344 個であり、比較的少ないです。最大公約数の値が同じものについて、まとめて処理できると嬉しいよなあという気持ちになるため、 gcd の値ごとに分けて考えることにしましょう。

まずは、 gcd(i, K) = 1 を満たす i について、 lcm(i, K) の総和 S を考えてみましょう。これは、

S = \sum_{1 \leq i \leq N, gcd(i, K) = 1} lcm(i, K) = K \times \sum_{1 \leq i \leq N, gcd(i, K) = 1} i

となり、条件を満たす i の総和と K の積になります。

条件を満たす i の総和は包除原理によって求めることができます。 K の素因数を列挙し、素因数偶数個の積を約数にもつ数の総和は足し、素因数奇数個の積を約数に持つ数の総和は引き・・・という方針で求められます。(包除原理に関しては他サイトを参照してください)

次に、 gcd(i, K) = x を満たす i について、 lcm(i, K) の総和 T を考えてみましょう。これは変形すると先ほどの計算と同じ方針でできます。

gcd(i, K) = x は、 gcd(i/x, K/x) = 1 と同値です。よって、

T = \sum_{1 \leq i \leq N, gcd(i, K) = x} lcm(i, K) = K \times \sum_{1 \leq i' \leq \lfloor \frac{N}{x} \rfloor, gcd(i', \lfloor \frac{K}{x} \rfloor) = 1} i'

となります。

まとめると、

  1. K の約数 M それぞれに対して以下を行う
  2. 1 \leq i \leq \lfloor \frac{N}{M} \rfloor かつ gcd(i, \lfloor \frac{K}{M} \rfloor) = 1 を満たす i の総和を答えに足す
  3. 2 の操作は包除原理によって高速に処理できる

ということになります。

ソースコード

割と綺麗に書けて個人的には満足です。

int N, K;

// 約数の列挙
vector<int> divisor(int n) {
    vector<int> ret;
    for(int i=1; i*i<=n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(n / i != i) ret.push_back(n/i);
        }
    }
    return ret;
}

// 素因数の列挙
vector<int> pFactorization(int n) {
    vector<int> ret;
    for(int i=2; i*i<=n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            while(n % i == 0) n /= i;
        }
    }
    if(n != 1) ret.push_back(n);
    return ret;
}

// 1 <= i <= n, gcd(i, m) = 1 なるすべての i の和を求める
int solve(int n, int m) {
    vector<int> vp = pFactorization(m);
    int s = vp.size(), ans = 0;
    rep(bit,0,1<<s) {
        int num = 1;
        rep(i,0,s) if(bit >> i & 1) num *= vp[i];
        int a = (n / num) % MOD;
        int b = (a * (a+1) / 2) % MOD;
        int c = num % MOD;
        if(__builtin_popcount(bit) % 2) {
            int sub = (b * c) % MOD;
            ans = (ans - sub + MOD) % MOD;
        }
        else {
            (ans += b * c) %= MOD;
        }
    }
    return ans;
}

signed main() {
    cin >> N >> K;
    vector<int> div = divisor(K);
    int ans = 0;
    rep(i,0,div.size()) {
        (ans += solve(N/div[i], K/div[i]) * K) %= MOD;
    }
    cout << ans << endl;
    return 0;
}

解けるまでだいぶ時間かかったので、これは要復習かも。

Snackdown 2017 Pre-elimination A: Consecutive Snakes

CodeChef

これは良問だなあと思った。

問題概要

原文 → Contest Page | CodeChef

長さ L (1 \leq L \leq 10^{9}) の蛇が数直線上に N (1 \leq N \leq 10^{5}) 匹おり、 i 番目の蛇の左端の座標は S_{i} (1 \leq S_{i} \leq 10^{9}) である。つまり、 i 番目の蛇は区間 \left[ S_{i}, S_{i} + L \right] にいる。

いま、この蛇たちを以下の条件が成り立つように移動させたい。

  • N 匹の蛇すべてについて、区間 \left[ A, B \right] (1 \leq A, B \leq 10^{9}) の中にいる
  • 左から i 番目の蛇の右端と i+1 番目の蛇の左端は繋がっている。つまり 1 番目の蛇が区間 \left[ X, X + L \right] にいるとき、 2 番目の蛇は \left[ X + L, X + 2L \right] におり、 \dots 、 N 番目の蛇は \left[ X + (N-1)L, X + NL \right] にいる。

ある蛇が \left[ X_{1}, X_{1} + L \right] から \left[ X_{2}, X_{2} + L \right] に移動するとき、コストが | X_{1} - X_{2} | かかる。全体コストはこのコストを N 匹に対して計算した時の総和である。条件が成り立つように移動させた時の全体コストの最小値を出力せよ。

解説

まず、条件より以下のことがわかります。

  • 一番左にくる蛇の左端の座標を決定すると、全ての蛇の左端の座標が決まる
  • 移動前に左から i 番目にいた蛇は、移動後も左から i 番目にいたほうが良い

つまり、蛇を座標順にソートしておいて、一番左の蛇がどこにいるか決めてしまえば、コスト計算はできるということです。しかし、制約を見ると一番左の蛇の配置パターンは非常に多いことがわかるので、何か工夫が必要です。そこで、一旦定式化して考えましょう。

一番左の蛇の左端を x とします。すると、 i 番目の蛇の左端は x + i L と表せます (0-indexed)。移動前に左から i 番目にいた蛇の左端を S_{i} とすると、全体コストは以下のように書けます。

\begin{align} cost &=& \sum_{i=0}^{N-1} | S_{i} - (x + iL) | \\ &=& \sum_{i=0}^{N-1} | (S_{i} - iL) - x | \\ &=& \sum_{i=0}^{N-1} | T_{i} - x | \end{align}

S_{i} - iL は x の値の設定に関係なく決まるので、定数とみなして良いです。これを新たに T_{i} とします。

T_{i} をソートすると、 T_{0} \leq T_{1}\leq \dots \leq T_{N-1} のような形になります。さて、 T_{i} \leq x を満たす最大の i を j とすると、全体コストはこのように書けます。

cost = \sum_{i=0}^{j} (x - T_{i}) + \sum_{i=j+1}^{N-1} (T_{i} - x)

コスト関数は絶対値付きの一次関数を足しあわせた形になっているので凸関数です。よって、 x について二分探索して解くことができます。

計算量はソート O(N \log N)、二分探索パートでコスト計算時に upper_bound が必要なため O(\log N \log C) です (C = B - A)。

ソースコード

累積和を 0-indexed にすると配列外参照が起こるので、そこだけ 1-indexed で書いています。

int T, N, L, A, B;
int s[100010];
int t[100010], acc[100010];

int get(int l, int r) {
    l++; r++;
    return acc[r] - acc[l-1];
}

int calc(int x) {
    int idx = upper_bound(t, t+N, x) - t;
    int vl = idx * x - get(0, idx-1);
    int vr = get(idx, N-1) - (N-idx) * x;
    return vl + vr;
}

signed main() {
    scanf("%lld", &T);
    rep(cases, 0, T) {
        scanf("%lld%lld%lld%lld", &N, &L, &A, &B);
        rep(i,0,N) scanf("%lld", &s[i]);
        sort(s, s+N);

        // 累積和は 1-indexed
        rep(i,0,N) t[i] = s[i] - i * L;
        sort(t, t+N);
        rep(i,0,N) acc[i+1] = acc[i] + t[i];

        // A <= x <= B を満たす x で最小を求めよう
        int lb = A - 1, ub = B - N * L;
        while(ub - lb > 1) {
            int mid = (ub + lb) / 2;
            if(calc(mid) < calc(mid+1)) ub = mid;
            else lb = mid;
        }
        cout << calc(ub) << endl;
    }
    return 0;
}

二分探索に落とし込めた時はちょっと感動した。自力で解けてよかった。