No.3435 [Cherry 8th Tune *] 何回 LOVE SONG を書き換えただろうか?
タグ : / 解いたユーザー数 42
作問者 : 👑
Kazun
/ テスター :
kazuppa
問題ヴィジュアル
▶ オープンで問題ヴィジュアル公開
問題文
文字列 $T$ に対して, $T$ の長さを $\lvert T \rvert$ と書く. また, $1 \leq k \leq \lvert T \rvert$ に対して, $T$ の $k$ 文字目を $T_k$ と書く.
abcdefghijklmnopqrstuvwxyzの連続とは限らない非空部分列 $A$ が与えられる.
$1 \leq i \leq \lvert A \rvert, 1 \leq j \leq \lvert A \rvert$ に対して, $d(A_i, A_j)$ が与えられる. なお, $1 \leq i \leq \lvert A \rvert$ に対して, $d(A_i, A_i)=0$ である.
$A$ に含まれる文字からなる長さ $M$ の文字列 $X, Y$ に対して, $h(X, Y)$ を $$h(X, Y) := \sum_{k = 1}^M d(X_k, Y_k)$$ で定める.
$N$ 個の $A$ に含まれる文字からなる長さ $M$ の文字列 $S_1, \dots, S_N$ が与えられる. $i = 1, 2, \dots, N$ それぞれに対して, $$H_i := \sum_{j=1}^N h(S_i, S_j)$$ を求めよ.
制約
- $A$ は
abcdefghijklmnopqrstuvwxyzの連続とは限らない非空部分列. - $0 \leq d(A_i, A_j) \leq 10^9 \quad (1 \leq i \leq \lvert A \rvert, 1 \leq j \leq \lvert A \rvert)$.
- $d(A_i, A_i) = 0 \quad (1 \leq i \leq \lvert A \rvert)$.
- $1 \leq N \leq 3000$.
- $1 \leq M \leq 3000$.
- $S_i$ は $A$ に含まれる文字からなる長さ $M$ の文字列 $\quad (1 \leq i \leq N)$.
- 入力で与えられる数は全て整数である.
入力
入力は以下の形式で標準入力から与えられる.
$A$
$d(A_1, A_1)$ $\dots$ $d(A_1, A_{|A|})$
$\cdots$
$d(A_{|A|}, A_1)$ $\dots$ $d(A_{|A|}, A_{|A|})$
$N$ $M$
$S_1$
$\vdots$
$S_N$
出力
出力は $N$ 行からなる. 第 $i~(1 \leq i \leq N)$ 行には $H_i$ を整数として出力せよ.
最後に改行を忘れないこと.
サンプル
サンプル1
入力
eglnosv 0 1 2 3 3 2 1 10 0 1 2 3 3 2 20 10 0 1 2 3 3 30 20 10 0 1 2 3 30 30 20 10 0 1 2 20 30 30 20 10 0 1 10 20 30 30 20 10 0 2 4 love song
出力
34 43
$H_1$ について説明する. $H_1 = h(S_1, S_1) + h(S_1, S_2)$ である. $h(S_1, S_1) = 0$ である. そして, $h(S_1, S_2)$ について, $$h(S_1, S_2) = d(S_{1,1}, S_{2,1}) + d(S_{1,2}, S_{2,2}) + d(S_{1,3}, S_{2,3}) + d(S_{1,4}, S_{2,4})$$ であり,
- $d(S_{1,1}, S_{2,1})=d($
l$,$s$)=3$ - $d(S_{1,2}, S_{2,2})=d($
o$,$o$)=0$ - $d(S_{1,3}, S_{2,3})=d($
v$,$n$)=30$ - $d(S_{1,4}, S_{2,4})=d($
e$,$g$)=1$
サンプル2
入力
a 0 4 7 aaaaaaa aaaaaaa aaaaaaa aaaaaaa
出力
0 0 0 0
任意の文字列 $X$ に対して, $h(X, X) = 0$ であるため, $H_1 = H_2 = H_3 = H_4 = 0$ となる.
サンプル3
入力
acehiloprtuvyz 0 314494608 104724885 5324504 549179606 19222002 399165599 695354275 408659881 597688443 151437226 179722653 689318127 252535978 957749869 0 801759730 739728337 237071606 234287808 554686708 637578559 71992222 918107705 979433550 76496183 440319858 644570458 66661340 93450065 0 475862350 903376449 340988748 706305207 218294620 346323197 134912188 994413106 932820420 505781092 328157233 146218811 176354549 60553290 0 144267582 334846732 490725233 40920057 65417082 578945121 981456425 633479575 397815292 18783118 825002511 356090725 998848647 568116998 0 890478876 943191726 549401055 595776247 405149204 758824525 642383908 95431741 644371087 915713687 186929986 314113107 528263664 298927204 0 113489116 673399424 38188983 97084667 940679166 85222889 665533552 964942712 195421351 612665014 954417694 949082177 850253552 147256370 0 488861602 816474455 856193523 711239546 188908168 900625962 60074082 378959009 151050984 965235187 531167527 609836474 140734379 949806587 0 857625614 139692863 471000173 971201171 120247550 2155306 295848986 759245119 186053967 171980837 285311461 462636598 83453294 143878101 0 825294886 878342132 691645764 229897982 49922258 86117240 638694452 889991764 242291364 108409007 301005333 526531009 765172383 162583483 0 176966146 655511689 646626472 251181735 687439211 540899795 385293593 17358602 326108284 919989675 630278171 129172143 312172450 815015133 0 956223026 962004929 583991752 457065515 985086035 426940730 487611304 951276505 562628038 785923576 915525767 676021391 109571350 917082766 0 167068892 765589634 379804366 315161108 940043755 856119466 281908333 626850934 974259999 49660758 458579431 906065751 288463731 517552865 0 932405754 860920155 196065801 785019749 614273106 739795623 396634158 251905109 744446007 312407690 380141988 377271676 979856128 222334810 0 3 6 cherry purple violet
出力
5993741923 3726581665 7933964062
$A$ に含まれる全ての英小文字が $S_1, \dots, S_N$ の中に現れるとは限らない.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。