読者です 読者をやめる 読者になる 読者になる

AOJ 0613 Treasures

問題概要

N 個の財宝が与えられ,それぞれ市場価値 w(i)と貴重度 v(i) が決まっている.
この財宝をAとBで分け合う.どちらも獲得しない財宝があってもよい.
分け合った後のAとBの財宝の市場価値の総和をそれぞれ Wa, Wb とする.
また,分け合った後のAとBの財宝の貴重度の総和を Va, Vb とする.
(Wa - Wb の絶対値) <= D を満たすようにしたとき,Vb - Va を最大化せよ.

・制約
1 <= N <= 30
1 <= w(i), v(i) <= 10^15

解法

w と v がでかいので半分全列挙.各要素は pair であり,first には Wa - Wb, second には Vb - Va を保存しておく.

TLE解(?)

半分前列挙した後,片方の集合をソートしておく.この集合を S1 とする.
その集合の各要素の貴重度 V(= p1.second) を,ソートされているこの順番にセグツリに代入しておく.
セグツリでは,各区間の最大値を管理するようにする.

もう片方の集合 S2 の各要素 p2 に対し,-D <= p1.first + p2.first <= D を満たすような集合 S1 の区間は二分探索により求まる.
この区間における S1 の V の最大値は,セグツリにクエリを投げれば分かる.

これを 集合 S2 の各要素にたいして行い,最大値を求める.
計算量は O(3^(N/2) log3^(N/2)) = O(N3^N).

なんだけど,かなりギリギリで,実際8秒制限に対して9秒とかかかってしまう.
定数倍早くしたら通ると思うけど,そんな気力はなかった.ちーん.

間に合う解法

TLE 解では S1 しかソートしてないけど,S2 もソートしておくと良い性質が得られる.

S2 のある要素について調べ終わり,次の要素について調べるときを考える.
すると,S1 のなかの条件を満たす区間は,右にずれる以外ありえないことが(少し考えれば)わかる.
なので,しゃくとり法(スライド最小値?)の要領でやれば良い.

オーダーは変わらないけど,遅いのはソート部分だけなので,セグツリ使うよりは遥かに速い.

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using P = pair<ll, ll>;

constexpr ll INF = 1e18;

void dfs(int i, int const last, vector<P>& res, vector<P> const& input, ll diff, ll val) {
    if(i == last) {
        res.emplace_back(diff, val);
        return;
    }
    dfs(i+1, last, res, input, diff-input[i].first, val-input[i].second);
    dfs(i+1, last, res, input, diff, val);
    dfs(i+1, last, res, input, diff+input[i].first, val+input[i].second);
}

int main() {
    int N;
    ll D;
    cin >> N >> D;

    vector<P> input(N);
    for(int i=0; i<N; ++i) {
        cin >> input[i].first >> input[i].second;
    }

    int N1 = N/2;
    vector<P> v1, v2;
    v1.reserve((int)pow(3, N1));
    v2.reserve((int)pow(3, N-N1));
    dfs(0, N1, v1, input, 0, 0);
    dfs(N1, N, v2, input, 0, 0);
    sort(v1.rbegin(), v1.rend());
    sort(v2.begin(), v2.end());

    ll ans = -INF;
    int t = 0;
    deque<P> deq;
    for(int i=0; i<v1.size(); ++i) {
        while(t < v2.size() && v2[t].first + v1[i].first <= D) {
            while(!deq.empty() && deq.back().second <= v2[t].second) {
                deq.pop_back();
            }
            deq.push_back(v2[t]);
            ++t;
        }
        while(!deq.empty() && deq.front().first + v1[i].first < -D) {
            deq.pop_front();
        }
        if(!deq.empty()) {
            ans = max(ans, v1[i].second + deq.front().second);
        }
    }
    cout << ans << endl;
}

AOJ 0145 Cards

問題概要

n 個のカードの山がある.カードには数字がかかれている.
それぞれの山の一番上と下のカードの数字は a(i) と b(i) である.
2つの山を重ねる操作を繰り返して,一つの山にすることを考える.
2つの山を重ねる時,それらの山の一番上と下にある4つのカードの数字を全てかけ合わせた値だけコストがかかる.
また,重ねる場合は,必ず左の山を上に,右の山を下にする.
この時,1つの山にするために必要なコストを最小化せよ.

制約

1 <= n <= 100
1 <= a(i), b(i) <= 200

解法

dp[i][j] := i 番目の山から j 番目の山までを1つの山にするために必要な最小のコスト
とする動的計画法で解ける.
ただし,dp[i][i] = 0 である.
dp[i][j] を求めるとき,i <= k < j なる各 k について考える.
すると,dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + a(i) * b(k) * a(k+1) * b(j)) という式が成り立つ.
(なぜなら,左の山は必ず上に重ねるから.)
これを i, j の幅を少しずつ増やしていけば,dp[0][n-1] が求める答えとなる.
計算量は O(n^3).

ソースコード

#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
 
constexpr ll INF = 1e18;
 
int main() {
    int n;
    cin >> n;
    vector<vector<ll>> dp(n, vector<ll>(n, INF));
    vector<ll> a(n), b(n);
    for(int i=0; i<n; ++i) {
        cin >> a[i] >> b[i];
    }
    for(int i=0; i<n; ++i) {
        dp[i][i] = 0;
    }
    for(int w=1; w<n; ++w) {
        for(int i=0; i+w<n; ++i) {
            for(int j=i; j<i+w; ++j) {
                dp[i][i+w] = min(dp[i][i+w], dp[i][j] + dp[j+1][i+w] + a[i]*b[j]*a[j+1]*b[i+w]);
            }
        }
    }
    cout << dp[0][n-1] << endl;
}

AOJ 0098 Maximum Sum Sequence II

問題概要

n次正方行列(a_ij)が与えられる.(a_ij) の部分行列の要素の和の最大値を求めよ.

・制約
1 <= n <= 100

解法

まず,要素の横方向について累積和を取る.
その後,横方向のある区間[i, j]を固定して考えてみる.この区間の各行の和はsum[k][j] - sum[k][i] である.
S[k] := sum[k][j] - sum[k][i] とおく.
すると,この区間の幅を考えたときの最大値は,S[k] の連続する部分列の和の最大値を求める問題に帰着できる.
これは動的計画法でとけるので,最終的な計算量は O(N^3)である.

ソースコード

#include <iostream>
#include <vector>
using namespace std;
 
using ll = long long;
 
int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            cin >> a[i][j];
        }
    }
    vector<vector<int>> sum(n, vector<int>(n+1));
    for(int i=0; i<n; ++i) {
        for(int j=0; j<n; ++j) {
            sum[i][j+1] += sum[i][j] + a[i][j];
        }
    }
    int res = -1e9;
    for(int i=0; i<=n; ++i) {
        for(int j=i+1; j<=n; ++j) {
            int t = 0;
            for(int k=0; k<n; ++k) {
                if(t < 0) {
                    t = sum[k][j] - sum[k][i];
                } else {
                    t += sum[k][j] - sum[k][i];
                }
                res = max(res, t);
            }
        }
    }
    cout << res << endl;
}

TopCoder SRM 711 Div2 Hard TreeMovingDiv2

問題概要

与えられた引数にしたがって, 頂点数が n の m 個の木を構築します.
それぞれの木を T(i) とします.
各 i = 0, 1, ..., m-1 について,辺 e(i) ∈ T(i) を一つ選びます.
e(i) を T(i) から取り除き,T(i+1) に加えます.T(m-1) のものは T(0) に加えます.
この操作を行った後,すべての T(i) がまだ木であるような操作の仕方は何通りありますか.
1e9+7 で割った余りを求めなさい.

・ 制約
2 <= n <= 50
2 <= m <= 50

解法

m, n の制約が緩いので,愚直な DP で通ります.
dp[i][j][k] := i 番目の木から j 番目の辺を選び,かつ 0 番目の木からは k 番目の辺を選んでいた場合の数
とします.
あとは,T(i) に対して,T(i-1) の j 番目の辺を選んだときに,T(i) で k 番目の木を選んだ場合,T(i) が木になっているかを Union-find 木で確認します.
木になっていれば,各 l に対して dp[i][k][l] += dp[i-1][j][l] とすればよいです.

最後に,0 番目の木に戻ってきたときは処理が特別になります.
dp[0][i][i] を一旦 0 に戻します.
同じように j, k を選んだ時に,木になっていれば,今度は各 l に対してではなく,k のみ dp[i][k][k] += dp[i-1][j][k]; とします.
こうしないと,最初に k 番目の辺を選んでいたのに,違う辺を選んでいた場合の数が含まれてしまうためです.

あとは,dp[0][i][i] の総和を取れば,答えになります.

計算量は O(mn^3 * (union-findの分)) です.

ソースコード

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

//
// union_find の実装は本質でないので省略
//

using ll = long long;

using edge = pair<int, int>;

constexpr ll mod = 1e9+7;

class TreeMovingDiv2 {
public:
    int count(int n, vector<int> roots, vector<int> a, vector<int> b, vector<int> c) {
        const int m = roots.size();
        vector<vector<edge>> es(m, vector<edge>(n-1));
        for(int i=0; i<m; ++i) {
            vector<int> x(n-1);
            x[0] = c[i];
            for(int k=1; k<n-1; ++k) {
                x[k] = ((ll)a[i] * x[k-1] + b[i]) % mod;
            }
            for(int j=0; j<n-1; ++j) {
                es[i][j].first = ((ll)roots[i] + j + 1) % n;
                es[i][j].second = ((ll)roots[i] + (x[j] % (j+1))) % n;
            }
        }
        vector<vector<vector<ll>>> dp(m+1, vector<vector<ll>>(n-1, vector<ll>(n-1)));
        for(int i=0; i<n-1; ++i) {
            dp[0][i][i] = 1;
        }
        for(int i=0; i<m; ++i) {
            int next = (i + 1) % m;
            if(next == 0) {
                for(int j=0; j<n-1; ++j) {
                    dp[0][j][j] = 0;
                }
            }
            for(int j=0; j<n-1; ++j) {
                int prev_v = es[i][j].first, prev_u = es[i][j].second;
                for(int k=0; k<n-1; ++k) {
                    union_find uf(n);
                    uf.unite(prev_v, prev_u);
                    for(int l=0; l<n-1; ++l) {
                        if(k == l) {
                            continue;
                        }
                        uf.unite(es[next][l].first, es[next][l].second);
                    }
                    if(uf.size(prev_v) == n) {
                        if(next == 0) {
                            (dp[next][k][k] += dp[i][j][k]) %= mod;
                        } else {
                            for(int l=0; l<n-1; ++l) {
                                (dp[next][k][l] += dp[i][j][l]) %= mod;
                            }
                        }
                    }
                }
            }
        }
        ll res = 0;
        for(int i=0; i<n-1; ++i) {
            (res += dp[0][i][i]) %= mod;
        }
        return res;
    }
};

感想

本番で通せそうで時間が足りなかった問題.全完したかった.

しかしこれ,入力に悪意があって,木の構築段階で int だとオーバーフローするような入力があるくせに,関数定義は vector(int) を強制されてます.嫌がらせかな???

Div 1 の 1 <= n <= 300 だと O(n^3) ってことなんだろうけど,方法が全然わからない.

TopCoder SRM 709 Div2 Med Permatchd2

問題概要

「グラフが "pretty" である」を,「グラフに含まれる任意の連結成分 S に対して,|E(S)| が偶数である」と定義する.
ここで,単純グラフが1つ与えられる.このグラフを "pretty" なものにするためには,辺を最小で何本追加すればよいか求めよ.
どのようにしても "pretty" にできない場合は,-1 とせよ.

・制約
1 <= |V(G)| <= 50
G は単純グラフである.

解法

まず,各連結成分に対して,頂点数と辺数を求めておく.これはDFSで十分.
偶数のものはそのままでよいので,奇数のものについて考える.
まず,|E(S)| が奇数となる連結成分 S の中に,辺を追加できるならそれが最適であることは明らかである.
よって,それが可能であるなら前もって追加して,偶数の連結成分にしておく.以下はそれを前提とする.
S の中に辺を追加できないのは,S が完全グラフである場合である.
残った奇数の連結成分(すべて完全グラフ)は,それらを環状に結べば全体として偶数にできる.
1つしか残らなかった場合は,偶数の連結成分と一本の辺を追加して結べば良い.
1つしか残らず,かつ偶数の連結成分が0個だった場合は,どうやっても無理なので -1 を返す.

ソースコード

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Permatchd2 {
public:
    int fix(vector<string> graph) {
        vector<bool> used(graph.size());
        vector<pair<int, int>> v;
        for(int i=0; i<graph.size(); ++i) {
            if(!used[i]) {
                int v_cnt = 0, e_cnt = 0;
                dfs(graph, i, v_cnt, e_cnt, used);
                e_cnt /= 2;
                v.push_back(make_pair(v_cnt, e_cnt));
            }
        }
        int res = 0;
        int odd_num = 0;
        for(int i=0; i<v.size(); ++i) {
            int v_cnt = v[i].first, e_cnt = v[i].second;
            if(v_cnt*(v_cnt-1)/2 != e_cnt && e_cnt % 2 == 1) {
                res++;
                v[i].second += 1;
            }
            odd_num += v[i].second % 2 == 1;
        }
        if(odd_num == 1) {
            res = -1;
        } else {
            res += odd_num;
        }
        return res;
    }
    void dfs(vector<string> const& g, int v, int& v_cnt, int& e_cnt, vector<bool>& used) {
        used[v] = true;
        v_cnt += 1;
        e_cnt += count(g[v].begin(), g[v].end(), 'Y');
        for(int i=0; i<g[v].size(); ++i) {
            if(used[i]) {
                continue;
            }
            if(g[v][i] == 'Y') {
                dfs(g, i, v_cnt, e_cnt, used);
            }
        }
    }
};

Codeforces Round #406 (div.2) C

問題概要

円上に n 個のマスがある.それぞれ 0 から n-1 まで番号が振られている.
0 番目はブラックホールである.
また,どこかのマスに一匹のモンスターがいる.
これらを使って2人でゲームをする.2人はそれぞれ集合S1, S2を持っていて,要素はいくつかの自然数である.
順番に,自分の集合の中から好きな数字をえらんで,モンスターを今いる位置から時計回りに選んだ数字分移動させる.この時,ちょうどブラックホールにモンスターを移動させたほうが勝ちである.
モンスターの初期位置が 1, 2, …, n-1 番目のマスだった場合,2人のプレイヤーが最善を尽くした時に先手(プレイヤーは二人いるので2通り)は「勝ち」「ループ」「負け」のいずれになるかをすべて答えよ.

・制約
2 <= n <= 7000
1 <= |Si| <= n-1, for i = 1, 2

解法

典型DP.ゲームなので,最終状態からさかのぼっていくというのが定石.
手番とモンスターの位置で,2*n の状態が存在する.
dp[i][j] := 先手が i 人目で,モンスターの初期位置が j マス目だったときの先手の結果 とする.
dp[1][0] = dp[0][0] = (負け) としておく.
(手番, モンスター位置) = (0, 0) と (1, 0) を根とするDFSをやる.(BFSでも良い.そっちのほうが多かったように思う.)
今見ている状態が負けであれば,一つ前の状態(手番が入れ替わる)は勝ちと決まる.

どのように遷移しても相手が勝ってしまう(すべての次の状態が勝ち)ならば,今の状態を負けとする.
なので,今見ている状態が勝ちであれば,一つ前の状態の勝ちうる遷移の数を一つ減らす.遷移の方法は,自分の持っている自然数の集合のサイズ分あるが,これが0になってしまった場合は,先ほど述べた自分の負けの状態である.

DFSで次に探索しようとしている状態が勝ちとも負けとも今の段階で決められない場合は,そこで探索を保留する.

最終的に,勝ちとも負けとも決まらなかった状態は,ループの状態である.(勝てないのは明らかなので,負けるよりも無限ループさせるほうが最善手となる.)

計算量は O(n^2).

ソースコード

#include <iostream>
#include <vector>
using namespace std;

constexpr int INF = 1e9;

int n;

// -1: current turn lose, 1: win, 0: visited(and not determined)
void dfs(int turn, int p, vector<vector<int>>& dp, vector<vector<int>>& cnt, vector<vector<int>> const& s) {
    if(dp[turn][p] == INF) {
        dp[turn][p] = 0;
    }
    for(auto x : s[turn^1]) {
        int np = (p - x + n) % n;
        if(dp[turn^1][np] != INF) {
            continue;
        }
        if(dp[turn][p] == -1) {
            dp[turn^1][np] = 1;
        } else if(--cnt[turn^1][np] == 0) {
            dp[turn^1][np] = -1;
        } else {
            continue;
        }
        dfs(turn^1, np, dp, cnt, s);
    }
}

int main() {
    cin >> n;
    vector<vector<int>> s(2);
    for(int i=0; i<2; ++i) {
        int k;
        cin >> k;
        s[i].resize(k);
        for(int j=0; j<k; ++j) {
            cin >> s[i][j];
        }
    }
    vector<vector<int>> dp(2, vector<int>(n, INF));
    vector<vector<int>> cnt(2, vector<int>(n));
    for(int i=0; i<2; ++i) {
        for(int j=0; j<n; ++j) {
            cnt[i][j] = s[i].size();
        }
    }
    dp[0][0] = dp[1][0] = -1;
    dfs(0, 0, dp, cnt, s);
    dfs(1, 0, dp, cnt, s);
    for(int i=0; i<2; ++i) {
        for(int j=1; j<n; ++j) {
            int r = dp[i][j];
            if(r == -1) {
                cout << "Lose";
            } else if(r == 1) {
                cout << "Win";
            } else {
                cout << "Loop";
            }
            cout << " \n"[j == n-1] << flush;
        }
    }
}

感想

最初,根を適当に選んで DFS していたせいで,ループをうまく扱えなくて困っていた.
こういうコードなんだけども,(DFS 部のみ抜粋)

int dfs(int p, vector<vector<int>>& dp, vector<vector<int>> const& s, int turn) {
    int& r = dp[turn][p];
    if(r != INF) {
        return r;
    }
    if(p == 0) {
        return r = -1;
    }
    r = 0;
    int t = 2;
    for(int i=0; i<s[turn].size(); ++i) {
        t = min(t, dfs((p+s[turn][i])%n, dp, s, (turn+1)%2));
    }
    return r = -t;
}

これだと以下の図のようなケース(不必要な辺は省いています)で死にます.
f:id:Suikaba:20170324150908p:plain
左下の状態は最終的に負けになって欲しいところですが,上のコードだとそうならない.
方針はわかってるのに解ききれなかったのは悔しい.

AOJ 1337 Count the Regions

問題概要

xy 平面に長方形が N 個与えられる.長方形によっていくつの領域に分かれるか求めよ.

・制約
1 <= N <= 50
長方形がある x, y 座標は 0 <= x, y <= 10^6

解法

N が小さいので座標圧縮と確信できる.
与えられた座標を2倍して持っておくと,幅が1しかない領域を数えるのが楽になる.(たとえば,3と4は2倍するとそれぞれ6と8になるので,3と4の間として7を使える.vectorで圧縮後の平面を持つのでこうしておくと便利.)

ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
using P = pair<int, int>;

int main() {
    int n;
    while(cin >> n, n) {
        vector<int> xs, ys;
        vector<int> x1(4*n), x2(4*n), y1(4*n), y2(4*n);
        for(int i=0; i<n; ++i) {
            int l, t, r, b;
            cin >> l >> t >> r >> b;
            l *= 2; t *= 2; r *= 2; b *= 2;
            x1[i*4] = l, x2[i*4] = r, y1[i*4] = t, y2[i*4] = t;
            x1[i*4+1] = l, x2[i*4+1] = l, y1[i*4+1] = b, y2[i*4+1] = t;
            x1[i*4+2] = r, x2[i*4+2] = r, y1[i*4+2] = b, y2[i*4+2] = t;
            x1[i*4+3] = l, x2[i*4+3] = r, y1[i*4+3] = b, y2[i*4+3] = b;
            for(int j=-1; j<=1; ++j) {
                xs.push_back(l+j);
                xs.push_back(r+j);
                ys.push_back(t+j);
                ys.push_back(b+j);
            }
        }
        sort(xs.begin(), xs.end());
        sort(ys.begin(), ys.end());
        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());
        for(int i=0; i<4*n; ++i) {
            x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();
            x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();
            y1[i] = find(ys.begin(), ys.end(), y1[i]) - ys.begin();
            y2[i] = find(ys.begin(), ys.end(), y2[i]) - ys.begin();
        }
        int res = 0;
        vector<vector<bool>> fld(ys.size(), vector<bool>(xs.size(), false));
        for(int i=0; i<4*n; ++i) {
            for(int y=y1[i]; y<=y2[i]; ++y) {
                for(int x=x1[i]; x<=x2[i]; ++x) {
                    fld[y][x] = true;
                }
            }
        }
        for(int i=0; i<ys.size(); ++i) {
            for(int j=0; j<xs.size(); ++j) {
                if(fld[i][j]) {
                    continue;
                }
                fld[i][j] = true;
                res++;
                queue<P> que;
                que.push(make_pair(i, j));
                while(!que.empty()) {
                    P p = que.front(); que.pop();
                    int sy = p.first, sx = p.second;
                    int dy[4] = {0, -1, 0, 1},
                        dx[4] = {1, 0, -1, 0};
                    for(int k=0; k<4; ++k) {
                        int ty = sy + dy[k], tx = sx + dx[k];
                        if(ty < 0 || ys.size() <= ty || tx < 0 || xs.size() <= tx) {
                            continue;
                        }
                        if(fld[ty][tx]) {
                            continue;
                        }
                        que.push(make_pair(ty, tx));
                        fld[ty][tx] = true;
                    }
                }
            }
        }
        cout << res << endl;
    }
}