Google Code Jam Round.2

結果

A-small/large
B-small
20pts,1225thで敗退。

もうちょいA早く通してC-smallだけでも通せばよかったなー。

A

問題文が割と読みにくかった。
要はツルを掴んでターザンして通り過ぎたor到達したツルに乗り換えることができる。
ツルが短すぎて掴めないということはなく、任意の長さ登って掴めるが、
逆(途中を掴んだ後下におりてより遠くに到達すること)はできない。

• >次に掴むツルでより遠くにいけるような状態ならよくて、到達点が同じなら

より手前から飛び移った方がお得、ってgreedyじゃないのかなぁ

• >書いてみる、sample合う
• >WA
• >ごにょごにょいろんなケース考える
• >90分ぐらい経過
• >どういうケースで通らないのか解らないので諦める
• >BFSで全探索してみる
• >sampleは合う
• >引数の(何番目のツル,掴んだ位置)でメモ化してみる
• >WAったsampleは普通に動くので出してみる
• >AC
• >large落として突っ込んでみる
• >終わらない
• >同じツルをいままでより上で掴むケースは明らかにいらないので枝狩る
• >終わった
• >提出

ソース

#define PB push_back
#define MP make_pair
#define ll long long

vector<int> ds;
vector<int> ls;
map<pair<int,int>, bool > m;
int dmax[10001];
int g,n;
bool solve(int pos, int len){
    if(ds[pos] + len >= g) return true;
    if(m.find(MP(pos,len)) != m.end()){
        return m[MP(pos,len)];
    }
    bool res = false;
    for(int i=pos+1;i<n;i++){
        if(ds[i] > ds[pos] + len) break;
        if(dmax[i] > min(ds[i] - ds[pos], ls[i])) continue;
        dmax[i] = min(ds[i]-ds[pos],ls[i]);
        res |= solve(i, min(ds[i] - ds[pos], ls[i]));
    }
    return m[MP(pos,len)] = res;
}

int main(){
    int x;
    cin >> x;
    for(int t=1;t<=x;t++){
        memset(dmax,-1,sizeof(dmax));
        int d,l;
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> d >> l;
            ds.PB(d);
            ls.PB(l);
        }
        cin >> g;

        printf("Case #%d: %s\n", t, solve(0,ds[0])?"YES":"NO");
        ds.clear();
        ls.clear();
        m.clear();
    }
}

B-small

10個しかないとか適当に置いても終わるだろjk

• >AC
• >largeは無理だろうなー
• >TLE

感想

来年はTシャツ取れるといいなー