おはやし日記

特にテーマ無しの日記。

Codeforces #650 D. Task On The Board を解く(こどふぉ 問題文和訳あり)[C++]

こんにちは。まさかのこどふぉへ進出。

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つ目のテストケースの回答としてaac aabがあり得ます。
  • 2つ目のテストケースの回答としてa b cがあり得ます。
  • 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\}$ のとき(epが増えてる)、$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で管理。

cordforces #650 D

Acceptedなりました。

おしまい

はじめてのこどふぉ。

3完2WAで計91ペナでした。

プライバシーポリシー ・お問い合わせはこちら