diverta 2019_2 C - Successive Subtraction (水色, 500 点)

復元つらい

問題へのリンク

問題概要

黒板に 個の整数 が書かれている。

• 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える

という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎ターンごとに出力)

制約

• 

考えたこと

この手の問題では、最終的に出来上がりうるものをわかりやすく特徴づけられないか、わかりやすく言い換えられないかを考えることが肝要だと思う。500 点だろうと 700 点だろうと 900 点だろうと。

で、少し考えてみると、例えば元の整数が (2, -4, 5, 6) とかだったとき、最終的に

• 2 - (-4) + 5 + 6 = 17

とかは作ることができることがわかる。ちょっと手を動かすと

• ± ± ± ... ± の形しか作れない
• プラスマイナスのうち、「全部がプラス」と「全部がマイナス」は作れない

ということが見えてくる。でもプラスとマイナスが両方とも存在していたら、それは絶対に作れそうだ。復元が要求されていなくて最大値を求めるだけだったら、ここで「証明のない貪欲」を投げる手もあるが、今回は復元もしなければならない。

...とその前に

最大値

上記の仮説を信じて、先に最大値を求めてみる。

もし「全部プラス」や「全部マイナス」が許されているなら単純に、

• が正のものはプラス
• が負のものはマイナス

とすればよい。でも単純にこれだと「全部プラス」になる場合もあるので、その場合は が一番小さいところにマイナスをつければよい。「全部マイナス」になる場合については が一番大きいところにプラスをつければよい。

復元

以上から、各 についてプラスをつけたいのかマイナスをつけたいのかまではハッキリとした。そうなるように操作を復元したい。まずはプラスとマイナスに分類する。

• プラス: a, b, c, d
• マイナス: x, y, z

とかになったとする。うまいことやりたい。とりあえず

• プラス: a, b, c, d
• マイナス: x

という具合にマイナスが 1 個だけの場合が作れたら、あとはそこから y, z, ... を引き続けるだけになる。これは次のように作れる。

• x - a
• x - a - b
• x - a - b - c
• d - (x - a - b - c) = (a + b + c + d) - x

という感じ。最後以外は x から引いていって、最後だけ逆から引く感じ。

(一応) 全部プラスと全部マイナスがダメな理由

全部プラスや全部マイナスがダメなのは最初に 個の整数の中から を選んで としたとき、この部分については、その後の操作で か かをずっと行き来することになるため。

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

int N;
vector<long long> A;

void solve() {
    vector<long long> plus, minus;
    for (int i = 0; i < N; ++i) {
        if (A[i] >= 0) plus.push_back(A[i]);
        else minus.push_back(A[i]);
    }
    sort(plus.begin(), plus.end(), greater<long long>());
    sort(minus.begin(), minus.end());
    if (minus.empty()) minus.push_back(plus.back()), plus.pop_back();
    if (plus.empty()) plus.push_back(minus.back()), minus.pop_back();

    vector<pair<long long, long long> > res;
    long long cur = minus[0];
    for (int i = 0; i+1 < plus.size(); ++i) {
        res.push_back({cur, plus[i]});
        cur -= plus[i];
    }
    res.push_back({plus.back(), cur});
    cur = plus.back() - cur;

    for (int i = 1; i < minus.size(); ++i) {
        res.push_back({cur, minus[i]});
        cur -= minus[i];
    }

    cout << cur << endl;
    for (auto p : res) cout << p.first << " " << p.second << endl;
}

int main() {
    cin >> N;
    A.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    solve();
}

diverta 2019_2 B - Picking Up (緑色, 300 点)

こういう全探索、意外と思い浮かぶようになるまでが遠いよね。
そして のケースが結構厄介 ^^;

問題へのリンク

問題概要

二次元平面上に 点がある。最初に整数 を自分で決める。そして、 個の点を好きな順序で順に辿っていく。このとき、

• 最初の点では +1
• その後移動するたびに、移動ベクトルが のときは +0
• そうでないときは +1

したものがペナルティとなる。ペナルティの最小値を求めよ。

制約

• 

考えたこと

まず の選び方が途方もなく多く見えるがそんなことはなく、

• ある についての

についてのみ試せば十分である。なぜなら、どの 2 点をとってもその差ベクトルになってないような を使ったらペナルティは になる。これより小さくはできない。なので、上記の場合だけ試せばよい。この時点で 通り。

さて、 を決めたらあとは、実際に 点を上手く並べることで、なるべく なジャンプが多くなるようにしたい。再びすべての に対して調べることで、 なジャンプが何個あるのかを求めればよい。

ただし、 の場合に要注意！！！！！

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

int N;
vector<long long> x, y;

int solve() {
    if (N == 1) return 1;

    int res = N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i == j) continue;
            long long dx = x[j] - x[i], dy = y[j] - y[i];

            int sub = 0;
            for (int i2 = 0; i2 < N; ++i2) {
                for (int j2 = 0; j2 < N; ++j2) {
                    if (j2 == i2) continue;
                    if (dx == x[j2] - x[i2] && dy == y[j2] - y[i2]) ++sub;
                }
            }
            res = min(res, N - sub);
        }
    }
    return res;
}

int main() {
    cin >> N;
    x.resize(N); y.resize(N);
    for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
    cout << solve() << endl;
}

AtCoder ABC 128 F - Frog Jump (橙色, 600 点)

• ジャンプの過程を無視して、最終的に出来上がるものがどうなるかを考えて、それをわかりやすく特徴づける
• 調和級数になるタイプの全探索

というタイプの問題。結構重たい。AGC なら C 問題でありそう。

問題へのリンク

問題概要

個の地点 にそれぞれ のスコアがある。

• 0 から出発してぴょんぴょんジャンプしながら を目指す
• 「すでに踏んだところ」または「0 未満」または「N 以上」の地点を踏んだらゲームオーバー

というルールで、最初に整数 を決めて、

• から出発して、 右に飛んで、 左に飛んで、、、(踏んだところのスコアを得ていく)

を繰り返す。最終的に に到達する方法のうち、得られる総スコアの最大値を求めよ。

制約

• 
• 

考えたこと

の場合はスコア 0。以後 とする。

とりあえず としてよい。そうでなかったら 2 ターン目で終わってしまう。ここで とおくと、これがちょっと特別な感じの値になっている。というのも最終的に踏む地点は

• 
• 

みたいになる。 の値をすべて調べて、両端からどこまで伸ばすかを全部調べれば OK。これは調和級数の和になってて全部で の計算量になる。

が の約数のときだけ注意して場合分けしてやった。

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N; cin >> N;
    vector<long long> s(N);
    for (int i = 0; i < N; ++i) cin >> s[i];

    long long res = 0;
    for (int p = 1; p <= N-1; ++p) {
        if ((N-1) % p == 0) {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < j; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
        else {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < N-1 && j > p; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
    }
    cout << res << endl;
}

AtCoder ABC 128 E - Roadwork (青色, 500 点)

これと似てる！！！
これの解法 3 みたいなやり方をイベントソートって呼ぶのね。

drken1215.hatenablog.com

問題へのリンク

問題概要 (意訳)

くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う

• 整数 が与えられて、区間 [ ) 全体を と比較して小さい方で置き換える

このあと、以下の 個のクエリに答えよ

• の位置の値を答えよ。

制約

• 

考えたこと

大体この問題と一緒なので、この問題に対応した 3 つの解法がそれぞれ使える。ここでは解法 3: イベントソートでやってみる。

drken1215.hatenablog.com

まさにいもす法の「区間加算」ならぬ「区間 chmin」バージョンという感じ！！！

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

using type = pair<int, long long>; // 1: query, 0; delete, -1: insert
using event = pair<long long, type>;

int main() {
    int N, Q; cin >> N >> Q;
    vector<event> v;
    for (int i = 0; i < N; ++i) {
        int s, t, x; cin >> s >> t >> x;
        v.push_back({s-x, type(-1, x)});
        v.push_back({t-x, type(0, x)});
    }
    for (int i = 0; i < Q; ++i) {
        int d; cin >> d;
        v.push_back({d, type(1, i)});
    }
    sort(v.begin(), v.end());

    vector<long long> res(Q);
    multiset<long long> se;
    for (auto p : v) {
        long long x = p.first;
        int type = p.second.first;
        long long val = p.second.second;
        if (type == -1) se.insert(val);
        else if (type == 0) se.erase(se.lower_bound(val));
        else res[val] = (se.empty() ? -1 : *(se.begin()));
    }
    for (auto v : res) cout << v << endl;
}

AtCoder ABC 128 D - equeue (水色, 400 点)

こういう全探索が意外と出てこないという意見はよく聞くよね。
同時に「複数種類の操作を行える問題では、操作の流れを単純化する」という典型思考を試す問題でもある。

問題へのリンク

問題概要

あなたは誕生日プレゼントとして友人から dequeue D

を貰いました。

deque は左右に長い筒であり、 個の宝石が一列に詰められています。宝石の価値は左から順に です。負の価値の宝石が詰められている場合もあります。

はじめ、あなたは 1 つも宝石を持っていません。あなたは、 に対して以下の 4 種類の操作から 1 つを選んで実行することを 回まで行うことができます。

• 操作 A: D に詰められた宝石のうち、左端の宝石を取り出して手に入れる。D が空の場合、この操作を行えない。

• 操作 B: D に詰められた宝石のうち、右端の宝石を取り出して手に入れる。D が空の場合、この操作を行えない。

• 操作 C: 持っている宝石を 1 つ選んで D の左端に詰める。宝石を持っていない場合、この操作を行えない。

• 操作 D: 持っている宝石を 1 つ選んで D の右端に詰める。宝石を持っていない場合、この操作を行えない。

操作終了後に持っている宝石の価値の合計の最大値を求めてください。

制約

• 
• 

考えたこと

こういう操作系の問題では、まずは操作の流れを単純化できないかと考えてみると良さそう。ひとまず

• 操作 A, B を一通り終えてから
• 操作 C, D をやっていく

というものだけ考えればよいことはすぐにわかる。A をやって C をやって、また A をやって...というのは完全に無駄だからだ。...ということがわかると、実はもうほとんど解けていて、

• 左から 個取り出す
• 右から 個取り出す (ここまでで かつ を満たす必要がある)
• 最大で 回、取り出したやつを大きい方から筒に再び詰めていく (ただしマイナスのものは詰めなくてよい)

とすれば OK。 通りの場合を調べればよくて、それぞれについて高々 程度の計算量 (取り出した価値のソートが一番時間かかる) で実現できるので、全体として で間に合う。

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

int main() {
    int N, K; cin >> N >> K;
    vector<long long> V(N);
    for (int i = 0; i < N; ++i) cin >> V[i];

    long long res = 0;
    for (int p = 0; p <= min(K, N); ++p) {
        for (int q = 0; p + q <= min(K, N); ++q) {
            vector<long long> v;
            long long cur = 0;
            for (int i = 0; i < p; ++i) v.push_back(V[i]), cur += V[i];
            for (int i = 0; i < q; ++i) v.push_back(V[N-1-i]), cur += V[N-1-i];
               
            sort(v.begin(), v.end());
            for (int i = 0; i < min(K - p - q, (int)v.size()); ++i) {
                if (v[i] < 0) cur -= v[i];
            }
            res = max(res, cur);
        }
    }
    cout << res << endl;
}