Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM495 DIV1 EASY (275pt)
TopCoder SRM495 DIV2 MEDIUM (525pt)
Problem Statement
SRM495 DIV1 自分の参加記録

問題概要

1~Nまで (Nは1000以下) の数字が書かれたカードが1枚ずつあり,素数だと背景が赤,そうでなければ背景が青.
今,K枚 (50以下) のカードが,裏向きに置いてある.そのカードは左から小さい順に置いてあることが保証されている.
カードの色だけが与えられたとき,各カードに対して,特定できるならその数字を,できないなら-1を返す問題.

解法

それぞれのカードの取りうる最小値を左から決めていく.
同様に,それぞれのカードの取りうる最大値を右から決めていく.
最小値と最大値が一致したカードのみ一意に定まる.

以下のコードは,それぞれのカードについて,それぞれの数字が取りうるかどうか全て判定している.
判定方法は,そのカードより左のカードの最大値をgreedyに決めていって,全てvalidな値が存在して,同様に右も最小値をgreedyに割り当てていってvalidな値が全部存在すれば良い.

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 getPrime(int n,int p[]){int i,j,n2=n/2;rep(i,n2)p[i]=1;for(i=3;i*i<n;i+=2)if(p[i>>1])for(j=(i*i)>>1;j<n2;j+=i)p[j]=0;j=1;p[0]=2;REP(i,1,n2)if(p[i])p[j++]=i*2+1;return j;}

int ps, p[1200];
int prime[1200];

class ColorfulCards {
public:
vector <int> theCards(int mx, string in) {
  int i,j,k,n,st,go,dame;
  vector <int> res;
  int ok[1200];

  ps = getPrime(1200,p);
  rep(i,1200) prime[i]=0;
  rep(i,ps) prime[p[i]]=1;

  n=in.size();
  rep(i,n) if(in[i]=='R') in[i]=1; else in[i]=0;
  
  rep(st,n){
    rep(i,mx+1) ok[i]=0;

    REP(i,1,mx+1) if(in[st] == prime[i]){
      j=i-1; dame=0;
      for(go=st-1;go>=0;go--){
        while(j>=1 && in[go]!=prime[j]) j--;
        if(j<1){ dame=1; break; }
        j--;
      }
      if(dame) continue;

      j=i+1; dame=0;
      for(go=st+1;go<n;go++){
        while(j<=mx && in[go]!=prime[j]) j++;
        if(j>mx){ dame=1; break; }
        j++;
      }
      if(dame) continue;

      ok[i]=1;
    }

    k=0;
    rep(i,mx+1) if(ok[i]) k++;
    if(k!=1){ res.push_back(-1); continue; }
    rep(i,mx+1) if(ok[i]) res.push_back(i);
  }

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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