No.1724 [Cherry 3rd Tune A] Lápiz labial de Sonia
タグ : / 解いたユーザー数 149
作問者 :
Kazun
/ テスター :
tatyam
箱星
お知らせ
ジャッジの結果がQLE だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.
問題文
ソニアは $N$ 種類の化粧品を買おうとしている. $N$ 種類の化粧品はそれぞれ A 社, B 社から販売されている.
ソニアはそれぞれの種類の化粧品について「A 社の製品」または「B 社の製品」のどちらか一方のみを買うことにした (両方買わないという選択はできない).
$i$ 種類目の化粧品について, 「A 社の製品」を買うと, ソニアは $A_i$ だけ嬉しさを獲得し, 「B 社の製品」を買うと, ソニアは $B_i$ だけ嬉しさを獲得する (それぞれ負の場合もあり得る).
ここで, ソニアは $N$ 種類の化粧品のうち, 「A 社の製品」をちょうど $K$ 種類, 「B 社の製品」をちょうど $N-K$ 種類買いたい.
ソニアの要望を満たすような化粧品の買い方のうち, 獲得する嬉しさの総和を最大にする $N$ 種類の化粧品の買い方を1つ求めよ.
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq K \leq N$
- $|A_i|, |B_i| \leq 10^9$
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる.$N$ $K$ $A_1$ $\cdots$ $A_N$ $B_1$ $\cdots$ $B_N$
出力
出力は $N$ 文字の文字列 $S$ からなる. $i$ 種類目の化粧品について, A 社の製品を買う場合は $S[i]=$A, B社の製品を買う場合は $S[i]=$B とせよ. また, 改行を忘れないこと.
なお, 獲得する嬉しさの総和を最大にするような買い方が複数存在する場合はそのうちの1つを出力すれば良い.
サンプル
サンプル1
入力
3 1 2 7 4 3 5 8
出力
BAB
- $1$ 種類目の化粧品は A 社の製品を買い, 残りの化粧品は B 社の製品を買う場合, ソニアは嬉しさとして, $2+5+8=15$ 獲得する.
- $2$ 種類目の化粧品は A 社の製品を買い, 残りの化粧品は B 社の製品を買う場合, ソニアは嬉しさとして, $3+7+8=18$ 獲得する.
- $3$ 種類目の化粧品は A 社の製品を買い, 残りの化粧品は B 社の製品を買う場合, ソニアは嬉しさとして, $3+5+4=12$ 獲得する.
BAB は正解となる.
サンプル2
入力
5 2 1 1 1 1 1 2 2 2 2 2
出力
ABBBA
$5$ 種類の化粧品のうち, $2$ 種類を A 社の製品, $3$ 種類を B 社の製品で買うような買い方全てにおいて, 獲得する嬉しさは $8$ になる.
よって, このような買い方は全て正解である. つまり, ABBBA だけでなく, BAABB や ABBAB でも正解になる
サンプル3
入力
6 3 -31 -41 -59 -26 -53 -59 -27 -18 -28 -18 -28 -46
出力
ABBABA
どのような買い方をしても, 獲得する嬉しさは負である. 何故, ソニアはこのような買い物をするのだろうか?
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。