Writer 解説: https://img.atcoder.jp/nikkei2019-2-qual/editorial.pdf

問題概要

$ 3N (N \leq 10^5)$ 個の整数 $ K, K+1, \cdots, K+3N-2, K+3N-1 (K \leq 10^9)$ から，$ N$個の三つ組$ (a_1, b_1, c_1), \cdots, (a_N, b_N, c_N) $ を作る．次の条件を満たすことが可能なら条件を満たす $ N$個の三つ組を1つ構成する．

$ 1 \leq i \leq N $ を満たす全ての $ i $ について， $ a_i + b_i \leq c_i $ が成り立つ．

解法概要

3つの値のうち，c は大きければ大きいほど余裕ができるので， $ K+2N, K+2N+1, \cdots, K+3N-2, K+3N-1 $ は c にしておく．

a, b となる全ての値の和が c となる全ての値の和を超えてしまうと明らかに不可能なので，ここから先はそれ以外の場合のみ考える．

可能な場合について (私が) パッと思いつくのが，

のように a, b, c を小さな値から順番に詰めていく方法 (WA解法1) や

のような小さい値からへびのような配置で詰めていく方法 (WA解法2) だが，

これらの方法は $ N \geq 2 $ の場合となると有効ではない．

例えば

は条件を満たさないし WA 解法2 (へび配置) でも条件を満たせないが，

のような場合は条件を満たすことができる．

ここからは色々な構成方法が考えられるのではないかと思うが，私が最初に思いついた解法を紹介する．

この解法は WA 解法1 (小さい順に詰める) を基にしている．

WA 解法 1 における a を固定し， b をいい感じに回転して， c でつじつまを合わせることを考える．

$ N = 5, K = 3 $ の場合，

のようにすると 7+12 > 17 となってしまい構成できなくなってしまう． b の最も大きな値である 12 を使っても構成できるようにするためには，少なくとも 12 と組む a が 17 (cの最大値) - 12 = 5 以下でないといけない．5 と 12 が一緒になるように回転すると次のようになる．

厳密には， b の最大値が $ K+2N-1$，c の最大値が $ K+3N-1$ であるため，これらの値と組まされる a は $ N $ である．そのため， $ K \leq N $ という条件も必要になる．

(5, 12, 17) の組のすぐ上以外は，c は 2 ずつ減少するので，あとはいい感じに c を埋めれば良い．

ただし，N が偶数の場合は a+b が同じになる組が登場するので同じ値を二度使わないようにだけ注意する．

もう少しちゃんと書くと， N が奇数のときは次のようになる．

a	b	c
K+N-1	K+2N-(N-K+2)	K+3N-2
$ \vdots $	$ \vdots $	$ \vdots $
N+1	K+N	K+2N+1
N	K+2N-1	K+3N-1
N-1	K+2N-2	K+3N-3
$ \vdots $	$ \vdots $	$ \vdots $
K	K+2N-(N-K+1)	K+3N-{2(N-K)+1}

N のある行よりも上は c が偶数になり，それ以外は c が奇数になる．

実装では N が偶数である場合の判定を横着して， set を用いることですでに使った値を二度使わないようにしている．

ソースコード

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

using namespace std;

using ll =  long long;

bool check(const ll n, const ll k) {
    ll ab_sum = 2*n*k + (2*n-1) * (2*n) / 2;
    ll c_sum = n*(k+2*n) + (n-1) * n / 2;
    return ab_sum <= c_sum && k <= n;
}

int main() {
    ll n, k;
    cin >> n >> k;
    if(!check(n ,k)) {
        cout << -1 << endl;
        return 0;
    }

    set<ll> unused_c;
    for(ll i=k+2*n;i<k+3*n;++i) unused_c.insert(i);
    vector<tuple<ll, ll, ll>> ans;
    ll a = n, b = k+2*n-1, c = k+3*n-1;
    ans.emplace_back(a, b, c);
    while(--a >= k) {
        --b;
        c = *unused_c.lower_bound(a+b);
        ans.emplace_back(a, b, c);
        unused_c.erase(c);
    }
    a = k+n-1;
    --b;
    while(a > n) {
        c = *unused_c.lower_bound(a+b);
        ans.emplace_back(a, b, c);
        unused_c.erase(c);
        --a;
        --b;
    }

    for(auto t: ans) {
        cout << get<0>(t) << " " << get<1>(t) << " "  << get<2>(t) << endl;
    }

}

所感

自力で解けたけど，それゆえに本番で問題文を読むことすらしなかったのが悔やまれる問題．

NoiminのNoise

第二回全国統一プログラミング王決定戦予選 E - Non-triangular Triplets

問題概要

解法概要

ソースコード

所感