Japan Alumni Group Summer Camp 2011 Day 2 - 4

AOJ

なんか3日連続でコンテストがあったのででました。

Day2: 3AC 14位
Day3: 7AC 9位
Day4: 4AC 8位

なかなか調子よくて、いい順位がとれました。
問題は全体的に短めで読みやすかったのでいい感じだったと思います。
難易度も、初日がやけに難しかった以外は私にはちょうど良かったです。

Day2

初日は問題がとても難しくて、大変だった。
私は問題は前から解いていく方針なので、最後の方の問題が簡単なセットだったから最初は全然解けなくて焦りました。
中盤以降、皆が解いている問題を解く方針にして(いつもそうしてる)、解いていった。
2日も前のことなので、難しい問題セットだったということしか記憶にない＞＜

Day3

前日の反省を活かし、最後の問題から開いていく。
Iが、ただの幾何で解けそうだと思いプログラムを書いていくも、実は細かいところを考えると結構難しい。
Iは諦めて周りを見ると、最初の方の問題を結構解いていてどう見ても作戦失敗。
気を撮り直して最初の問題から適当に解いていった。
解けそうな問題は全部解いたつもりなので非常に満足の行く結果に。

なんか印象に残ってるのでGの、完全グラフ探索コードだけ貼っておく。

#include <cstdio>
#include <algorithm>
#include <climits>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

int candidate[100];
int cn;
int fr[100][100];
int n, m;
int ans;

void solve(int now){
  if(now == cn){
    if(cn == 1) return;
    int tmp = 0;
    REP(i,cn){
      int mm = INT_MAX;
      REP(j,cn)if(i != j){
	mm = min(mm, fr[candidate[i]][candidate[j]]);
      }
      tmp += mm;
    }

    //REP(i,cn) printf("%d ", candidate[i]+1); printf(": %d\n", tmp);

    ans = max(ans, tmp);
  }else{
    // select
    {
      int cntmp = cn;
      int rab = candidate[now];
      for(int i = now + 1; i < cn;){
	if(fr[rab][candidate[i]] == 0){
	  --cn;
	  swap(candidate[i], candidate[cn]);
	}else{
	  ++i;
	}
      }

      solve(now + 1);

      cn = cntmp;
    }
    // not select
    {
      --cn;
      swap(candidate[now], candidate[cn]);
      solve(now);
      swap(candidate[now], candidate[cn]);
      ++cn;
    }
  }
}

int main(){
  scanf("%d%d", &n, &m);
  cn = n;
  REP(i,m){
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    fr[a-1][b-1] = fr[b-1][a-1] = c;
  }
  REP(i,n) candidate[i] = i;
  
  solve(0);

  printf("%d\n", ans);

  return 0;
}

次に入れても、完全グラフを壊さないリスト(candidate)を更新しながらdfsして行った。
結構工夫して書いたけど、あんまり頑張らなくても通るらしい。残念。

Day4

ちょっと眠いのを頑張って参加。
なんか適当にファーストアクセプトを狙おうと思い、問題タイトルからC問題を選ぶ。
なんかグリーディーにやったら行けそうと思い提出するもWA。
仕方ないのでDPを書いて提出。MLEを食らうが、少し工夫しAC。
しかしその間にファーストアクセプトはとられました＼(^o^)／
その後は皆が解いている問題を解いていって終わった感じ。
DとIは方針は間違ってなさそうだったので、あと２問はワンチャンあった。
とくにIはその後すぐにACもらえたのでもったいない。

Fが、面白い感じにかけたと思うので、貼り貼り。

#include <set>
#include <algorithm>
#include <cstdio>

#define REP(i,n) for(int i=0; i<(int)(n); i++)

using namespace std;

const int MAX = 1000;
const int iter = 1000;
double memo[iter + 1][MAX]; //終わってから気づいたけどMAX+1にしないとあふれる場合がある

int s, n, k;

double prob[101];
double buff[101];

int main(){
  scanf("%d%d%d", &s, &n, &k);

  s = abs(s);

  if(s == 0){
    puts("0.0000000");
    return 0;
  }

  REP(i,n*k+1) prob[i] = 0.0;
  prob[0] = 1.0;
  REP(cc, k){
    REP(i,n*k+1) if(prob[i] != 0.0){
      REP(j,n){
	buff[i+j+1] += prob[i] * (1.0 / n);
      }
    }
    REP(i,n*k+1) prob[i] = buff[i];
    REP(i,n*k+1) buff[i] = 0.0;
  }

  double ans = 0.0;

  if(MAX < s){
    int kitai = (k * (n + 1) / 2);
    int tmp = (s - MAX + kitai - 1) / kitai;
    ans = tmp;
    s -= tmp * kitai;
  }

  memo[0][s] = 1.0;
  REP(cc, iter){
    REP(i,s+1) if(memo[cc][i] != 0.0){
      REP(j,n*k+1){
	int next = abs(i - j);
	memo[cc+1][next] += memo[cc][i] * prob[j];
      }
    }
    ans += (cc + 1) * memo[cc+1][0];
    memo[cc+1][0] = 0.0;
  }

  printf("%.7f\n", ans);
  
  return 0;
}

最初の位置が遠い場合は、適当に付近まで近似的にぶっ飛ぶ。
そのあとは付近を収束させる感じで繰り返し計算。
想定解は、連立方程式を解くみたいでまだちょっと分かっていない。