Google Code Jam Round.1C

結果

A(small/large) C(small)
565th 40pts 1:36:15

なんとか通過したよー。
Round2通過は無理だろうけど精一杯がんばります。

A　Diamond Inheritance

全ての点からDFSして既にvisitedの点に当たったらYes、そうでなければNo。

C　Box Factory

ぱっと見でLCSっぽいDPだろうなぁと思う。
問題分から、同じ種類のbox/toyが連続してこないという確信が得られなかったので
まず連続する同じ種類の生産をまとめるようにする。

まず

dp[i][j] := i-thBox,j-thToyまで使ったときの発送できる最大値

として考えてみる。

• >種類が同じなら詰めるだけ詰めて余ったのは捨てる、種類が違ったらbox/toyのどちらかを全て捨てる
• >Pretest1あった！
• >small提出
• >WA
• >Pretest2が合ってない←アホ
• >詰めたあと捨てないほうがいい場合もあるのか…
• >dp[i][j][k][l]でk,l=個数とすると明らかにMLE
• >solve(i,j,k,l)で再帰にしてみよう
• >サンプル合う
• >small,correct
• >largeのランダムジェネレータを書く
• >やっぱりTLE
• >k,lはあんまりいろんな値を取らない気がするのでメモ化してみる
• >N=100,M=100でもすぐ返ってくるようになる
• >submit

結果的にWAだった、原因は1ケースごとにメモの値を消していなかったこと。
複数ケースの場合は特に注意したい…。

以下ソース

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define PB push_back
#define MP make_pair
#define ll long long

inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}

class State{
public:
    int bi,ti;
    ll bn,tn;
    State(int _bi, int _ti, ll _bn, ll _tn){
        bi = _bi;
        ti = _ti;
        bn = _bn;
        tn = _tn;
    }
    
    bool operator <(State arg) const{
        if(bi != arg.bi){
            return bi < arg.bi;
        }
        if(ti != arg.ti){
            return ti < arg.ti;
        }
        if(bn != arg.bn){
            return bn < arg.bn;
        }
        return tn < arg.tn;
    }
};

map<State, ll> ma;
int n,m;
vector<ll> box, toy;
vector<int> kbox, ktoy;

ll solve(int bi, int ti, ll bn, ll tn){
    ll ret=0,tmp;
    if(bi >= n || ti >= m) return 0;
    if(ma.find(State(bi,ti,bn,tn)) != ma.end()){
        return ma[State(bi,ti,bn,tn)];
    }

    if(kbox[bi] == ktoy[ti]){
        //すぐ捨てる
        ret = max(ret, solve(bi+1, ti+1, box[bi+1], toy[ti+1]) + min(bn,tn));
        //とっておく
        if(bn > tn){
            ret = max(ret, solve(bi, ti+1, bn-tn, toy[ti+1]) + min(bn,tn));
        }else if(bn < tn){
            ret = max(ret, solve(bi+1, ti, box[bi+1], tn-bn) + min(bn,tn));
        }
    }else{
        ret = max(ret, solve(bi+1,ti,box[bi+1], tn));
        ret = max(ret, solve(bi,ti+1,bn, toy[ti+1]));
    }
    return ma[State(bi,ti,bn,tn)] = ret;
}

int main(){
    int t;
    cin >> t;
    for(int x=1;x<=t;x++){

        cin >> n >> m;
        ll numtmp=0,ktmp;
        ll kind, num;
        box.clear();
        toy.clear();
        kbox.clear();
        ktoy.clear();
        ma.clear();
        cin >> num >> kind;
        for(int i=1;i<n;i++){
            cin >> numtmp >> ktmp;
            if(ktmp == kind){
                num += numtmp;
            }else{
                box.PB(num);
                kbox.PB(kind);
                num = numtmp;
                kind = ktmp;
            }
        }
        box.PB(num);
        kbox.PB(kind);

        cin >> num >> kind;
        for(int i=1;i<m;i++){
            cin >> numtmp >> ktmp;
            if(ktmp == kind){
                num += numtmp;
            }else{
                toy.PB(num);
                ktoy.PB(kind);
                num = numtmp;
                kind = ktmp;
            }
        }
        toy.PB(num);
        ktoy.PB(kind);

        n = box.size();
        m = toy.size();
        ll ret;
        ret = solve(0,0,box[0],toy[0]);
        printf("Case #%d: %lld\n",x,ret);
    }
}