Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

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

問題概要

H*W (50*50以下) のグリッドを考える.
各グリッドは白か黒の色をしている.
問題文で与えられたプログラムを使って,色を塗り替える.
最終的に色がどうなったかが与えられるので,もともとの色はどうだったか,考えうるパターン数をmod 1000000007で求める問題.

解法

行ごとに独立して考えられる.
2行目を全部?という文字にしておいて,1行目を処理する.
2行目で?でなく,アウトプットの2行目と一致してない文字があれば,それは不可能.
そうでなければ,?でなくなった場所は,もともとWでもBでもよかったので, 2^?でなくなった数 だけのパターン数がある.

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

#define M 1000000007
#define ll long long

ll solve(string in, string out){
  int i,j,k,n=in.size();
  int chk[100];
  ll res=1;

  rep(i,n) chk[i]=-1;

  REP(i,1,n){
    if(in[i-1]=='B' && in[i]=='W') chk[i-1] = chk[i] = 'B';
    if(in[i-1]=='W' && in[i]=='B') chk[i-1] = chk[i] = 'W';
    if(in[i-1]=='B' && in[i]=='B') swap(chk[i-1],chk[i]);
  }

  rep(i,n) if(chk[i]>=0 && out[i]!=chk[i]) return 0;
  rep(i,n) if(chk[i]>=0) res = (res*2)%M;
  
  return res;
}

class AlgridTwo {
public:
int makeProgram(vector <string> output) {
  int i;
  ll res=1, tmp;
  string in,out;

  REP(i,1,output.size()){
    tmp = solve(output[i-1],output[i]);
    res = (res*tmp)%M;
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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