解決
Aは先手時津風、Bは後手クォイルティと覚えておいた方が良いでしょう。覚えて \(f(X)\) のために \(X\) この人の最終状態 (それぞれ勝ち、引き分け、負け) は次のとおりです。 \(1,0,-1\)）。
まず、オール０とオール１の状況を具体的に判定する。
文字列の最初の 0 が \(l_0\)最後の0は入っています \(r_0\)、\(l_1,r_1\) 同じ理由です。
まず、より日常的な状況を判断します。もし \(r_0-l_0+1\le k\) または \(r_1-l_1+1\le k\) そうすればAは一手で勝つことができます。そして、Aが何をしてもBが一歩で勝てる状況を判断します。
この時点で2手以内では絶対に勝負は終わらない。 B 少なくともAの操作を繰り返して、操作後も状況が変わらないようにします。あと一歩では勝てない状態が A に戻されるため、ゲームは無限に進み、引き分けになります。 \(f(B)\ge 0\)。同様に、先行者もこれを行うことができます \(f(A)\ge 0\)。そしてゼロサムゲームのせいで \(f(A)+f(B)=0\)結局は引き分けしかない。
コード
#include
using namespace std;
int n,k;
string s;
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n>>k>>s;
if(s[0]=='1') for(char &c:s) c^=1; // 令s[0]='0'
// 特判全0/全1
if(s.find('0')==s.npos||s.find('1')==s.npos){
cout<<"tokitsukaze\n";
return 0;
}
int l0=s.find('0'),r0=s.rfind('0');
int l1=s.find('1'),r1=s.rfind('1');
// A一步取胜
if(r0-l0+1<=k||r1-l1+1<=k){
cout<<"tokitsukaze\n";
return 0;
}
// A无论如何操作后B都能一步取胜
if(r0min(r0-l0+1,r1-l1+1)&&n-k=n-1){
cout<<"quailty\n";
return 0;
}
}
if(l0l1){ // 0001...0111
int bound=max(r0-l0-1,r1-l1-1);
if(k>bound){
cout<<"quailty\n";
return 0;
}
}
// 平局
cout<<"once again\n";
return 0;
}
