こんにちは。まさかのこどふぉへ進出。
Cまで解きました。
で、Dの解説とサンプルコード（Codeforces Round #650 (Div. 3) Editorial - Codeforces）を読んだらなるほどぉ〜〜〜ってなったので自分で書いてみます。
問題
https://codeforces.com/contest/1367/problem/D
できる限り和訳してみます。
Polycarp（誰？）は英小文字（a-z）からなる文字列 $S$ を書きました。
その後、彼は $S$ からいくつか文字を消し、残っている文字をランダムに並び替えて文字列 $T$ を書きました。あなたは、与えられた情報から $T$ をあててください。
- $T$ の長さは $ m $ であり、それぞれの文字に次のルールから得られる数字がついています。数字は数列 $ \{ b_1, b_2, \cdots , b_m \} $ として与えられます。
- $b_i$ は、$T$ の $i$ 番目の文字 $T_i$ について、$T$ のなかで $T_i$ よりアルファベット順が大きい文字 $T_j$ との距離 $|i-j|$ の総和です。
例えば、$T = \text{abzb}$ のとき
- $T_1$ は
aなので $T$ の中でアルファベット順でaより後ろである文字との距離の総和をとって $b_1 = |1−2|+|1−3|+|1−4|=1+2+3=6$ - $T_2$ は
bなので $T_3 = \rm{z}$ がアルファベット順で後ろにあるため、$b_2 = |2−3|=1$ - $T_3$ は
zなので、$T$ の中にアルファベット順がzより後ろである文字はないため、$b_3 = 0$ - $T_4$ は
bなので $T_3 = \rm{z}$ がアルファベット順で後ろにあるため、$b_4 = |4−3|=1$
従って、$T = \text{abzb}$ のとき $b = \{6,1,0,1\}$ が与えられます。
与えられた文字列 $S$ と数列 $b$ から、$T$ としてあり得るものを見つけてください。
$T$は次の2つの要求を同時に満たす必要があります。
- $T$ は、$S$ からいくつかの（0文字も可）文字を消して任意の順で並び替えて得られる
- $T$ から上記のルールに従って求めた数列は、入力で与えられる $b$ と一致する。
入力
第1行目に整数 $q$ : テストケースの数 $(1≤𝑞≤100)$
続いて $q$ 個のテストケースが与えられます。それぞれのテストケースについて
- 1行目 : $S (1 \le |S| \le 50)$ $S$ は英小文字からなる
- 2行目 : 整数 $ m (1≤m≤|S|) $ : 数列 $b$ のサイズ
- 3行目 : 整数 $b_1, b_2, \cdots , b_m (0 \le b_i \le 1225)$
それぞれのテストケースについて答えが存在することが保証されます。
出力
$q$ 行出力します。$k$ 行目には $k$ 番目のテストケースに対する回答 $T$ を出力します。複数の答えが存在するとき、そのうちの1つを出力します。
入出力例
- 入力
4 abac 3 2 1 0 abc 1 0 abba 3 1 0 1 ecoosdcefr 10 38 13 24 14 11 5 3 24 17 0
- 出力
aac b aba codeforces
- 1つ目のテストケースの回答として
aacaabがあり得ます。 - 2つ目のテストケースの回答として
abcがあり得ます。 - 3つ目のテストケースの回答としては
abaのみですが、ここでのbは $S$ の2文字目に由来するか3文字目に由来するかを区別しません（原文: In the third test case, only the string 𝑡 equals to "aba" is suitable, but the character 'b' can be from the second or third position.）。
解法
- $b_i = 0$ であるところには、$T$ の中で最もアルファベット順が後ろのものが入る（その文字が $S$ の中に十分存在すれば）。
- そこを埋めたら、他の場所の $b_j$ から $|i-j|$ を引く。
よくわからんので例を。入力例4からちょっと改変
$T = \text{ecoosdcefrep} , b = \{38, 13, 24, 14, 11, 5, 3, 24, 17, 0\}$ のとき（eとpが増えてる）、$T$ をアルファベット順に並び替えておくとccdeeefooprs。
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| s |
$b_{10} = 0$ なので $T_{10} = \rm{s}$ とする。その他の $b_j$ には、そこに入る文字がなんであろうとすべて $|10-j|$ が加算されているのでそれぞれ差っ引いてあげる。そうすると $i=10$ を無視した問題に帰結する。
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | s |
| 29 | 5 | 17 | 8 | 6 | 1 | 0 | 22 | 16 |
$T$ に残っている文字はccdeeefoopr。$b_{9} = 0$ なので $T_{9} = \rm{r}$ とする。
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | s |
| 29 | 5 | 17 | 8 | 6 | 1 | 0 | 22 | 16 | |
| -6 | -5 | -4 | -3 | -2 | -1 | r | -1 | -2 | |
| 23 | 0 | 13 | 5 | 4 | 0 | 21 | 14 |
$T$ に残っている文字はccdeeefoop。$b_i = 0$ となる場所が2つあるがどちらかだけにpを入れるなどしてはいけない。pは捨てて、oが2つあるのでそれを入れる。
引き算はそれぞれのoからの距離を重ねて引く。
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | s |
| 29 | 5 | 17 | 8 | 6 | 1 | 0 | 22 | 16 | |
| -6 | -5 | -4 | -3 | -2 | -1 | r | -1 | -2 | |
| 23 | 0 | 13 | 5 | 4 | 0 | 21 | 14 | ||
| -1 | o | -1 | -2 | -3 | -6 | -7 | |||
| -5 | -3 | -2 | -1 | o | -2 | -3 | |||
| 17 | 9 | 1 | 0 | 13 | 4 |
$T$ に残っている文字はccdeeef。$b_{5} = 0$ なので $T_{5} = \rm{f}$ とする。
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | s |
| 29 | 5 | 17 | 8 | 6 | 1 | 0 | 22 | 16 | |
| -6 | -5 | -4 | -3 | -2 | -1 | r | -1 | -2 | |
| 23 | 0 | 13 | 5 | 4 | 0 | 21 | 14 | ||
| -1 | o | -1 | -2 | -3 | -6 | -7 | |||
| -5 | -3 | -2 | -1 | o | -2 | -3 | |||
| 17 | 9 | 1 | 0 | 13 | 4 | ||||
| -4 | -2 | -1 | f | -3 | -4 | ||||
| 13 | 7 | 0 | 10 | 0 |
$T$ に残っている文字はccdeee。$b_4 = b_9 = 0$ なので $T_4 = T_9 = \rm{e}$ とする。余ったeは捨てる。
同様に残りを埋める
| 38 | 13 | 24 | 14 | 11 | 5 | 3 | 24 | 17 | 0 |
|---|---|---|---|---|---|---|---|---|---|
| -9 | -8 | -7 | -6 | -5 | -4 | -3 | -2 | -1 | s |
| 29 | 5 | 17 | 8 | 6 | 1 | 0 | 22 | 16 | |
| -6 | -5 | -4 | -3 | -2 | -1 | r | -1 | -2 | |
| 23 | 0 | 13 | 5 | 4 | 0 | 21 | 14 | ||
| -1 | o | -1 | -2 | -3 | -6 | -7 | |||
| -5 | -3 | -2 | -1 | o | -2 | -3 | |||
| 17 | 9 | 1 | 0 | 13 | 4 | ||||
| -4 | -2 | -1 | f | -3 | -4 | ||||
| 13 | 7 | 0 | 10 | 0 | |||||
| -3 | -1 | e | -4 | ||||||
| -8 | -6 | -1 | e | ||||||
| 2 | 0 | 5 | |||||||
| -2 | d | -5 | |||||||
| 0 | 0 | ||||||||
| c | c | ||||||||
| c | o | d | e | f | o | r | c | e | s |
実装
$S$ に含まれるアルファベットを文字と個数のmapで管理。
Acceptedなりました。
おしまい
はじめてのこどふぉ。
3完2WAで計91ペナでした。
