Official

E - カードバトル / Card Battle Editorial by kyopro_friends

高橋君は青木君の行動を知っており、両者の行動が終わってから勝敗判定が行われるため、青木君が常に先に行動するとしてもゲームの進行は変わりません。青木君のそのターンの行動が終わった時点のことを「高橋君の行動時」と呼ぶことにします。

高橋君はターン終了時のエネルギーが 0 以下の場合勝利できないため、高橋君の行動時の高橋くんのエネルギーが 1 の場合、アタックすることはできません。エネルギーが 2 以上のとき、必ずアタックするとして損をしません。

証明 ターン $i$ における高橋君の行動時、高橋君のエネルギーが2以上あるとする。 ①このターンにアタックすることで勝利できる場合
明らかにアタックするのが最適である
②このターンにアタックしても勝利できない場合
②(1)ターン $i$ より後、ターン $j$ で勝利するまでにアタックをしなかった場合
仮定より $j>i$ である。 ターン $j-1$ の高橋君の行動時に高橋君のエネルギーは 2 以上あり、かつ、青木君のエネルギーは 1 なので、ターン $j-1$ の行動をアタックに変更することで 1 ターン早く勝利することができる。
②(2)ターン $i$ より後、初めて攻撃するのがターン $j$ であるとき
ターン $i$ 以降ターン $j$ より前の全てのターンについて、ターン終了時の高橋君のエネルギーは 3 以上ある。よって、ターン $i$ の行動をアタック、ターン $j$ の行動をチャージに変更することができる（この間のターン終了時の高橋君のエネルギーは 1 以上になる）。また、このときターン $j$ 以降の互いのエネルギーは元と一致するので、この変更により損をしない。

よって、先頭から順にシミュレーションをすることで \(O(T)\) でこの問題を解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int takahashi, aoki, turn;
  cin >> takahashi >> aoki >> turn;
  string s;
  cin >> s;
  
  for(int i=0; i<turn; i++){
    if(s[i] == 'C'){
      aoki++;
    }else{
      aoki--;
      takahashi--;
    }
    if(takahashi <= 1){
      takahashi++;
    }else{
      takahashi--;
      aoki--;
    }
    if(aoki <= 0){
      cout << i+1 << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

実装例 (Python)

takahashi, aoki, _ = map(int, input().split())
S = input()

for i, c in enumerate(S):
  if c == 'C':
    aoki += 1
  else:
    aoki -= 1
    takahashi -= 1
  if takahashi <= 1:
    takahashi += 1
  else:
    takahashi -= 1
    aoki -= 1
  if aoki <= 0:
    print(i+1)
    exit()
print(-1)

posted:
last update: