自明な上界を達成できるパターンだった！

問題へのリンク

問題概要

長さ $N+1$ の非負整数列 $A_{0}, A_{1}, \dots, A_{N}$ が与えられる。この数列はどの隣接する二項も値が異なる。

この数列をなるべく多くの $N+1$ 項の非負整数列へと分解せよ。分解とは

分解された各非負整数列の各項を足すと、もとの数列 $A$ に一致する
どの分解された非負整数列も、隣接二項間の大小関係が、もとの数列 $A$ に一致する

という条件を満たすことを指す。

制約

$1 \le N \le 100$
$0 \le A_{i} \le 10^{4}$

考えたこと

サンプルを見てみる。 $A = (3, 8, 6, 10)$ は、次の 2 つの整数列に分解できる。

$(2, 4, 3, 5)$
$(1, 4, 3, 5)$

3 つには分解できない。なぜならば、8 - 6 = 2 だからだ。もし 3 つに分解できたとすると、合計したときに、二項目と三項目との差が 3 以上にならなければならない。しかし $A_{1} - A_{2} = 2$ なのでそれは不可能だ。以上から

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ より多く分解することはできない

ということがいえた。

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ は達成可能

逆に、 $K$ 個に分解することは常に可能だ。それが示されれば、 $K$ 個が最大値ということで確定する。

まずなるべく多く分解するためには、「各 $A_{i}$ をなるべく均等に $K$ 分割したい」という気持ちになる。そして余った分は上から配っていく感じで OK。

コード

#include <bits/stdc++.h>
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;
    string S;
    cin >> N >> S;
    vector<long long> x(N+1);
    for (int i = 0; i < N+1; ++i) cin >> x[i];

    long long M = 1LL<<60;
    for (int i = 0; i < N; ++i) chmin(M, abs(x[i]-x[i+1]));

    vector<vector<long long>> res(M, vector<long long>(N+1));
    for (int j = 0; j <= N; ++j) {
        long long r = x[j] % M;
        for (int i = 0; i < M; ++i) {
            res[i][j] = x[j] / M;
            if (i < r) ++res[i][j];
        }
    }

    cout << M << endl;
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j <= N; ++j) cout << res[i][j] << " ";
        cout << endl;
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 053 A - >< again (水色, 400 点)

問題概要

制約

考えたこと

$K = \min_{i = 0, 1, \dots, N-1} |A_{i} - A_{i+1}|$ は達成可能

コード