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

AOJ 0517 Longest Steps

解法

しゃくとり法でやった.
与えられた k 枚のカードをソートしておく.
0が含まれていれば1つだけ飛ばせるので,それは場合分けで処理.
行けるところまでいったら,左端をカードの数字が1以上飛んでいるところに更新する.

オーダーはソートがネックなので O(klogk + k).

しかし,連続部分を pair でもっておいて,0 が含まれていれば隣り合う連続区間をつなげる,みたいな実装の方が自然かもしれない.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, k;
    while(cin >> n >> k, n) {
        vector<int> v(k);
        for(int i=0; i<k; ++i) {
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        int f = v[0] == 0;
        int l = 0+f, r = 1+f, cnt = 0, next_l = -1;
        int res = 0;
        while(true) {
            next_l = -1;
            while(r < k && (v[r] - v[r-1] == 1 || v[r] - v[r-1] == 2)) {
                if(v[r] - v[r-1] == 1) {
                    r++;
                } else if(cnt < f) {
                    cnt++;
                    next_l = r;
                    r++;
                } else {
                    break;
                }
            }
            res = max(res, r - l + ((r == k && cnt < f) || cnt));
            if(r == k) {
                break;
            }
            if(next_l == -1) {
                l = r;
                r++;
            } else {
                l = next_l;
            }
            cnt = 0;
        }
        cout << res << endl;
    }
}

AOJ 0302 Star Watching

解法

星を輝度でソートする.
輝度の最小(つまり左端)を決めて,しゃくとり法でできる.
座標の最大最小は,priority_queueでもmapでもmultisetでもなんでもよい.
自分は最初 priority_queue で書いて通したが,他の人のコードを読むと multiset が一番すっきりしていたのでそちらで書き直した.

計算量は O(NlogN)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
int main() {
    int N, d;
    cin >> N >> d;
    vector<tuple<int, ll, ll>> v(N);
    for(int i=0; i<N; ++i) {
        int b;
        ll x, y;
        cin >> x >> y >> b;
        v[i] = make_tuple(b, x, y);
    }
    sort(v.begin(), v.end());
 
    ll res = 0;
    multiset<ll> x, y;
    int r = 0;
    for(int l=0; l<N; ++l) {
        while(r < N && get<0>(v[r]) - get<0>(v[l]) <= d) {
            x.insert(get<1>(v[r]));
            y.insert(get<2>(v[r]));
            r++;
        }
        res = max(res, (*x.rbegin() - *x.begin()) * (*y.rbegin() - *y.begin()));
 
        if(r == N) {
            break;
        }
        x.erase(x.find(get<1>(v[l])));
        y.erase(y.find(get<2>(v[l])));
    }
    cout << res << endl;
}

AOJ 0299 Railroad II

解法

d(i) をソートし,かつ p が 0 となるようにずらしておく.
ちょっと考えると,解の候補としては

  • d(1) まで反時計回りで一周する
  • d(M) まで時計回りで一周する
  • d(i) まで時計回りで訪れた後,そこから反時計回りで d(i+1) まで訪れる
  • d(i+1) まで反時計回りで訪れた後,そこから時計回りで d(i) まで訪れる

の4通りしかないことが分かる.
あとはこれを実装するだけ.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int N, M, p;
    cin >> N >> M >> p;
    vector<int> d(M);
    for(int i=0; i<M; ++i) {
        cin >> d[i];
        d[i] -= p;
        d[i] = (d[i] + N) % N;
    }
    sort(d.begin(), d.end());
    int res = min(d.back(), N - d[0]);
    for(int i=0; i<M-1; ++i) {
        res = min(res, min(2*d[i] + (N - d[i+1]), 2*(N - d[i+1]) + d[i]));
    }
    cout << res * 100 << endl;
}

AOJ 0254 Scone

問題概要

数列 {a_n} と整数 M が与えられる.
適当な i <= j を選んで ( a(i) + a(i+1) + ... + a(j) ) mod M を最大化せよ.

・制約
1 <= n <= 30000
1 <= M <= 100000
0 <= a(i) <= 2^32 - 1

解法

累積和と二分探索.
mod を取った累積和を sum(i) で表すことにする.
右端 j を固定すると,j までの累積和の中で sum(j) 以上で最小のもの sum(i) を見つけて, ( sum(j) - sum(i) + M ) mod M を見ていけば良い.
sum(i) を見つけるのに二分探索する.setにつっこめば楽.

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n, m;
    while(cin >> n >> m, n) {
        vector<int> a(n+1);
        for(int i=1; i<=n; ++i) {
            cin >> a[i];
            a[i] %= m;
            (a[i] += a[i-1]) %= m;
        }
        int res = 0;
        set<int> s;
        for(int i=1; i<=n; ++i) {
            auto it = s.upper_bound(a[i]);
            res = max(res, a[i]);
            if(it != s.end()) {
                res = max(res, (a[i] - *it + m) % m);
            }
            s.insert(a[i]);
        }
        cout << res << endl;
    }
}

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;
}