CODE FESTIVAL 2016 Final H - Tokaido

問題ページ

考えたこと

• dp[すぬけくんのコマの位置][りんごさんのコマの位置][手番] としたDPはできそう
• 明らかに状態が多すぎるので減らしたい
• コマが隣接して置かれていないとき，左のコマは右に隣接するまで一つずつずらすのが最適
• dp[左のコマの位置][手番] としたDPにできそう
• 手番が変わったとしてもdpの正負が反転するだけなので手番は持たなくていい
• 遷移を考えると dp[i] = max(-dp[j]+a[j]-sum(a[i+1]~a[j-1]) | i<j) となる
• この遷移はO(N)かかるので高速化が必要
• 区間add区間maxができる遅延セグ木があればO(log N)でできる
• M=1なら解けた
• a[n-1]が変化したときに答えがどう変化するのか？
• a[n-1]がめっちゃ大きかったら答えが a[0]-a[1]-sum(a[2]~a[n-2])+a[n-1] となるのははい
• 実験を書いたが大した規則がなくて不可能では？
  -----解説を見た-----
• dpの遷移の高速化をもっと単純な形にできる
• 蟻本p67の重複組み合わせの変形のように dp[i] と dp[i+1] の形が似ていることを使う
• dp[i] = max(dp[i+1]-a[i+1], a[i+1]-dp[i+1]) = abs(dp[i+1]-a[i+1]) となる
• ans = a[n-1] からスタートして ans = abs(ans-a[i]) という遷移をi=n-2からi=2まで行えばよい
• dp[i=jまで遷移を行った][ansの値] = score としたDPを考えると答えはdp[n-1][a[n-1]]となる
• このDPの遷移は特徴的なので高速にできる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n);
    REP(i, n-1) cin >> a[i];

    ll sum = 0;
    FOR(i, 2, n-1) sum += a[i];

    deque<ll> dp(sum+1);
    REP(i, sum+1) dp[i] = i;
    FOR(i, 2, n-1) {
        // dp[1]~dp[a[i]] を逆順にしてpush
        vector<ll> v;
        REP(j, a[i]) v.push_back(dp[j+1]);
        REP(j, a[i]) dp.push_front(v[j]);
    }

    ll q;
    cin >> q;
    while(q--) {
        ll x;
        cin >> x;
        if(sum <= x) {
            cout << x-sum+a[0]-a[1] << endl;
        } else {
            cout << dp[x]+a[0]-a[1] << endl;
        }
    }

    return 0;
}

こういうDPの高速化を問題としてはじめて見た
DPを高速化して単純な問題にする→その問題の愚直DPを書いて高速化 するDP高速化詰め合わせセットって印象