Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM300 DIV2 HARD - CircleOrder (この記事を編集する[管理者用])

Source

TopCoder SRM300 DIV2 HARD (1000pt)
Problem Statement

問題概要

円の形をした道路がある.
その上に,$25$台以下の車(アルファベット小文字)と,それぞれの車の目的地(対応するアルファベット大文字)が与えられる.
車は$1$台ずつ動かし,途中で立ち止まらず,目的場所に移動する.
車はすれ違うことはできない.
どの順番で動かせば,全ての車が目的地に辿り着けるか,その順番の中で辞書順最小のものを求める問題.
不可能であるなら,それを指摘する.

解法

まず,全ての車が目的地に辿り着ける必要条件(必要十分ではない!)は
 与えられた文字列から小文字だけ抜き出した文字列を$S$
 与えられた文字列から大文字だけ抜き出した文字列を$T$
としたとき,$S$か$T$を適当に回転(頭から数文字をお尻にくっつける)したとき一致すること.
このときだけ考えると,車はすれ違わないので,どの車から動かしても,他の車が目的地に辿りつけなくなるようなことはない.
(逆に,ある車が目的地にたどり着いた後でないと,動かせない車はある)
なので,greedyに動かせる車のうち,アルファベット順で最も早い車から動かしていって,最終的に全部の車が辿り着けるかどうか調べれば良い.

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 is_can_move(string circle, char a){
  int i, j, k;
  char A = a + 'A' - 'a';
  
  rep(i,circle.size()) if(circle[i]==a) break;
  if(i == circle.size()) return 0;
  rep(j,circle.size()) if(circle[j]==A) break;

  for(k=(i+1)%circle.size();k!=j;k=(k+1)%circle.size())
    if(circle[k]=='#' || ('a'<=circle[k]&&circle[k]<='z')) break;
  if(k==j) return 1;
  
  for(k=(i+circle.size()-1)%circle.size();k!=j;k=(k+circle.size()-1)%circle.size())
    if(circle[k]=='#' || ('a'<=circle[k]&&circle[k]<='z')) break;
  if(k==j) return 1;

  return 0;
}

class CircleOrder {
public:
string firstOrder(string circle) {
  int i, j, k;
  string res;

  for(;;){
    REP(i,'a','z'+1) if(is_can_move(circle, i)) break;
    if(i > 'z') break;
    res += (char)i;

    rep(k,circle.size()){
      if(circle[k]==i) circle[k] = '-';
      if(circle[k]==i+'A'-'a') circle[k] = '#';
    }
  }

  if(res.size() != circle.size()/2) return "NONE";
  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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