問題

問題文

CODE FESTIVAL 2016の予選には $N$ 人が参加しました。参加者は、国内の学生であるか、海外の学生であるか、どちらでもないかのどれかです。
予選は国内または海外の学生のみが通過することができ、上位の学生から順に、以下の条件を満たすときに通過します。学生でない参加者は予選を通過できません。
・国内の学生は、現在予選の通過が確定した参加者が $A+B$ 人に満たなければ、予選を通過する
・海外の学生は、現在予選の通過が確定した参加者が $A+B$ 人に満たず、さらに海外の学生の中での順位が $B$ 位以内なら、予選を通過する
参加者の情報を表す文字列 $S$ が与えられます。$S$ の $i$ 文字目が a のとき予選で $i$ 位の参加者が国内の学生であることを、$S$ の $i$ 文字目が b のとき予選で $i$ 位の参加者が海外の学生であることを、$S$ の $i$ 文字目が c のとき予選で $i$ 位の参加者がそのどちらでもないことを表しています。
すべての参加者について、上位から順に、予選を通過した場合はYes、そうでない場合はNoを出力するプログラムを作成してください。

制約

・$1 \le N,A,B \le 100000$
・$A+B \le N$
・$S$ の長さは $N$ である。
・$S$ は文字 a と b と c のみからなる。

収録されている問題セット

[BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #003

回答

回答1 (AC)

問題文に書かれていることをそのままコーディングすれば良い問題です。予選を通過した国内学生の人数を変数 na に、予選を通過した海外学生の人数を変数 nb に記録します。予選で $i$ 位の参加者が国内学生ならば、これまでに予選を通過した学生数 na+nb が $A+B$ より小さければこの国内学生は予選通過となるので、na を 1 増加します。予選で $i$ 位の参加者が海外学生ならば、これまでに予選を通過した学生数 na+nb が $A+B$ より小さく、かつ予選を通過した海外学生数 nb が $B$ より小さければ、この学生は予選通過となるので、nb を 1 増加します。コードは以下のようになりました。

cf2016qb_b-1.cpp

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

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  string s;
  cin >> s;

  int na = 0, nb = 0;
  for ( int i=0; i<n; i++ ) {
    string yosen = "No";
    if ( s.at(i)=='a' ) {
      if ( na+nb<a+b ) {
        na += 1;
        yosen = "Yes";
      }
    } else if ( s.at(i)=='b' ) {
      if ( na+nb<a+b && nb<b ) {
        nb += 1;
        yosen = "Yes";
      }
    }
    cout << yosen << endl;
  }
}

調べたこと

AtCoder の解説 → コンテスト全体の解説

回答1と同じ方針でした。

リンク

前後の記事

前の記事 → AtCoderログ：0061 - AGC 012 A
次の記事 → AtCoderログ：0063 - ABC 085 B