garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい

AtCoder Grand Contest 007_B_Construct Sequences

Atcoder 青色

青色の問題.久々にアルゴリズムもへったくれもない問題です.数学好きなのでこういった問題の方が好きです.

atcoder.jp

問題の説明

1からNを並べた順列{p_i}(1≦i≦N)が与えられる.以下の条件を満たす数列{a_N}および,{b_N}を出力せよ.

条件

  • 1≦a_i,b_i≦10^9
  • 正整数列{a_i}は狭義単調増加
  • 正整数列{b_i}は狭義単調減少
  • a_{p_i}+b_{p_i}は狭義単調増加
  • 1≦N≦200,000

 

考えた事

問題文にある通り,答え方としてはp_iに合わせてa_i,b_iを作りだし,答えればよい.

まず考えるべきは全探索である.極端な話であるが*1,この問題の入力としてあり得る数列p_i全てに合わせa_iとb_iを先に全て作りだせば答えとなる.

この指針には2つ問題がある.まず第一に計算量である.当然のことながら,上の方法を行う場合,計算量はO(200000!)となりどう考えても無理がある.

次に解法としての適当さである.そもそもこの問題は答えを1つ列挙する問題である.裏を返せば全部試すなと読めるのではなかろうか.答えが複数種類ある事を暗に示唆されている問題で愚鈍に全て試すのは明らかに効率がよくない.

ではどうすべきか.こういった問題において効果的なのは条件を徐々に厳しくする形で問題を見つめる事である.全ての条件を一気に考えても分からなくなってにゃにゃ！？となっておしまいである.我々は人間だ.カワイイカワイイにゃんこと違って物事を整理して考えねばいけない種族だ.がんばろう.

この場合だと「a_{p_i}+b_{p_i}は狭義単調増加」はめんどうそうである.ひとまず置いて置こう.他から考える.とはいえ他の条件は狭義単調増加,狭義単調減少な数列を作るだけなのですぐできるだろう.なぜわざわざすぐできる事を分けて先に書いたか.ここが今回の大きなポイントである.

つまり今回の問題はp_iによらず,先にa_i,b_iの数列を作っておき,p_iに合わせてそれを微調整するように考えればいいのである.

a_i+b_iがどの順で大きくなるかはp_iが入力されるまで分からない.ならば先にどんな数列を作っておくとよいだろうか.自分なら先に作っておくべき数列はiによらずa_i+b_iが同じ大きさになる数列と考える.

そして後からp_iの順にそれぞれの数列の項に+iずつしていけば「a_{p_i}+b_{p_i}は狭義単調増加」の条件も満たす.ここで注意しなければならないのは,+iによる変化量である.これを行うと一番小さいa_{p_1}とa_{p_{20000}}とで19999の差が出来る.「{a_i}は狭義単調増加」という条件を満たしたままこれを行うには,先にa_iとa_{i+1}とで20,000の差をつけておけばいい.

つまり,a_1=20000,a_2=40000,a_3=60000......といった具合だ.そしてこれによって先に作るべきb_iの詳細も分かる.「iによらずa_i+b_iが同じ大きさになる数列」を作ればいいのだからb_i-b_{i+1}=20000となるように作ればいい.

vll a(N);
    vll b(N);
    rep(i, N) { a.at(i) = 20000 * (i + 1); }
    rep(i, N) { b.at(i) = 20000 * (N - i); }

このようにして作ったa_iとb_iが以上である.これによって「a_{p_i}+b_{p_i}は狭義単調増加」以外の全てを満たし,「iによらずa_i+b_iが同じ大きさになる数列」を作成できた.

後は,

rep(i, N) {
        a.at(p.at(i) - 1) += i;
        b.at(p.at(i) - 1) += i;
    }

として,p_iの順に1ずつ差をつけていけば,元々の条件を満たしながら「a_{p_i}+b_{p_i}は狭義単調増加」の条件をみたす.

そしてこれは高々,(2×10^4)^2=4×10^8であり,a_i,b_i≦10^9の制約を満たしている.以上をもって数列a_i,b_iを作成する事に成功した.

こういった問題は典型解がなく,難しいが非常に楽しいものである.コツというか自分の考えとしては条件を緩める,特にp_iのような変数絡みの条件を後回しにすると,解放のアプローチが得やすいだろう.ここまでお読みいただきありがとうございました.

プログラム

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<long long>;
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
int main() {
    ll N;
    cin >> N;
    vll p(N);
    rep(i, N) { cin >> p.at(i); }
    vll a(N);
    vll b(N);
    rep(i, N) { a.at(i) = 20000 * (i + 1); }
    rep(i, N) { b.at(i) = 20000 * (N - i); }
    rep(i, N) {
        a.at(p.at(i) - 1) += i;
        b.at(p.at(i) - 1) += i;
    }
    rep(i, N) { cout << a.at(i) << ' '; }
    cout << endl;
    rep(i, N) { cout << b.at(i) << ' '; }
    cout << endl;
}

*1:極端とつけている時点で察しはつくかもしれない