UTPC2010 - しおしおたのブログ

UTPCに参加してきました。

３８位でした。
レベルの高い参加者の中では頑張ったとおもいます、が、！

まだ、もしかしたら２問くらいはうまくいけば解けたかもしれないのでくやしいです。

結果と問題。

http://www.utpc.jp/2010/standings.html
http://m-judge.maximum.vc/problem_list.cgi?top=10122&btm=10133

以下問題について

どう見てもけいおん！
４分でAC

Oh、宝くじ。
そういえば最近買ったのが外れました。
stringで処理して、１５分でAC

ぷよぷよ。
ちょっとめんどくさい、飛ばそう。

うぬぬぬ？
Name the crossing
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1134&lang=jp
に重みがついて、でも、簡単になった感じ？
どっちにしろ、手元でグラフ書いてみる。
サンプルすべてグラフで解決しそう。
よし、書こう。
エッジ一本一本追加しながら、グラフのコストと入力のコストが矛盾ないか調べてみよう。
コストの出し方はDFSでいっか。
サンプルでた！
提出。
TLE。
DFSでvisited管理してなかった。直して提出。
AC。45分かかっちゃった。
ソース

#include<iostream>
#include<string>
#include<map>
#include<algorithm>

#define INF 100000000

using namespace std;

int d;

bool visited[201];
int edge[201][201];
bool findf;

void dfs(int now, int cost, int to){
  if(now == to){
    d = cost;
    findf = true;
  }
  for(int i=0; i<201; i++){
    if(edge[now][i] != INF && !visited[i]){
      visited[i] = true;
      dfs(i, cost + edge[now][i], to);
      if(findf)return;
      // visited[i] = false;
    }
  }
}

main(){

  int n;

  cin >> n;

  map<string, int> index;
  int cnt=1;

  fill(&edge[0][0], &edge[200][201], INF);
  
  bool flag = true;

  for(int i=0; i<n; i++){
    int tmp, cost;
    string from, to;
    char c;

    cin >> tmp >> to >> c >> tmp >> c >> cost >> from;

    if(index[to] == 0){
      index[to] = cnt;
      cnt++;
    }
    if(index[from] == 0){
      index[from] = cnt;
      cnt++;
    }
    d = INF;

    fill(visited, visited + 201, false);

    visited[index[from]] = true;

    findf = false;

    dfs(index[from],0, index[to]);



    if(d != INF && d != cost){
      flag = false;
    }			     
    edge[index[from]][index[to]] = cost;
    edge[index[to]][index[from]] = -1 * cost;
  }

  if(flag){
    cout << "Yes" << endl;
  }

  else cout << "No" << endl;
}

よし、Cを解こう。
ぷよぷよ。
ごりごり。
結果があわない。
出力してみると、どうやら、ブロックを下にずらすところが全然だめだめだった。
swapしまくる戦法！
でた！
AC

ほかにもいろいろバグあってめっちゃ時間かかった。

１時間ちょっとですね。

ソース

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

string m[12];
bool visited[12][6], melt, flag;
int tx[] = {-1, 1, 0, 0}, ty[] = {0, 0, 1, -1}, cost;

void dfs(int y, int x){
  cost++;
  visited[y][x] = true;
  if(cost>=4){
    flag = true;
    melt = true;
  }
  for(int i=0; i<4; i++){
    int nx = x + tx[i];
    int ny = y + ty[i];
    if(nx < 0 || ny < 0 || ny >=12 || nx >=6){
      continue;
    }
    if(m[y][x] == m[ny][nx] && !visited[ny][nx]){
      dfs(ny, nx);
    }
    if(m[ny][nx] == 'O'){
      visited[ny][nx] = true;
    }
  }
}


main(){

  for(int i=0; i<12; i++){
    cin >> m[i];
  }

  int cnt = 0;
  while(1){
    flag = false;
    for(int i=0; i<12; i++){
      for(int j=0; j<6; j++){
	melt = false;
	if(m[i][j] == '.'  || m[i][j] == 'O'){
	  continue;
	}
	cost = 0;
	fill(&visited[0][0], &visited[11][6], false);
	dfs(i, j);
	if(!melt){
	  continue;
	}
	for(int k=0; k<6; k++){
	  for(int l=0; l<12; l++){
	    if(visited[l][k]){
	      m[l][k] = '.';
	    }
	  }
	}
      }
    }
    for(int k=0; k<6; k++){
      for(int i=0; i<12; i++){
	for(int l=11; l>0; l--){
	  if(m[l][k] == '.'){
	    swap(m[l][k], m[l-1][k]);
	  }
	}
      }
    }   
    if(!flag){
      cout << cnt << endl;
      break;
    }
    cnt++;
  }
}

こういう問題みてあんまりヤル気になれないなぁ。

DPの香りが！
絶対DP！

でも出ない。

なんで？

最後のサンプルケースがどうしてもでない。

時間終了。

あとから、@matyaa　先輩に聞いてみたところ、ｙのところにひとつも１が入らなかった場合、
ｙのところがすべて０になる場合を除くから、２^(不確定なｙの数）- 1　になるらしい。
なるほど！そうか。

2^(不確定なyの数 -1)にしてた。
１にするためのyを固定してしまってた。

感想

やっぱり、コンテストはとてもたのしいです。とくに、ツイッターで話題になってたのでなんか一体感があってとても楽しかったです。