予鈴

競プロとか備忘録とか…

B - Construct Sequences

B - Construct Sequences

解く前に考えてたこと

・配列の要素数を超える大きい公差を持った等差数列を考えて、順列Pによる差を相殺したい。
・具体例を考えるも、一般化できずに死亡、特に、入力n の値によって、数列を構築しようとしたのが問題かもしれない。

正解

M = 40000
A_i = M(i+1)
B_i = M(n-i-1) などとすると、 A_i +B_i = M(n)となる。つまり、添字iの値によらず一定である。
問題はA_i + B_iもまた単調に増加する数列とする必要があるので、A_{P_i}の添字にiを足してやる。Mが巨大なので、問題なく数列を構築することができる。

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? 1e9:1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){int b=0;for(auto itr :a){if(b++!=0)cout << " "; cout << itr;} }
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
#define int ll
signed main(){
    int n; cin >> n;
    vector<int>p(n);  rep(i,n) cin >> p[i];
    vector<int>a(n),b(n);
    int maxi = 40000;
    rep(i,n){
        a[i] = maxi*(i+1);
        b[i] = maxi*(n-i-1)+1;
    }
    rep(i,n){
        a[p[i] - 1] += i;
    }
    join(a); cout << endl;
    join(b); cout << endl;
}
感想

書いてみると意外と解けそうな気がする。ちなみにWAを量産したのはf:id:yebityon:20180527130538p:plain
この制約を見落としていたため。
M = 1e7 などとすると死にます。