Codeforces Round #143 B. Magic, Wizardry and Wonders

なかなか解法が思いつかなかったのでとりあえず要素数5の場合を紙の上でシミュレーションしてみた。

与えられた数列を a0, a1, a2, a3, a4　とすると
　1手目　a0, a1, a2, (a3-a4)
　2手目　a0, a1, (a2-(a3-a4))
　3手目　a0, (a1-(a2-(a3-a4)))
　4手目　(a0-(a1-(a2-(a3-a4))))
最終的にこんなかんじになる。カッコとはずすと

　a0 - a1 + a2 - a3 + a4　=　(a0 + a2 + a4) - (a1 + a3)

と書ける。これから

　（奇数番目の項の和）-（偶数番目の項の和）= d

となればいいとわかる。
奇数項の和を x , 偶数項の和を y とおくと、
　x - y = d
とかける。また元の配列の各要素は1以上l以下なので、奇数項の個数をp、偶数項の個数をqとおくと、
　p <= x <= l*p
　q <= y <= l*q →　q <= (x-d) <= l*q
となる。この２つの式を満たすようなxを全探索で求める。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n,d,l;
    cin>>n>>d>>l;
    int p=(n+1)/2;
    int q=n-p;
    vector<int> odd(p), even(q);
    for(int x=p; x<=l*p; ++x) {
        int y=x-d;
        if(q<=y && y<=l*q) {
            // 奇数番目の項の和がx, 偶数番目の項の和がyになるような配列を作る
            int i=0;
            while(x>0) { odd[i%p]++; i++; x--; }
            i=0;
            while(y>0) { even[i%q]++; i++; y--; }
            break;
        }
    }
    if (odd[0]==0) { cout<<-1<<endl; return 0; }
    for(int i=0;i<n;++i) {
        if(i%2==0) cout<<odd[i/2]<<' ';
        else cout<<even[i/2]<<' ';
    }
    cout<<endl;
    return 0;
}