naoya_t@topcoder

GCJ 2010 Round 2 : B. World Cup 2010

14:57 |

後回しにしてたBが簡単すぎて泣きそう

教訓

もちつけ

コンテスト中の思考

• そもそも何で後回しにしたかというと最初に個々のチームについて考えてしまったからで
• それだと上の方で重複しててどうのこうのとか。（もう馬鹿かと。）
• 再帰でなんとかなるよねきっと
• 各チームについて、買わなければならないチケット数 = (P-見逃してもよい回数) だよね。そこまでは簡単
• あるぇーどういう再帰で書いたらいいんだ（焦）
• 後で考えるか…
• その「後」が来なかった件

冷静に解き直したコード

• 落ち着いて書いたら20分かからなかった
• small/largeとも瞬殺＆一発AC

#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cstdio>
#include <cmath>
#include <cctype>
using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define rep(var,n)  for(int var=0,lim=(n);var<lim;var++)
#define REP(var,ar)  for(int var=0,lim=(ar).size();var<lim;var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define all(c)  (c).begin(),(c).end()
#define found(s,e)  ((s).find(e)!=(s).end())

int P, es;
vector<int> M;
vector<vector<int> > prices;
vector<vector<int> > minm;

#define NON 1e9+1 // 100000x1000=1e9...

map<int,int> mm;

int sub(int lev,int idx,int seen){
  // 0..10<4>, 0..1023<10>, 0..10<4>
  int k=(lev<<14)|(idx<<4)|seen;
  if(found(mm,k)) return mm[k];
  
  if (seen < minm[lev][idx]) return mm[k]=NON;
  if (lev==P) return mm[k]=0;
  int skip_this = sub(lev+1,2*idx,seen) + sub(lev+1,2*idx+1,seen);
  int watch_this = prices[lev][idx] + sub(lev+1,2*idx,seen+1) + sub(lev+1,2*idx+1,seen+1);
  int min_ = min(skip_this, watch_this);
  return mm[k]=((min_ >= NON)? NON : min_);
}

int main(){
  int T;cin>>T;
  rep(t,T){
    mm.clear();
    
    cin>>P; es=1<<P;
    M.resize(es);
    rep(i,es) cin>>M[i];
    
    prices.resize(P); minm.resize(P+1); minm[P].resize(es);
    rep(i,es) minm[P][i]=P-M[i];
    for(int j=P-1;j>=0;--j){
      int es_j=1<<j;
      prices[j].resize(es_j); rep(i,es_j) cin>>prices[j][i];
      minm[j].resize(es_j); rep(i,es_j) minm[j][i]=max(minm[j+1][i*2]-1,minm[j+1][i*2+1]-1);
    }
    
    int ans=sub(0,0,0);
    printf("Case #%d: %d\n", 1+t, ans);
  }
  return 0;
}