Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 290 B問題 Qual B

AtCoder ABC290 ABC 200 pts B問題

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$N$ 人の人が予選大会に参加した.

それぞれの人の決勝の参加意思は長さ $N$ の文字列で表され, $S$ の $i$ 文字目が $\texttt{o}$ ならば参加意思があり, $\texttt{x}$ ならば参加意思はない.

決勝の参加意思がある人のうち, 上位 $K$ 人が決勝進出となる.

$N$ 人の決勝の進出の可否を以下で決定される長さ $N$ の文字列 $T$ で出力せよ.

予選 $i$ 位の人が決勝に進出するならば, $T$ の $i$ 文字目は $\texttt{o}$ である.
予選 $i$ 位の人が決勝に進出しないならば, $T$ の $i$ 文字目は $\texttt{x}$ である.

制約

$1 \leq K \leq N \leq 100$
$S$ は $\texttt{o}, \texttt{x}$ からなる長さ $N$ の文字列
$S$ にある $\texttt{o}$ の数は $K$ 個以上

解法

$S$ にある $\texttt{o}$ の場所を $i_1, i_2, \dots, i_L$ とする ( $i_1 \lt i_2 \lt \dots \lt i_L$ ).

このとき, $T$ は $i_1, \dots, i_K$ 文字目が $\texttt{o}$ で, それ以外は $\texttt{x}$ である文字列になる.