Round 2 Problem B. World Cup 2010 small
Google Code Jam Round 1 は最高1008位でした。
あーあRound2へは進めないな・・・と思ったら、おめでとうメールが。
確認するとちょうど1000位になってるよ!
よくわからないけど、Round2に進めることになってしまったので、練習練習。
http://code.google.com/codejam/contest/dashboard?c=635102#s=p1
smallは簡単。
最初の方の試合は全部見ない。試合ごとに後何回見逃せるかを計算して、結果が0になる試合は見なきゃいけないので見る。
Large問題は始めの試合を観ておいたほうがコストが低い、と言う事があり得るから、このアルゴリズムじゃ無理。他の人のソースを見て勉強します・・・。
#include <iostream> #include <algorithm> #include <string> #include <cmath> #include <vector> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;i++) int P; int M[2000]; int prices[15][2000]; int cost(int int solve(int no) { cin >> P; int teams = 1<<P; rep(i, 0, teams-1) cin >> M[i]; rep(i, 1, P) { rep(j,0, (teams>>i) - 1) cin >> prices[i-1][j]; } int cost = 0; rep(i, 1, P) { rep(j, 0, (teams>>i) - 1) { M[j] = min(M[j*2], M[j*2+1]); if(M[j]==0) cost++; else M[j]--; } } cout << "Case #" << no << ": " << cost() << endl; } int main() { int T; cin >> T; rep(no, 1, T) { solve(no); } return 0; }