問題一覧 > 通常問題

No.2240 WAC

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 158
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 NachiaNachia
9 ProblemId : 9100 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 21:28:20

問題文

$N$ 個の W, $N+M$ 個の A, $M$ 個の C からなる文字列 $S$ が与えられます。

次の操作を $N+M$ 回繰り返して、$N$ 個の WA と $M$ 個の AC を手に入れられるかどうか判定してください。

  • $1\le i\lt j\le |S|$ を満たす整数 $(i,j)$ を選ぶ。
  • $S_i$ と $S_j$ をこの順に結合した文字列を手に入れる。
  • $S$ の $i$ 文字目と $j$ 文字目を取り除く。(とくに、 $|S|$ が $2$ 減少する。)

    • 制約

    • $N,M$ は整数
    • $1\le N,M\le 10^5$
    • $S$ は $N$ 個の W, $N+M$ 個の A, $M$ 個の C からなる文字列

    入力

    $N$ $M$
$S$

    出力

    操作を $N+M$ 回繰り返して、$N$ 個の WA と $M$ 個の AC を手に入れられるなら Yes を、そうでないなら No を出力してください。

    サンプル

    サンプル1
    入力
    1 2
WAAACC
    出力
    Yes

    $1$ 回目の操作では $(i,j)=(4,6)$ を選べば AC、 $2$ 回目の操作では $(i,j)=(3,4)$ を選べば AC、 $3$ 回目の操作では $(i,j)=(1,2)$ を選べば WA を それぞれ手に入れることができます。

    サンプル2
    入力
    2 2
ACWAWACA
    出力
    Yes

    サンプル3
    入力
    2 3
WACAACACAW
    出力
    No

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。