結果

問題 No.2278 Time Bomb Game 2
ユーザー cho435cho435
提出日時 2023-04-21 23:31:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,513 bytes
コンパイル時間 2,032 ms
コンパイル使用メモリ 204,564 KB
最終ジャッジ日時 2025-02-12 12:37:01
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 52 WA * 3 TLE * 14 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for (int i=0;i<(int)(n);i++)

int n;
string s;
vector<int> sl(2e5,-1);
vector<int> sr(2e5,-1);
int dfs(int nk,int nt){
  if(nt==0) return 0;
  int sz=sr.at(nk)-sl.at(nk);
  if(sz<=nt&&sz%2==0) return 1;
  if(sz==1){
    int rt=0;
    int enflg=1;
    if(nk>0){
      if(sr.at(nk-1)-sl.at(nk-1)!=1) enflg=0;
    }
    if(nk<n-1){
      if(sr.at(nk+1)-sl.at(nk+1)!=1) enflg=0;
    }
    if(enflg&&nt%2==0) return 0;
    if(nk>0){
      rt|=1^dfs(nk-1,nt-1);
    }
    if(nk<n-1){
      rt|=1^dfs(nk+1,nt-1);
    }
    return rt;
  }
  int rt=0;
  if(sl.at(nk)!=0){
    int df=nt-(nk-sl.at(nk));
    if(df>0){
      df=(df+1)%2;
      rt|=1^dfs(sl.at(nk)-1,df);
    }
  }
  if(sr.at(nk)!=n){
    int df=nt-(sr.at(nk)-nk-1);
    if(df>0){
      df=(df+1)%2;
      rt|=1^dfs(sr.at(nk),df);
    }
  }
  return rt;
}

int main(){
  int k,t;
  cin>>n>>k>>t;
  k--;
  string s;
  cin>>s;
  {
    sl.at(0)=0;
    rep(i,n-1){
      if(s.at(i)==s.at(i+1)){
        sl.at(i+1)=sl.at(i);
      }else{
        sl.at(i+1)=i+1;
      }
    }
    reverse(s.begin(),s.end());
    sr.at(0)=n;
    rep(i,n-1){
      if(s.at(i)==s.at(i+1)){
        sr.at(i+1)=sr.at(i);
      }else{
        sr.at(i+1)=n-i-1;
      }
    }
    reverse(s.begin(),s.end());
    reverse(sr.begin(),sr.begin()+n);
  }
  map<char,string> mp={{'A',"Alice"},{'B',"Bob"}};
  char rv='A'^'B'^s.at(k);
  if(dfs(k,t)) cout<<mp.at(s.at(k))<<endl;
  else cout<<mp.at(rv)<<endl;
}
0