Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

SRM493 DIV1 EASY/DIV2 MEDIUM - StonesGame (この記事を編集する[管理者用])

Source

TopCoder SRM493 DIV1 EASY (300pt)
TopCoder SRM493 DIV2 MEDIUM (600pt)
Problem Statement
SRM493 DIV1 自分の参加記録

問題概要

N個 (10^6以下) の石が一直線に並んでいる.
左からM番目の石のみ白くて,他は黒い.
2人でゲームをする.順番にターンが回ってくる.
毎ターン,白い石を含むように連続するK個の石を選び,順番をひっくり返し,白い石を左からL番目に移動した人の勝ち.
先手必勝か,後手必勝か,永遠に長引かせられるか,を判定する問題.

解法

全ての手は可逆なので,後手は順番が回ってきて勝てないなら,先手の手を打ち消すことで引き分けに持ち込める.
よって,
 1手でMからLに移動できるなら先手の勝ち
 先手がどう動かそうが,次にLに移動可能なら後手の勝ち
 そうでなければ引き分け

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

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

int is_can(int N, int S, int K, int G){
  int in, rest;

  if(S>G) in=S, S=G, G=in;
  in = G-S+1;

  rest = K - in;
  if(rest<0 || rest%2) return 0;

  rest /= 2;
  if(rest > S || rest > N-G-1) return 0;
  return 1;
}

class StonesGame {
public:
string winner(int N, int S, int K, int G) {
  int i, fg=0;

  S--; G--;

  if(is_can(N,S,K,G)) return "Romeo";
  rep(i,N) if(is_can(N,S,K,i)){
    if(is_can(N,i,K,G) == 0){ fg=1; break; }
  }

  if(!fg) return "Strangelet";
  return "Draw";
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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