Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2161-26742c23
この記事にトラックバックする(FC2ブログユーザー)

SRM523 DIV1 HARD - AlphabetPaths (この記事を編集する[管理者用])

Source

TopCoder SRM523 DIV1 HARD (900pt)
Problem Statement

問題概要

幅21以下,高さ21以下のグリッドが与えられ,各セルは空白かアルファベット一文字が書かれている.
この問題においては登場するアルファベットは
 A B C D E F Z H I K L M N O P Q R S T V X
の21種類のみを考える.
上下左右に隣接しているとして,グリッド上の長さ21のパスで,全てのアルファベットが1回ずつ出現するものは何パターンあるかを求める問題.

解法

11番目に訪れるセルがどこかで21*21パターン全探索する.
そこから,10マス移動する経路を全列挙し,ちょうど,全て異なる文字を踏んだ組に対して,その数の積を答えに加えていく.
移動する際,後戻りはしないので,大体,O(21^2*3^10)程度でできる.自分はソート使ったのでもう1個logがかかっているが最悪ケースで1秒程度だった.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long

int x, y, mp[33][33], in[33][33];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

int fin[200000], fin_num[200000], fin_size;

void dfs(int a, int b, int step, int mask){
  int na, nb, k;

  if(step==10){
    fin[fin_size++] = mask;
    return;
  }

  rep(k,4){
    na = a + dx[k];
    nb = b + dy[k];
    if(na<0 || nb<0 || na>=x || nb>=y || in[na][nb]<0) continue;
    if(mask & 1<<in[na][nb]) continue;
    dfs(na, nb, step+1, mask|(1<<in[na][nb]));
  }
}

ll solve(int a, int b){
  int i,j,k;
  ll res = 0;

  k = mp[a][b];

  rep(i,x) rep(j,y){
    in[i][j] = mp[i][j];
    if(mp[i][j] <  0) continue;
    if(mp[i][j] == k){ in[i][j] = -1; continue; }
    if(in[i][j] >  k) in[i][j]--;
  }

  fin_size = 0;
  dfs(a,b,0,0);

  if(!fin_size) return 0;

  sort(fin, fin+fin_size);
  k = 1;
  fin_num[0] = 1;
  REP(i,1,fin_size){
    if(fin[k-1] == fin[i]){ fin_num[k-1]++; continue; }
    fin[k] = fin[i];
    fin_num[k] = 1;
    k++;
  }
  fin_size = k;

  j = fin_size-1;
  rep(i,fin_size){
    while( j >= 0 && fin[i]+fin[j] > (1<<20)-1 ) j--;
    if(j < 0) break;
    if(fin[i] + fin[j] == (1<<20)-1) res += (ll)fin_num[i]*fin_num[j];
  }

  return res;
}

class AlphabetPaths {
public:
ll count(vector <string> letterMaze) {
  int i,j,k;
  ll res = 0;
  char *letter = "ABCDEFZHIKLMNOPQRSTVX";

  x = letterMaze.size();
  y = letterMaze[0].size();

  rep(i,x) rep(j,y){
    if(letterMaze[i][j]=='.'){ mp[i][j] = -1; continue; }
    rep(k,21) if(letterMaze[i][j]==letter[k]) break;
    mp[i][j] = k;
  }

  rep(i,x) rep(j,y) if(mp[i][j] >= 0){
    res += solve(i, j);
  }

  return res;
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2161-26742c23
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。