AtCoderログ：0023 - ABC 210 B

問題：ABC 210 B - Bouzu Mekuri

問題文

$N$ 枚のカードからなる山札があります。
それぞれのカードは、「良いカード」か「悪いカード」かのどちらかです。
高橋君と青木君は、この山札を使って対戦ゲームをします。
このゲームでは、$2$ 人は交互に山札の一番上のカードを引いて、そのカードを食べます。
先に悪いカードを食べたプレイヤーの負けです。（ここで、山札には少なくとも $1$ 枚の悪いカードが含まれていることが保証されます。）
0 と 1 からなる文字列 $S$ が与えられます。$i=1,2,\ldots,N$ について、
・$S$ の $i$ 文字目が 0 のとき、山札の上から $i$ 番目のカードが良いカードであることを表します。
・$S$ の $i$ 文字目が 1 のとき、山札の上から $i$ 番目のカードが悪いカードであることを表します。
高橋君が先手でゲームを始めるとき、高橋君と青木君のどちらが負けるかを答えてください

制約

・$1 \le N \le 10^5$
・$N$ は整数
・$S$ は 0 と 1 からなる長さ $N$ の文字列
・$S$ は少なくとも $1$ 個の 1 を含む。

回答1 (AC)

対戦ゲームのルールは、カードを交互にめくり、最初に悪いカードをめくった方が負けるというものです。なので、文字列 s で最初に 1 が現れるときのインデックスを調べれば良いでしょう。コードは以下のようになりました。コードではインデックスが 0 から始まるため、インデックスが偶数なら高橋君、インデックスが奇数なら青木君の順番となることに注意が必要です。

abc210b-1.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;

  int index = 0;
  while ( s.at(index)!='1' ) {
    index += 1;
  }

  if ( index%2==0 ) {
    cout << "Takahashi" << endl;
  } else {
    cout << "Aoki" << endl;
  }
}

回答2 (AC)

回答1のポイントは「文字列の最初の 1 のインデックスを求める」ことでした。文字列に対する find 関数を利用すると、このようなインデックスを簡単に求めることが出来ます。コードは以下のようになりました。私が提出したコードではこの方針を使用しました。

abc210b-2.cpp

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
 
  int index = s.find('1');
  if ( index%2==0 ) {
    cout << "Takahashi" << endl;
  } else {
    cout << "Aoki" << endl;
  }
}

調べたこと

AtCoder の解説 → 公式解説

for 文を使ったコーディングが紹介されていました。

リンク

• 前の記事 → AtCoderログ：0022 - ABC 210 A
• 次の記事 → AtCoderログ：0024 - ABC 210 C