Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM504 DIV1 EASY (250pt)
TopCoder SRM504 DIV2 MEDIUM (500pt)
Problem Statement
SRM504 DIV1 自分の参加記録

問題概要

BとWのみからなる100000文字以下の文字列が与えられる.
先頭の文字を削除して,
 それがBだったら,残りの文字列の全てのBをWに変えて,WをBに変える
 それがWだったら,残りの文字列を左右反転させる
文字列がなくなるまで行うとき,Bを削除した回数を求める問題.

解法

文字列の処理を行わずにシミュレーションする.
削除されたBの数が奇数なら,先頭の文字を反転して考える.
削除されたWの数が奇数なら,後ろを先頭と考える.
とすると,O(長さ)でシミュレーションできる.

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

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

char in[1000000]; int st, len;

class MathContest {
public:
int countBlack(string ball, int repetitions) {
  int i,j,k;
  int w=0, b=0;
  int next;

  st=0; len=0;
  rep(i,repetitions) rep(j,ball.size()) in[len++] = ball[j];

  while(len){
    if(w%2==0){
      next = in[st]; st++; len--;
    } else {
      next = in[st+len-1]; len--;
    }

    if( (b%2==0 && next=='W') || (b%2==1 && next=='B') ){
      w++;
    } else {
      b++;
    }
  }

  return b;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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