読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

SRM 701 Div1

0完でした。

ずっとEasyを考えていて思いついたのが終了五分前だった(しかも嘘。


方針
勝てる数or勝てる数に必ずできる数ならAlice、
そうでなければBob

変化量は2~10なのでAliceがその変化量に必ず調整できるかを判定する

n%i(2<=i<=10)が勝てる数かどうかを判定する。

コーナーケース
複数の数を組み合わせなければいけない場合に落ちる

コインDPしようかとも思ったけどn<10^9なので無理。
多分ここからは解けなくはないはず。

以下WAのソース

#include <bits/stdc++.h>
using namespace std;
class PartisanGame {
public:
string getWinner(int n, vector <int> a, vector <int> b) {
  bool f,ff;
  int i,j,k,m=5;
  bool ok[12]={};
  for(i=2;i<11;i++){
    ok[i]=true;
    for(j=0;j<b.size();j++){
      ff=false;
      for(k=0;k<a.size();k++){
	ff|=(b[j]+a[k]==i);
      }
      ok[i]&=ff;
    }
  }
  f=false;
  for(k=0;k<=5;k++){
    ff=false;
    for(i=0;i<b.size();i++) ff|=(k==b[i]);
    if(ff) continue;
    for(i=2;i<11;i++){
      if(!ok[i]) continue;
      for(j=0;j<a.size();j++){
	if((n-k)%i==a[j]){
	  f=true;
	}
      }
    }
    for(j=0;j<a.size();j++){
      if(n-k==a[j]){
	f=true;
      }
    }
  }
  return f?"Alice":"Bob";
}

時間があるときに解き直したい(ゲーム問題は蓄積が足りてない感
周期でやる方法は思いつかなかったのでそのうち書くかも。

結果
1339->1085

Div2落ちです。
戻ってこれるように頑張ります。(未完)