Xmas Contest 2012

hosさんのXmas Contest 2012にPerorinCoders(りんごさん、きゅうり)で出て１位でした。
EとGを解いたのでコードをのせときます。

G
Ruins2と同じような方法でO(N^3)で出来る。

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<double,P> Q;

const double eps = 1e-10;
const int MX = 405, INF = 100000000;

int n;
int x[MX], y[MX];
ll dp[6][MX][MX];
Q e[MX*MX]; int ei;

int main(){
  int te;
  scanf("%d",&te);
  while(te--){
    scanf("%d",&n);
    
    rep(i,n) scanf("%d%d",&x[i],&y[i]);
    
    rep(k,6)rep(i,n)rep(j,n) dp[k][i][j] = 0;
    
    ei = 0;
    rep(i,n){
      dp[0][i][i] = 1;
      rep(j,n){
        if(i == j) continue;
        e[ei++] = Q(atan2(x[j]-x[i],y[j]-y[i]),P(i,j));
      }
    }
    
    sort(e,e+ei);
    
    int a, b;
    rep(i,ei){
      a = e[i].se.fi;
      b = e[i].se.se;
      
      rep(k,5)rep(j,n) dp[k+1][j][b] += dp[k][j][a];
    }
    
    ll ans = 0;
    rep(i,n) ans += dp[5][i][i];
    
    printf("%lld\n",ans);
  }
  
  return 0;
}

手元実行なので、O(N^4)でも間に合うらしく、ちょっと残念。

E
実行時間長くてもいいならいろいろ解き方あるっぽい？
まずは、強連結成分分解してDAGにして、exp+bonusとexpの最大値を両方計算していけば解ける。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef pair<double,P> Q;

const int MX = 300005, INF = 999999999;

int n, m;
bool bl[MX];
struct edge{ int next, to, c, d;};
edge e[MX], re[MX], ke[MX];
int head[MX], g;
int rhead[MX], rg;
int khead[MX], kg;
bool used[MX];
int vn[MX], nv[MX], vk;
bool kb[MX], kc[MX], kd[MX];

int dp1[MX], dp2[MX];

void dfs(int v){
  if(used[v]) return;
  used[v] = true;
  for(int i = head[v]; i != -1; i = e[i].next) dfs(e[i].to);
  nv[vk--] = v;
}
void rdfs(int v){
  if(!used[v]) return;
  used[v] = false;
  vn[v] = vk;
  for(int i = rhead[v]; i != -1; i = re[i].next) rdfs(re[i].to);
}

int main(){
  int te, a, b, c, d, s, t;
  scanf("%d",&te);
  
  char ch;
  while(te--){
    scanf("%d%d",&n,&m);
    
    rrep(i,n){
      scanf(" %c",&ch);
      if(ch == '0') bl[i] = false; else bl[i] = true;
      head[i] = -1; rhead[i] = -1; khead[i] = -1;
      used[i] = false;
      kb[i] = kc[i] = kd[i] = false;
    }
    g = rg = kg = 0;
    
    rep(j,m){
      scanf("%d%d%d%d",&a,&b,&c,&d);
      e[g] = (edge){head[a],b,c,d}; head[a] = g++;
      re[rg] = (edge){rhead[b],a,c,d}; rhead[b] = rg++;
    }
    
    vk = n;
    rrep(i,n) dfs(i);
    vk = 1;
    rrep(i,n){
      if(!used[nv[i]]) continue;
      rdfs(nv[i]);
      vk++;
    }
    
    rrep(i,n){
      a = vn[i];
      if(bl[i]) kb[a] = true;
      for(int j = head[i]; j != -1; j = e[j].next){
        b = vn[e[j].to];
        if(a == b){
          if(e[j].c) kc[a] = true;
          if(e[j].d) kd[a] = true;
        } else {
          ke[kg] = (edge){khead[a],b,e[j].c,e[j].d}; khead[a] = kg++;
        }
      }
    }
    
    s = vn[1]; t = vn[n];
    //rrep(i,n) printf("%d ",nv[i]);
    //printf("%d %d\n",s,t);
    
    rrep(i,t){ dp1[i] = -INF; dp2[i] = -INF;}
    dp1[0] = 0; dp2[0] = 0; kc[0] = false; kd[0] = false;
    ke[kg] = (edge){-1,s,0,0}; khead[0] = kg++;
    
    for(int i = 0; i <= t; i++){
      if(dp1[i] == -INF) continue;
      if(kc[i]) dp1[i] = dp2[i] = INF;
      if(kd[i]) dp1[i] = INF;
      if(kb[i]) dp2[i] = dp1[i];
      for(int j = khead[i]; j != -1; j = ke[j].next){
        b = ke[j].to; c = ke[j].c; d = ke[j].d;
        dp1[b] = min(max(dp1[b],dp1[i]+c+d),INF);
        dp2[b] = min(max(dp2[b],dp2[i]+c),INF);
      }
    }
    
    printf("%d\n",dp2[b]);
  }
  
  return 0;
}

両方1発ACでうれしい。