Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

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

Source

TopCoder SRM526 DIV1 MEDIUM (500pt)
Problem Statement

問題概要

2人でゲームを行う.打つ手がなくなったら負け.
それぞれ,勝てるなら最短ターンで勝つ,負けるなら最長ターンで負けようと動く.
ゲームは,何ターンでどちらの勝利で終わるかを求める問題.
最初数字 N (474747以下) が書かれている.
その数字を1以上K以下引いた数字に書き換える.(KはN以下)
ただし,書き換える数字は,先手は素数,後手は合成数になるように書き換えなければいけない.

解法

Mをとても大きい数字として,Kターンで勝てる状態をM-K,Kターンで負ける状態をKとする.
すると,状態遷移先の最小値を見つければ良い.
seg treeやヒープなどを使えばlog Nかlog Kで見つけることができる.(seg tree使うと結構時間ぎりぎりになる)
greedy解もあるが,難しい.(勝つ側は出来るだけ多く減らし,負ける側は少なく減らす.向かう場所は3か合成数がたくさん連続している場所.細かい部分で色々注意)
素数の最大の幅は120程度で,それを超えるときgreedyで,それ以下の時,愚直なO(NK)のDPという方法もあるらしい.

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 M 1000000000

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, pr[500000], isp[500000];

int dp[2][500000];
set<pair<int,int> > s[2];

class PrimeCompositeGame {
public:
int theOutcome(int N, int K) {
  int i,j,k;
  int now, next, go;
  int res;

  ps = getPrime(500000, pr);
  rep(i,500000) isp[i] = 0;
  rep(i,ps) isp[pr[i]]=1;

  s[0].clear(); s[1].clear();

  REP(i,2,N){
    now  = isp[i];
    next = 1-now;
    
    dp[next][i] = M;

    go = M;
//    REP(k,1,K+1) if(i-k >= 2 && go > dp[next][i-k]) go = dp[next][i-k];  これを高速にやりたい
    while(s[next].size()){
      pair<int,int> t = *s[next].begin();
      if(t.second < i-K){
        s[next].erase(s[next].begin());
        continue;
      }
      go = t.first;
      break;
    }
    
    if(go > M/2) dp[now][i] = (M-go) + 1;
    else         dp[now][i] = M - (go+1);

    rep(k,2) s[k].insert( make_pair(dp[k][i], i) );
  }

  go = M;
  REP(k,1,K+1) if(N-k >= 2 && go > dp[1][N-k]) go = dp[1][N-k];

  if(go > M/2) res = -(M-go);
  else         res = go;

  return res;
}

};

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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