Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM586 DIV1 MEDIUM - History (この記事を編集する[管理者用])

Source

TopCoder SRM586 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

$K$ 個の国がある.($K \leq 26$)
各国は1年は同じ長さで,同じタイミングに都市が始まるが,基準となる年が異なる.(A国の第71年目はB国の第91年目かもしれない)
各国は,それぞれ10人以下の王様がいて,王様の任期はある年の始まりから,ある年の終わりまで.
王様の任期が何年に始まって,何年に終わったかというリストが,その国の年の数え方で与えられる.
過去戦争が起こった記録が,どの国のどの王様と,どの国のどの王様とが戦ったか,という記録のリストが与えられる.
戦争は,1年以内に終わり,年をまたぐことはない.
クエリが50個以下与えられるので,それぞれのクエリに答える問題.
各クエリでは,異なる国の王様の名前が2つ与えられるので,その2つ王様が同時に王様になっていた時期がある可能性があるかどうかを求める.

解法

各国同士の年の数え方がどのぐらいずれている可能性があるか,その最大値と最小値を更新していく.
それは,最短路問題に帰着されるので,ワーシャルフロイドなどで計算できる.
あとは,各クエリに答えるだけ.

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 INF 1000000000

int read_int_from_char(const char in[],int l,int ret[]){
  int i,n,fg,mfg;
  if(l<0) {for(i=0;;i++) if(in[i]<' ') break; l=i;}
  n=0; fg=0; mfg=0; ret[0]=0;
  rep(i,l+1){
    if(in[i]=='-'){mfg=1; continue;}
    if(isdigit(in[i])){ret[n]=ret[n]*10+in[i]-'0'; fg=1; continue;}
    if(!fg) continue;
    fg=0; if(mfg){ret[n]=-ret[n]; mfg=0;}
    ret[++n]=0;
  }
  return n;
}

class History {
public:
string verifyClaims(vector <string> dynasties, vector <string> battle_baka, vector <string> queries) {
  int i, j, k, n;
  int a, b, aa, bb;
  int ast, aed, bst, bed;
  int yr[40][40], yr_sz[40];
  int maxd[30][30], mind[30][30];
  string battle = "", bt;
  string res = "";

  rep(i,battle_baka.size()) battle += battle_baka[i];

  n = dynasties.size();
  rep(i,n){
    yr_sz[i] = read_int_from_char(dynasties[i].c_str(), -1, yr[i]) - 1;
  }

  rep(i,n) rep(j,n) maxd[i][j] = INF, mind[i][j] = -INF;
  rep(i,n) maxd[i][i] = mind[i][i] = 0;

  stringstream ss(battle);
  while(ss >> bt){
    a = bt[0] - 'A';
    aa = atoi(bt.c_str() + 1);
    for(i=0;;i++) if(bt[i]=='-') break;
    b = bt[i+1] - 'A';
    bb = atoi(bt.c_str() + i+2);

    ast = yr[a][aa]; aed = yr[a][aa+1]-1;
    bst = yr[b][bb]; bed = yr[b][bb+1]-1;

    mind[a][b] = max(mind[a][b], bst-aed);
    maxd[a][b] = min(maxd[a][b], bed-ast);
    
    ast = yr[b][bb]; aed = yr[b][bb+1]-1;
    bst = yr[a][aa]; bed = yr[a][aa+1]-1;

    mind[b][a] = max(mind[b][a], bst-aed);
    maxd[b][a] = min(maxd[b][a], bed-ast);
  }

//  rep(i,n) rep(j,n) printf("%d %d : mn %d mx %d\n",i,j,mind[i][j],maxd[i][j]);

  rep(k,n) rep(i,n) rep(j,n) if(mind[i][j] < mind[i][k]+mind[k][j]) mind[i][j] = mind[i][k]+mind[k][j];
  rep(k,n) rep(i,n) rep(j,n) if(maxd[i][j] > maxd[i][k]+maxd[k][j]) maxd[i][j] = maxd[i][k]+maxd[k][j];

  rep(k,queries.size()){
    string bt = queries[k];
    a = bt[0] - 'A';
    aa = atoi(bt.c_str() + 1);
    for(i=0;;i++) if(bt[i]=='-') break;
    b = bt[i+1] - 'A';
    bb = atoi(bt.c_str() + i+2);

    ast = yr[a][aa]; aed = yr[a][aa+1]-1;
    bst = yr[b][bb]; bed = yr[b][bb+1]-1;

    ast += mind[a][b];
    aed += maxd[a][b];
    if(bed < ast || bst > aed) res += "N"; else res += "Y";
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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