問題一覧 > 通常問題

No.1724 [Cherry 3rd Tune A] Lápiz labial de Sonia

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 151
作問者 : 👑 Kazun / テスター : tatyam 箱星
1 ProblemId : 4974 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-29 19:33:17

お知らせ

ジャッジの結果が QLE だった場合, 問題のミスまたはジャッジのミスが考えられます. ご報告をお願いします.

問題文

ソニアは N 種類の化粧品を買おうとしている. N 種類の化粧品はそれぞれ A 社, B 社から販売されている.

ソニアはそれぞれの種類の化粧品について「A 社の製品」または「B 社の製品」のどちらか一方のみを買うことにした (両方買わないという選択はできない).

i 種類目の化粧品について, 「A 社の製品」を買うと, ソニアは Ai だけ嬉しさを獲得し, 「B 社の製品」を買うと, ソニアは Bi だけ嬉しさを獲得する (それぞれ負の場合もあり得る).

ここで, ソニアは N 種類の化粧品のうち, 「A 社の製品」をちょうど K 種類, 「B 社の製品」をちょうど N−K 種類買いたい.

ソニアの要望を満たすような化粧品の買い方のうち, 獲得する嬉しさの総和を最大にする N 種類の化粧品の買い方を1つ求めよ.

制約

  • 1≤N≤2×105
  • 0≤K≤N
  • |Ai|,|Bi|≤109
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる. 
N K
A1 ⋯ AN
B1 ⋯ BN

出力

出力は 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 獲得する.
よって, 2 種類目の化粧品は A 社の製品を買う方法が最大の嬉しさを獲得するので, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。