Google Code Jam 2013 Round2 - pes

残念な結果に終わった昨年のリベンジマッチ。

A : Ticket Swapping

問題文長い…と思って一旦飛ばしたものの、他も難しそうだったので結局Aから。
端から入退場をシミュレーションして、一番新しいチケットで退場すれば良さそう。
そのシミュレーションをどう書くかでだいぶ迷ってしまって無駄に時間かかった。
stackを使うなんて華麗な実装は考えもしなかったぜ…。

最初にInput/Outputだけ見てmodには気付いたので、被害者の会入りせずに済んだ。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdio>

using namespace std;

const int MOD = 1000002013;

int main(){
    int T; cin >> T;
    int N, M;
    for(int test=1;test<=T;test++){
        cin >> N >> M;
        map< int, pair<long long, long long> > mp;
        long long origSum = 0;
        for(int i=0;i<M;i++){
            int o, e, p;
            cin >> o >> e >> p;
            long long cost = ((2LL*N-(e-o)+1)*(e-o)/2)%MOD;
            origSum += (p*cost)%MOD;
            origSum %= MOD;
            if(mp.count(o)) mp[o].first += p;
            else            mp[o] = make_pair(p, 0);
            if(mp.count(e)) mp[e].second += p;
            else            mp[e] = make_pair(0, p);
        }
        long long decSum = 0;
        int prev = -1;
        vector< pair<long long, long long> > vp;
        for(map< int, pair<long long, long long> >::iterator it=mp.begin();it!=mp.end();it++){
            int idx = it->first;
            for(int i=0;i<vp.size();i++){
                long long cost = ((2LL*vp[i].first-(idx-prev)+1)*(idx-prev)/2)%MOD;
                decSum += (vp[i].second*cost)%MOD;
                decSum %= MOD;
                vp[i].first -= (idx-prev);
            }
            if(it->second.first > 0){
                vp.push_back(make_pair(N, it->second.first));
                sort(vp.rbegin(), vp.rend());
            }
            int exitNum = it->second.second;
            for(int i=0;i<vp.size();i++){
                if(exitNum == 0) break;
                if(vp[i].second < exitNum){
                    exitNum -= vp[i].second;
                    vp[i].second = 0;
                } else {
                    vp[i].second -= exitNum;
                    exitNum = 0;
                }
            }
            prev = idx;
        }
        int res = (origSum-decSum+MOD)%MOD;
        printf("Case #%d: %d\n", test, res);
    }
}

B : Many Prizes

解像度の関係で2^Nが2^Mに見えて、Mとは一体…としばらく悩んだ。
最悪の当たり方をした場合にある人が何位になるかは簡単に求められそう。
- 最初、i番の人に勝てる人はi人いる。
- 同じブロックにiさんより強い人がいれば、その中の一人にiさんを負かしてもらう。
- 次にiさんと同じブロックに残せるiさんより強い人の数は、(i-1)/2人。
- これをiさんがブロック内で一番強い人になるまで繰り返せば良い。

で、iさんが最悪でもP位以内に入れれば(i-1)さんも絶対P位以内に入れる。
二分探索乙でした。

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

long long solveWin(int N, long long P){
    long long L = 0, R = 1LL<<N;
    while(R-L>1){
        long long mid = (L+R)/2;
        long long win = mid;
        long long rank = 0;
        for(int i=N-1;i>=0;i--){
            if(win > 0){
                rank += (1LL<<i);
                win = (win-1)/2;
            } else {
                break;
            }    
        }
        if(rank < P) L = mid;
        else         R = mid;
    }
    return L;
}

long long solveLose(int N, long long P){
    long long L = 0, R = 1LL<<N;
    while(R-L>1){
        long long mid = (L+R)/2;
        long long lose = (1LL<<N)-mid-1;
        long long rank = 0;
        for(int i=N-1;i>=0;i--){
            if(lose > 0){
                lose = (lose-1)/2;
            } else {
                rank = (1LL<<(i+1))-1;
                break;
            }
        }
        if(rank < P) L = mid;
        else         R = mid;
    }
    return L;
}

int main(){
    int T; cin >> T;
    int N; long long P;
    for(int test=1;test<=T;test++){
        cin >> N >> P;
        printf("Case #%d: %lld %lld\n", test, solveWin(N, P), solveLose(N, P));
    }
}

C : Erdős–Szekeres

最初はSmallすら分からなくてオワタ感あった。

Aは、最長増加部分列を求めるDPの結果得られるDPテーブルと一緒。
Bも、ひっくり返した数列に対して作ったDPテーブルみたいなもの。
そこから考えてみると、
- i < j について、A[i] >= A[j] なら X[i] > X[j]。
- i < j のとき、A[i]+1 = A[j] をみたす最大のiに対して X[i] < X[j]
が言えて、Bについても似たような大小関係が得られる。

これが十分条件かは自信がなかったものの、
- X[i] < X[j]をみたす組について、i->jに辺を貼ったグラフを作る
- 辞書順最小のトポロジカル順序を求める
- (ﾟдﾟ)ｳﾏｰ
という作戦を決行してみることに(※辞書順最小を見落としてて1回WAもらった)。

辞書順最小のトポロジカル順序をどうするかと思ったものの、O(n^2)で良かったので、
- 作ったグラフに対して各ノードの入次数を持っておく
- 入次数0のノードのうち最小のインデックスのものを選ぶ
- 選んだノードを除いての各ノードの入次数を更新する(O(n))
という感じでやった。

以下のコードは提出コードから要らない部分を除いたもの。

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

using namespace std;

int in[2000];
int road[2000][2000];

int main(){
    int T; cin >> T;
    int N;
    int A[2000], B[2000];
    for(int test=1;test<=T;test++){
        cin >> N;
        for(int i=0;i<N;i++) cin >> A[i];
        for(int i=0;i<N;i++) cin >> B[i];
        memset(in, 0, sizeof(in));
        memset(road, 0, sizeof(road));
        for(int i=0;i<N;i++){
            int lastIdx = -1;
            for(int j=0;j<i;j++){
                if(A[j] >= A[i]) road[i][j] = 1;
                if(A[j]+1 == A[i]) lastIdx = j;
            }
            if(lastIdx != -1) road[lastIdx][i] = 1;
        }
        for(int i=N-1;i>=0;i--){
            int lastIdx = -1;
            for(int j=N-1;j>i;j--){
                if(B[j] >= B[i]) road[i][j] = 1;
                if(B[j]+1 == B[i]) lastIdx = j;
            }
            if(lastIdx != -1) road[lastIdx][i] = 1;
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                if(road[i][j]) in[j]++;
        }

        vector<int> res(N);

        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(in[j] == 0){
                    res[j] = i+1;
                    for(int k=0;k<N;k++)
                        if(road[j][k]) in[k]--;
                    in[j] = -1;
                    break;
                }
            }
        }

        printf("Case #%d:", test);
        for(int i=0;i<N;i++) printf(" %d", res[i]);
        printf("\n");
    }
}

Rank 79 : /oo/oo/oo/--/ Score 63, Penalty 2:20:02

2010はギリギリ通過で、2011はラスト数分で通過ライン滑り込み、2012は大敗北でしたが、
初めて余裕を持ってRound2を通過することができました。
Round3も0でない点数目指してがんばります。