2015-12-03

Typical DP Contest C - トーナメント

問題リンク : C: トーナメント - Typical DP Contest | AtCoder

解法 :
DP全然思い浮かばなかったので愚直に計算した
他の人のコード見て勉強します

コード:

#include<bits/stdc++.h>

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

using namespace std;

double R[1200],dp[2][1200];
int K;

inline double calc(double P,double Q) { return 1.0 / ( 1.0 + pow(10.0,(Q-P)/400.0)); }

void dfs(int cur_K) {
  if( cur_K <= 1 ) {
    for(int i=0;i<(1<<K);i+=2) {
      dp[cur_K&1][i]   = calc(R[i],R[i+1]);
      dp[cur_K&1][i+1] = calc(R[i+1],R[i]);
    }
    return;
  }
  dfs(cur_K-1);
  int phase = cur_K&1;
  rep(i,(1<<K)) dp[phase][i] = 0;
  rep(winner,(1<<K)) {
    int size = (1<<cur_K);
    int pre_size = (1<<(cur_K-1));
    for(int i=0;i<(1<<K);i+=size) {
      if( i <= winner && winner < i+size ) {
        int range_L=-1,range_R=-1;
        for(int j=i;j<i+size;j+=pre_size){
          if( j <= winner && winner < j+pre_size ) {
            range_L = j, range_R = j+pre_size;
            break;
          }
        }
        REP(j,i,i+size) {
          if( range_L <= j && j < range_R ) continue;
          dp[phase][winner] += dp[!phase][winner] * dp[!phase][j] * calc(winner[R],R[j]);
        }
        break;
      }
    }
  }
}

void compute(int K) {
  dfs(K);
  rep(i,(1<<K)) printf("%.10f\n",dp[K&1][i]);
}

int main() {
  cin >> K;
  rep(i,(1<<K)) cin >> R[i];
  compute(K);
  return 0;
}

2015-12-02

Typical DP Contest B - ゲーム

動的計画法典型DPコンテスト

問題リンク : B: ゲーム - Typical DP Contest | AtCoder

解法 :
dp[i][j] := 左の山の残りがi個、右の山の残りがj個の時の（すぬけのターン）最大or（すめけのターン）最小値

両方の山が０を初期状態とし、１手1手戻りながら計算する

コード :

#include<bits/stdc++.h>

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

using namespace std;

#define SUNUKE 0
#define RNG    1
#define IINF INT_MAX

int n[2],v[2][1010],dp[1010][1010];

void compute() {
  rep(i,n[0]+1) rep(j,n[1]+1) dp[i][j] = -1;
  int player = (((n[0]+n[1])&1)?SUNUKE:RNG);
  dp[0][0] = 0;
  rep(phase,n[0]+n[1]+1) {
    rep(i,n[0]+1) {
      int j = phase - i;
      if( j < 0 || j > n[1] ) continue;
      if( dp[i][j] == -1 ) continue;
      // SUNUKE 
      if( player == SUNUKE ) {
        if( i < n[0] ) {
          if( dp[i+1][j] == -1 ) dp[i+1][j] = -IINF;
          dp[i+1][j] = max(dp[i+1][j],dp[i][j]+v[0][i]);
        }
        if( j < n[1] ) {
          if( dp[i][j+1] == -1 ) dp[i][j+1] = -IINF;
          dp[i][j+1] = max(dp[i][j+1],dp[i][j]+v[1][j]);
        }
      }
      // RNG
      if( player == RNG ) { 
        if( i < n[0] ) {
          if( dp[i+1][j] == -1 ) dp[i+1][j] = IINF;
          dp[i+1][j] = min(dp[i+1][j],dp[i][j]);
        }
        if( j < n[1] ) {
          if( dp[i][j+1] == -1 ) dp[i][j+1] = IINF;
          dp[i][j+1] = min(dp[i][j+1],dp[i][j]);
        }
      }
    }
    player = !player;
  }
  cout << dp[n[0]][n[1]] << endl;
}

int main() {
  rep(i,2) cin >> i[n];
  rep(i,2) rep(j,i[n]) cin >> v[i][n[i]-j-1];
  compute();
  return 0;
}

2015-12-02

Typical DP Contest A - コンテスト

動的計画法典型DPコンテスト

問題リンク : A: コンテスト - Typical DP Contest | AtCoder

解法 :
bool dp[i] := i が作れるならtrue, otherwise false

コード :

#include<bits/stdc++.h>

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

using namespace std;

int n;
bool dp[10001];

int main() {
  dp[0] = true;
  cin >> n;
  rep(i,n) {
    int tmp;
    cin >> tmp;
    for(int j=10000;j>=0;j--) if( dp[j] ) dp[j+tmp] = true;
  }
  int cnt = 0;
  rep(i,10001) cnt += dp[i];
  cout << cnt << endl;
  return 0;
}

2015-12-01

ACM-ICPC 2015 Tsukuba Regional Contest : つくば大会参加記

日常 ICPCアジア地区参加記

ACM-ICPC 2015 つくば大会に参加したので記録

チーム情報

コーチ : 先輩　研究が忙しい中つくばまで来て頂き有難うございました　「あのシャワー水しかでなかったんだけど」
コンテスタント1 : 後輩T　競プロ歴２日　英語マスター　バンバン訳してバンバン伝える　後輩Sと共にアルゴリズマーをやったりもする
コンテスタント2 : 後輩S　競プロ歴３日　アルゴリズマー＋司令官　バンバン解法を出してくる　英語は苦手らしい
コンテスタント3 : 自分　実装＋典型問題担当　分からないことをクエリー形式で後輩Sに投げまくる

１日目
筑波へ移動

つくばへ向かう
車内で腹痛に襲われる
冷や汗が止まらず右耳も聞こえなくなり、加えて視界に黒い点が広がっていった
さらには吐き気、めまい等の細かい症状があり、その場に座り込もうかとも考えたが重病だと思われると気まずいので耐えた今思えば十分に重症だった..
電車から降りたら治った

トライアルユース

普段ならcontrolがある場所にCapsLockがありタイプミスしまくる
CapsLockが何故存在するのか考える
controlとCapsLockの位置を変える方法が分からないので後で某チームに聞きに行くことにする

Javaチャレンジ

とりあえず四隅のブロックの真ん中以外のスクエアに移動し、その後はブロックの存在する２方向に攻撃し続けるAIを書く
submitするがwaiting
40分経過 waiting
waiting
...

歓迎会

マグロのSUSHIが一瞬で消える
豚汁が最高に美味しい
SUSHI 豚汁豚汁肉　サーモン
川の流れのようにチーム紹介

宿舎

去年のオリンピックセンターと似た感じ
ブラックコーシーとマックスコーヒーを購入
再度腹痛に襲われる正露◯を飲む
トイレと部屋を行き来する、局地的に熱い夜だった

２日目
朝

昨日買った２種類のコーヒーをキメる
腹の調子は良い、カピオへ移動

コンテスト
A : 0から順に存在するか確かめても十分間に合うくらい答えは小さい気がする => AC
トイレに行く

B : やるだけ => WA
後輩とデバッグ　実装、方針、解釈を確かめる　どれも大丈夫そうで謎
コーナーケースを考えながらトイレに行く
数十分経過した時点で後輩から「ここは俺に任せて先に行け」と指示が飛んできたので次へ

C : 問題概要を聞きトイレに行く
　ちょうどn手でいける場所は状態遷移行列のn乗で求まるでしょ、しかし最小にする方法は謎
もう一人の後輩と一緒に考えるが謎
トイレに行く
数十分が経過した時、Bを任せていた後輩から声が掛かる
(後輩) : 一つ聞きたいんですが、このREPとはなんですか？
(自分) : REP(i,s,n) は for で i を s から n-1 まで１ずつ回してくdefineだよ
(後輩) : ではなぜ#define REP(i,s,n) for(int i=0;i<n;i++)なんですか
(自分) : !?

B : REPの初期値を修正し提出 => AC
テンプレミスで１時間４０分溶かして辛い
トイレに行く
トイレから帰る途中会津チームの方をみると風船が６つあるように見える
n度見した後立ち止まって風船を数える、確かに6つある

D : 順位確認、会津が強い
Cが謎なのでDの概要を聞く
ただの巡回スケジューリングでしょ典型と言い残しトイレに行くがトイレ待ちのキューが詰まっている
トイレの中にスタッフを配置して複数人入れれば良いのに、、と考える
トイレから復帰し実装、提出 => AC

C : 後輩が思いついたそうなので話を聞きとりあえず実装
サンプルは一致したが弱いので一応一人１ケースずつサンプルを考えてチェックすることに
後輩の考えたサンプルが一致しない、方針がダメという話になる
トイレに行く　スタッフが１人中に入り複数人入れるようになっていた
後輩から、今は幅優先でやっているものを優先度を付きにしたら良いと言われる
結構Ad-hocな感じで、なぜそれで良いのか理解できないので実装は保留
トイレに行き順位を確認する
会津がすごい順位になってる
「会津凄い、会津強くない？」と繰り返し後輩に問いかけていたら後輩から集中しろと怒られる、申し訳オブザワールド
後輩と議論していると、ゴールから頂点をマージしていってスタートとゴールが同じグループに入ったら終了でそれまでのマージ回数を答えると良さげという話になる
実装、提出 => WA
コードをプリントしてデバッグ
行列の掛け算のことろでなぜかmod 2をしていることに気がつく
これは１以上になったら１にまとめるの間違いでは？
修正、提出 => AC

E : 残り１０分くらいしかない、説明を聞くもよく分からない
実装間に合わなそうなのでコンテストを振り返ってみる

終了

結局４完２１位だった
小さな実装ミスで大きくタイムロスをしてしまったので反省
今のチームはこれで最後（一人が他大学に行くため）なので、
来年出るなら一人は競プロしてる人、もしくは非競プロ勢を競プロ勢化して入れようと決意（自分が止まってもチームが止まらないために）
そのためには競技プログラミング部を作ったほうが良いかもしれない
アルゴリズマーの後輩は来年もいるので競プロ勢化したい

３日目
エクスカーションに参加し帰宅、即寝た

2015-11-24

LiveArchive 6582 : UVa 1642 : Magical GCD

UVa LiveArchive 苦手分野数学

問題リンク:https://icpcarchive.ecs.baylor.edu/external/65/6582.pdf

問題概要：
長さn(1<= n <= 100000)の数列が与えられる
数列の各要素a[i]は1以上10^12以下
数列の連続した部分列を取り出し、(部分列全体のgcd) * (部分列の長さ) を値とする
値の最大値を出力せよ

解法：
部分列の最も右となる要素を全探索する
最も右の要素の番号をiとする
iを０からn−１まで順に試す
その中で[j,i] (0<=j<=i)から得られる各gcdについての値を求める
gcdが重複しているものについては最もjが０に近いようなものを選ぶ
このとき、[j,i]から得られるgcdの集合の大きさはO( log(a[i]) )しかない
なぜなら、
gcd(a[j,i-1]) != gcd(a[j,i]) のとき、gcd(a[j,i-1])/2>=gcd(a[j,i])なので、
gcd(a[j,i])はO(log(a[i])回後には１になるため

コード：

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

int main() {
  int T;
  cin >> T;
  while( T-- ) {
    int n;
    cin >> n;
    ll maxi = 0;
    map<ll,int> mp; 
    rep(i,n) {
      ll a;
      cin >> a;
      maxi = max(maxi,a);
      map<ll,int> tmp;
      tmp[a] = i;
      for(map<ll,int>::iterator it=mp.begin();it!=mp.end();it++) {
	ll gcd = __gcd(it->first,a);
	maxi = max(maxi,gcd*(ll)(i-(it->second)+1));
	if( tmp.count(gcd) ) tmp[gcd] = min(tmp[gcd],it->second);
	else                 tmp[gcd] = it->second;
      }
      mp = tmp;
    }
    cout << maxi << endl;
  }
  return 0;
}

2015-11-08

AOJ 1350 : There is No Alternative

MST ICPC AOJ 橋切断点

問題リンク:There is No Alternative | Aizu Online Judge

問題概要:
重み付き無向グラフが与えられる
これに対する最小全域木は複数存在しうるが、それら全ての最小全域木に共通して存在する辺の数とそれらの総和を求めよ

解法:
Kruskal法を用いてMSTを構築する
全ての最小全域木に共通して存在するような辺は、その辺の重み以下の辺からなるグラフにおける橋となる
辺を小さい順に追加してグラフを構築しつつ追加する辺の重みが変わるタイミングで橋を求め、それらを数えれば良い

コード:

#include<bits/stdc++.h>

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

using namespace std;

struct Edge { 
  int src,dst,w; 
  bool operator < ( const Edge& e ) const {
    if( w != e.w ) return w < e.w;
    if( src != e.src ) return src < e.src;
    return dst < e.dst;
  }
};
const int MAX_V = 510; //
int V,E; //
vector<Edge> G[MAX_V]; // undirected graph
vector<int> dfs_num,dfs_low,dfs_parent,articulation_vertex;
int dfsNumberCounter, dfsRoot, rootChildren;
int cost[MAX_V][MAX_V];

//O(V+E)
int base_weight;
vector<Edge> bridges;
#define UNVISITED -1
void articulationPointAndBridge(int u){
  dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
  rep(j,(int)G[u].size()){
    Edge &v = G[u][j];
    if( dfs_num[v.dst] == UNVISITED ) {
      dfs_parent[v.dst] = u;
      if( u == dfsRoot ) rootChildren++;

      articulationPointAndBridge(v.dst);

      if( dfs_low[v.dst] >= dfs_num[u] ) articulation_vertex[u] = true;
      if( dfs_low[v.dst] >  dfs_num[u] ) {
        if( base_weight == cost[u][v.dst] ) {
          bridges.push_back((Edge){u,v.dst,base_weight});
        }
        //printf("Edge (%d,%d) is a bridge\n",u,v.dst);
      }
      dfs_low[u] = min(dfs_low[u],dfs_low[v.dst]);
    } else if( v.dst != dfs_parent[u] ) {
      dfs_low[u] = min(dfs_low[u],dfs_num[v.dst]);
    }
  }
}

void calculateArticulationPointAndBridge(){
  dfsNumberCounter = 0;
  dfs_num.assign(V,UNVISITED);
  dfs_low.assign(V,0);
  dfs_parent.assign(V,0);
  articulation_vertex.assign(V,0);
  
  //printf("Bridges:\n");
  rep(i,V) {
    if( dfs_num[i] == UNVISITED ) {
      dfsRoot = i, rootChildren = 0;
      articulationPointAndBridge(i);
      articulation_vertex[dfsRoot] = ( rootChildren > 1 );
    }
  }
  
  //printf("Articulation Points:\n");
  //rep(i,V) if( articulation_vertex[i] ) printf("Vertex %d\n",i);
}

int par[MAX_V];

int find(int x){
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}


void compute(vector<Edge> edges){
  set<int> weights;
  rep(i,V) par[i] = i;
  sort(edges.begin(),edges.end());
  rep(i,E){
    Edge &e = edges[i];
    if( find(e.src) != find(e.dst) ) {
      unit(e.src,e.dst);
      weights.insert(e.w);
    }
  }
  int cnt=0,sum=0;
  int cur = 0;
  for(set<int>::iterator it=weights.begin();it!=weights.end();it++){
    int w = *it;
    while( cur < E && edges[cur].w < w ) ++cur;
    if( cur >= E ) break;
    if( edges[cur].w > w ) continue;
    base_weight = w;
    while( cur < E && edges[cur].w == w ) {
      Edge &e = edges[cur++];
      G[e.src].push_back((Edge){e.src,e.dst,e.w});
      G[e.dst].push_back((Edge){e.dst,e.src,e.w});
    }
    bridges.clear();
    calculateArticulationPointAndBridge();
    cnt += (int)bridges.size();
    sum += (int)bridges.size() * w;
  }
  printf("%d %d\n",cnt,sum);
}

int main(){
  memset(cost,-1,sizeof(cost));
  vector<Edge> edges;
  scanf("%d %d",&V,&E);
  {
    int s,t,w;
    rep(i,E){
      scanf(" %d %d %d",&s,&t,&w);
      --s, --t;
      edges.push_back((Edge){s,t,w});
      cost[s][t] = cost[t][s] = w;
    }
  }
  compute(edges);
  return 0;
}

2015-11-08

LiveArchieve 6804 : Group of Strangers

LiveArchive ICPC AdHoc

問題リンク:https://icpcarchive.ecs.baylor.edu/external/68/6804.pdf

問題概要：
無向グラフが与えられる
3点を選んだとき、それらの間に1本も辺が存在しないようなものの数を数えろ

解法:
公式解説の通り

コード:

#include<bits/stdc++.h>

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

using namespace std;

typedef long long ll;

const int MAX_V = 5010;
int V,E;
vector<int> G[MAX_V];
bool edge[MAX_V][MAX_V];
bool heavy[MAX_V];
int heavyV,heavy_vertex[MAX_V];
typedef pair<int,int> ii;

inline ll nC2(ll n) { return n * ( n - 1LL ) / 2LL; }

bool comp(int a,int b) {
  return (int)G[a].size() > (int)G[b].size();
}

void compute(){
  {
    heavyV = 0;
    int limit = sqrt(E);
    rep(i,V) if( (int)G[i].size() >= limit ) {
      heavy[i] = true;
      heavy_vertex[heavyV++] = i;
    }
  }
  rep(i,V) sort(G[i].begin(),G[i].end(),comp); //重要
  vector<int> dvec;
  rep(i,V) dvec.push_back(i); 
  sort(dvec.begin(),dvec.end(),comp); //重要
  // 3-edge triple
  ll three = 0;
  // heavy - heavy - heavy ( ( E**0.5 ) ** 3 )
  rep(i,heavyV) REP(j,i+1,heavyV) if( edge[heavy_vertex[i]][heavy_vertex[j]] ) {
    REP(k,j+1,heavyV) if( edge[heavy_vertex[i]][heavy_vertex[k]] && edge[heavy_vertex[j]][heavy_vertex[k]] ) {
      ++three;
    }
  }

  // 辺の端点a,bの両方がheavyでないような辺について考える　a < b とする これより、aがheavyならbもheavyなのでこれらは無視する　つまり、aはheavyではないため、E**0.5しかそのようなaは存在しない
  rep(i,V) if( !heavy[i] ) {
    int a = i;
    rep(j,(int)G[i].size()){
      int &b = G[i][j];
      if( (int)G[a].size() >  (int)G[b].size() ) break;
      if( (int)G[a].size() == (int)G[b].size() && a > b ) continue;

      rep(k,V){
        int c = dvec[k];
        if( (int)G[b].size() >  (int)G[c].size() ) break;
        if( (int)G[b].size() == (int)G[c].size() && b > c ) continue;
        if( c == a || c == b ) continue;
        if( edge[a][c] && edge[b][c] ) {
          ++three;
        }
      }
    }
  }

  //cout << "three = " << three << endl;

  // 2-edge triple
  ll two = 0;
  rep(i,V) if( (int)G[i].size() >= 2 ) {
    int degree = (int)G[i].size();
    two += nC2(degree);
  }
  two -= 3LL * three;
  
  //cout << "two = " << two << endl;

  // 1-edge triple
  ll one = 0;
  rep(i,V) if( (int)G[i].size() >= 1 ) {
    int degree = (int)G[i].size();
    one += (ll)degree * (ll)( V - degree - 1 );
  }
  one /= 2LL;
  one -= two;

  //cout << "one = " << one << endl;
  ll ans = ( ( (ll)V * (ll)(V-1) * (ll)(V-2) ) / 6LL ) - ( three + two + one );
  printf("%lld\n",ans);
  //cout << ( ( (ll)V * (ll)(V-1) * (ll)(V-2) ) / 6LL ) - ( three + two + one ) << endl;
}

int main(){
  int T,CNT=1;
  scanf("%d",&T);
  while( T-- ){
    rep(i,V) G[i].clear();
    memset(edge,false,sizeof(edge));
    memset(heavy,false,sizeof(heavy));
    scanf(" %d %d",&V,&E);
    int s,t;
    rep(i,E){
      scanf(" %d %d",&s,&t);
      --s, --t;
      G[s].push_back(t);
      G[t].push_back(s);
      edge[s][t] = edge[t][s] = true;
    }
    printf("Case #%d: ",CNT++);
    compute();
  }
  return 0;
}

土下座しながら探索中

主に競技プログラミング

Typical DP Contest C - トーナメント

Typical DP Contest B - ゲーム

Typical DP Contest A - コンテスト

ACM-ICPC 2015 Tsukuba Regional Contest : つくば大会参加記

LiveArchive 6582 : UVa 1642 : Magical GCD

AOJ 1350 : There is No Alternative

LiveArchieve 6804 : Group of Strangers