2020-03-29

Typical DP Contest H - ナップザック

問題概要

$N (\leq 100)$ 個の物があり，$i$ 番目の物の重さ，価値，色は $ w_i, v_i, c_i$ である。重さ $W$，かつ $C$ 色までナップザックに詰めることができるとき，ナップザックに詰められた物の価値の和の最大値を求めよ。

解法概要

解法の前に，私が陥った WA 解法 (ソースコード) について書いておきたい。

$\mathit{dp}_{i, j}$ を，$i$ 色使用済みで重さがの和が $j$ の場合の価値の和の最大値とする。あとは通常のナップザック問題と同じように $N$ 個の物を順番に見る。ただし，$\mathit{color}_{i, j}$ を$\mathit{dp}_{i, j}$ で使用済みの色の集合と考えて $\mathit{dp}_{i, j}$ と同時に更新していく。

この場合，次のようなケースで WA となってしまう。

6 つの物のうち 3 つめまで見た場合を考えてみよう。同じ「2 色使用済み，重さは 2」であれば，1 番目と 2 番目を入れる場合，2 番目と 3 番目を入れる場合，1 番目と 3 番目を入れる場合の 3 通りが考えられる。この WA 解法では色数と重さが同じであれば中身の色が何であるかを区別しない。そのため，全体を見たときに色 2 と色 3 を入れるのが最適 (価値の合計を 12 にすることができる) であることを判定できず，3 番目まで見た地点で価値が大きい色 1 と色 3 を入れる (価値の合計は 11 にしかならない) を入れてしまう。

ではどうすれば良いのかというと，すごくざっくりいうとある色 $c$ の全体に対する影響をまとめて計算して，色 $c$ の影響分を dp テーブルにまとめて足し合わせることができれば良い。

具体的な実現方法を述べる。$\mathit{dp}_{i, j}$ の定義は WA 解放と同じである。ただし，色ごとに，その地点での dp テーブルのコピー($dpk$ とする)を用意し，それを使って通常のナップザック問題のような状態遷移を行う。色ごとにまとめて $\mathit{dpk}$ を考えているので，色数は$\mathit{dp}_{i, j}$ から 1 だけ増える。そのため，ナップザック問題の要領で重さと価値の計算をしているときには色数 $i$ の遷移は考えなくてよい。こうしてできた $\mathit{dpk}$ は $\mathit{dp}$ が今見ている色 $k$ の影響を受けると仮定した場合の途中計算結果である。これを使って，すべての $i, j$ について $\mathit{dp}_{i, j}$ を $\mathit{dp}_{i, j}$ か $\mathit{dpk}_{i-1, j}$ のうち大きい方に更新する (色数 $i-1$ の状態に色 $k$ を追加したら色数は $i$ になるはず)。

ソースコード

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

using namespace std;

constexpr int NC = 50;

int main() {
    int N, W, C;
    cin >> N >> W >> C;
    int w, v, c;
    vector<Pii> items[NC+1];
    for(int k=0;k<N;++k) {
        cin >> w >> v >> c;
        items[c].emplace_back(w, v);
    }

    vector<vector<int>> dp(C+1, vector<int>(W+1, -1));
    dp[0][0] = 0;
    for(int ci=1;ci<=NC;++ci) {
        vector<vector<int>> dpk(dp);
        for(int k=items[ci].size()-1;k>=0;--k) {
            for(int i=C-1;i>=0;--i) {
                for(int j=W-items[ci][k].first;j>=0;--j) {
                    dpk[i][j+items[ci][k].first] = max(dpk[i][j+items[ci][k].first], dpk[i][j] + items[ci][k].second);
                }
            }
        }
        for(int i=0;i<C;++i) {
            for(int j=0;j<=W;++j) {
                dp[i+1][j] = max(dp[i+1][j], dpk[i][j]);
            }
        }
    }

    int ans = 0;
    for(int i=0;i<=C;++i) {
        for(int j=0;j<=W;++j) ans = max(ans, dp[i][j]);
    }

    cout << ans << endl;
}

所感

以前挫折した Typical DP Contest を埋めてみることにした。

2020-03-19

AtCoder Regular Contest 023 D - GCD区間

競技プログラミング (問題解説)

問題: D - GCD区間

公式解説: 解説スライド

問題概要

長さ $n (\leq 10^5)$ の数列 $a_1, a_2 \dots, a_N (1 \leq a_i \leq 10^9)$ がある。この数列に対して，次のクエリが $m (\leq 10^5)$ 回与えられる。それぞれのクエリの答えを出力せよ。

最大公約数が $x$ となる区間はいくつある？

解法概要

$a_l, a_{l+1} \dots, a_{r-1}, a_r$ の最大公約数を $\mathit{gcd}(l, r)$ と表す。

区間の数は全部で $n^2-1$ 個あるので，区間$[s, t]$ の $s$ と $t$ をすべて愚直に試していると当然間に合わない。

しかし，$t = T$ と $t$ を固定したとき，区間$[s, T](1 \leq s \leq T)$について，$\mathit{gcd}(s, T)$ の値としてありうるものは30個未満になる。何故ならば，$2^{30} \ge 10^9$ より数列の各要素が持つ素因数も30個未満であるため，要素同士の最大公約数の素因数も30個未満になるからである。$t = T$ で，$s$ を$T$ から $1$ へと減らしていくにつれて，その区間の最大公約数から素因数が徐々に削られていくイメージ。

したがって，$t$ の値ごとに，$\mathit{gcd}(s, t) (1 \leq s \leq t)$ の値の出現回数を map などに保持しながら数えればよい。実装の上では，$t = T$ のときに「$\mathit{gcd}(s, T-1) (1 \leq s \leq T-1)$ と $a_T$ から $\mathit{gcd}(s, T)$ を求めること」と「$\mathit{gcd}(T, T)$ の値 (必ず $a_T$を数えること」をしておけばよい。$\mathit{gcd}(s, T-1)$ が30種類未満なので，この前処理部分の時間計算量はループ分の $\mathcal{O}(n \log \max_i a_i)$ と map の値の参照分の $\mathcal{O}(\log \max_i a_i)$ で$\mathcal{O}(n (\log \max_i a_i)^2)$。

区間の終端のインデックスが $t$ でかつ最大公約数が $x$ の区間の数を $\mathit{cnt}_{t, x}$ とすると，クエリで答えるべきは $\sum_{t = 1}^n \mathit{cnt}_{t, x}$。クエリごとに毎回足し算をしていては間に合わないので，$x$ の値ごとに事前に足し合わせておく。

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

using ll = long long;

ll gcd(ll a, ll b) {
    if(b == 0) return a;
    return gcd(b, a%b);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(n);
    for(int i=0;i<n;++i) cin >> a[i];

    map<ll, ll> mp[n];
    mp[0][a[0]] = 1;
    for(int t=1;t<n;++t) {
        for(auto itr=mp[t-1].begin();itr!=mp[t-1].end();++itr) {
            mp[t][gcd(itr->first, a[t])] += itr->second;
        }
        ++mp[t][a[t]];
    }
    for(int t=0;t<n-1;++t) {
        for(auto itr=mp[t].begin();itr!=mp[t].end();++itr) {
            mp[n-1][itr->first] += itr->second;
        }
    }

    ll  x;
    for(int i=0;i<m;++i) {
        cin >> x;
        cout << mp[n-1][x] << endl;
    }
}

所感

gcd として取りうる値が少ないことを使った考察がなかなか身につかない。

2020-03-18

キーエンスプログラミングコンテスト 2020 D - Swap and Flip

競技プログラミング (問題解説)

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f

公式解説: 解説 pdf

問題概要

$N ( \leq 18)$ 枚のカードがあり，左から $i$ 枚目のカードは表に $A_i (\leq 100)$，裏に$B_i (\leq 100)$ が書いてある。次の操作のみを行い，カードが左から右に広義単調増加になるように並べることができるだろうか。できるならば最小の操作回数を答えよ。

整数 $i (\leq N-1)$ を1つ選び， $i$ 枚目のカードと $i+1$ 枚目のカードの位置を交換する。その後，その2枚のカードを裏返す。

解法概要

swap に加えて flip も行われるのでややこしいが，カードの裏表に関しては

最終的な場所の index と最初の index の差が偶数なら表
最終的な場所の index と最初の index の差が奇数なら裏

といえる (1つ動くたびに裏表が逆になるので)。

また，裏表については，1回の操作で

表になっている2枚のカードが裏になる
表と裏のカード1枚ずつがそれぞれ裏と表になる
裏になっている2枚のカードが表になる

しかないので，裏返されているカードは常に偶数枚になる。

仮に，最終的なカードの裏表がすべてのカードについて決まっているとする。上記の考察より，最終的な裏表と最初の index の偶奇から「最終的なカードの index の偶奇」がわかる。より具体的には，

最初の index は偶数，最終的に表になるカードは最終的な index も偶数
最初の index は偶数，最終的に裏になるカードは最終的な index は奇数
最初の index は奇数，最終的に表になるカードは最終的な index も奇数
最初の index は奇数，最終的に裏になるカードは最終的な index は偶数

となる。

最終的な index の偶奇ごとに (見えている値, 元々の index) を格納した vector を作ると，後はソートして交互に組み合わせれば操作後の数列ができる。操作後の数列を作っている最中に最終的な index が偶数 / 奇数になる数のいずれかが枯渇したら，その裏表の組み合わせでは広義単調増加列はできない。特に数が枯渇することもなく広義単調増加列を作れる場合は，できた数列の要素それぞれの元々の index を格納した新しい数列を作り，それに対して転倒数を求めれば操作回数が求まる。

今回は $N$ が18以下と小さいので，すべてのカードの裏表の組み合わせ $2^N$ 通りをすべて試すことができる。$2^N$ 通りすべてについて操作回数を計算し，最小の操作数を答えればよい。

時間計算量は $\mathcal{O}(2^N N \log (\max(N, A_\mathrm{max}, B_\mathrm{max})))$……なのかな？

ソースコード

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

using namespace std;

using Pii = pair<int, int>;

constexpr int INF = 1 << 30;

template<typename T>class BIT {
    public:
    int n;
    vector<T> bit;
    
    BIT(int n): n(n){
        bit.resize(n);
        fill(bit.begin(), bit.end(), (T)0);
    }

    void add(int idx, T x){
        for(int i=idx;i<=this->n;i+=i&-i) bit[i] += x;
    }

    //bit[1]からbit[end]までの和 (閉区間)
    T sum(int end){
        T ret = (T)0;
        for(int i=end;i>=1;i-=i&-i) ret += bit[i];
        return ret;
    }

    T count_swap(vector<int> &v){
        T ret = (T)0;
        int m = v.size();
        for(int i=1;i<=m;++i){
            add(v[i-1], 1);
            ret += i - sum(v[i-1]);
        }
        return ret;
    }
};


int main() {
    int n;
    cin >> n;
    vector<Pii> a(n);
    for(int i=0;i<n;++i) cin >> a[i].first;
    for(int i=0;i<n;++i) cin >> a[i].second;

    int ans = INF;
    for(unsigned int bi=0;bi<(1<<n);++bi) { // カードを裏返す/裏返さないの組み合わせ
        if(__builtin_popcount(bi) % 2) continue; // 裏返っているカードの数が奇数にはならない

        vector<Pii> v[2];   // v[0]: 偶数番目に配置されるべきカード, v[1]: 奇数番目に配置されるべきカード
        {
            vector<Pii> tmp_v(n);
            for(int i=0;i<n;++i) {
                if(bi & (1 << i)) {
                    v[1-i%2].emplace_back(a[i].second, i);
                } else {
                    v[i%2].emplace_back(a[i].first, i);
                }
            }
            sort(v[0].begin(), v[0].end());
            sort(v[1].begin(), v[1].end());
        }

        bool is_ok = true;
        int prev_v = -1;
        vector<int> u(n);
        for(int i=0;i<n;++i) {
            if(i/2 >= v[i%2].size() || prev_v > v[i%2][i/2].first) {
                is_ok = false;
                break;
            }
            prev_v = v[i%2][i/2].first;
            u[i] = v[i%2][i/2].second + 1;
        }
        if(!is_ok) continue;

        BIT<int> tree(100);
        ans = min(ans, tree.count_swap(u));
    }

    cout << ((ans == INF)?-1:ans) << endl;
}

所感

解説とは違う解法で解いたみたい。