Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM530 DIV1 MEDIUM - GogoXMarisaKirisima/DIV2 HARD - GogoXReimuHakurai (この記事を編集する[管理者用])

Source

TopCoder SRM530 DIV1 MEDIUM (500pt)
TopCoder SRM530 DIV2 HARD (1000pt)
Problem Statement (DIV1)
Problem Statement (DIV2)

問題概要

ノード数N (50以下) の有向グラフが与えられる.
自分に枝が張られていたり,同じノード間に2本枝があったりはしない.
ノード0からノードN-1に移動するのを,以下の方法で繰り返すとき,最大で何回ノード0からノードN-1に移動できるかを求める問題.
 ノード0からノードN-1に行くのに,今まで使ったことのない枝を少なくても1個通らなければいけない.
 (そのパスの途中にノードN-1を含んでも良い)
 ノードN-1についたら,枝を使わず,ノード0にジャンプできる.
DIV2の場合のみ,グラフはDAGで,ノードiからノードjに枝があるならi < jでなければならない.

解法

使えるノードをノード0,N-1以外で,ノード0からノードN-1に移動する際に通ることのできるものとする.
同様に使える枝を,ノード0からノードN-1に移動する際に通ることのできるものとする.
すると答えは,
 使える枝数 - 使えるノード数
になる.
なぜなら,ノード0,N-1以外で新しいノードにたどり着いたときは,そのノードに来るとき使った枝,出ていくときに使った枝,2本消費してしまう.
そうでなければ,すでにたどり着いてるノードからは,今まで使った枝のみで0から来れ,N-1にいけるので,枝の消費1本で1回だけN-1まで移動できるから.
(DIV1もDIV2も解答はこの方針は同じ)

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

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

class GogoXMarisaKirisima {
public:
int solve(vector <string> choices) {
  int i,j,k,n;
  int edge[51][51];
  int valid_node = 0, valid_edge = 0;

  n = choices.size();
  rep(i,n) rep(j,n){
    if(choices[i][j] == 'Y') edge[i][j] = 1;
    else                     edge[i][j] = 0;
  }
  rep(i,n) edge[i][i] = 1;

  rep(k,n) rep(i,n) rep(j,n) edge[i][j] |= (edge[i][k]&edge[k][j]);
  if( !edge[0][n-1] ) return 0;

  REP(i,1,n-1) if(edge[0][i] && edge[i][n-1]) valid_node++;

  rep(i,n) rep(j,n) if(choices[i][j]=='Y'){
    if(edge[0][i] && edge[j][n-1]) valid_edge++;
  }
  
  return valid_edge - valid_node;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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