A - Lovely Language Model

実行時間制限: 2 sec / メモリ制限: 1024 MiB

問題文

高橋君には、好きな文字列が N 個ある。i 番目の文字列は S_i であり、その好ましさは P_i である。各 S_i は、a〜f の6種類の英小文字のみから構成されている。

最近、高橋君は確率的に文字列を生成するモデルに興味を持っており、自分が好きな文字列が高い確率で現れるような生成モデル、Lovely Language Model (LLM) を設計したいと考えている。

この生成モデルは M 個の状態から構成される。各状態 i（0 \leq i < M）には a〜f の 1 文字の英小文字 C_i を割り当てる。また、状態 i から状態 j への遷移確率を、パーセント単位の整数 A_{i,j} として設定する。これらはすべての i に対して次の条件を満たさなければならない：

\[ \sum_{j=0}^{M-1} A_{i,j} = 100 \]

このモデルは状態 0 から開始し、長さ L の文字列を生成すると停止する。生成される文字列の 1 文字目には、初期状態 0 に割り当てられた文字 C_0 が使われる。その後は遷移確率に従って状態遷移を行い、各遷移先の状態に割り当てられた文字を順に出力していく。

このようにして生成された文字列において、各文字列 S_i が連続部分文字列として 1 回以上 現れた場合、その好ましさ P_i を獲得する。好ましさの総和の期待値ができるだけ大きくなるように、文字割り当て C_0, C_1, \dots, C_{M-1} および遷移確率行列 A を設計せよ。

得点

設計したモデルで長さ L の文字列を生成する場合に、各文字列 S_i が連続部分文字列として 1回以上 含まれる確率を Q_i とする。 このとき、以下のスコアが得られる。

\[ \mathrm{round}\left(\sum_{i=0}^{N-1} P_i \cdot Q_i\right) \]

合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

入力は以下の形式で標準入力から与えられる。

N M L
S_0 P_0
S_1 P_1
\vdots
S_{N-1} P_{N-1}
  • N は文字列の数を表し、すべてのテストケースで N = 36 に固定されている。
  • M はモデルの状態数であり、M = 12 に固定されている。
  • L は生成する文字列の長さであり、L = 10^6 に固定されている。
  • S_i は a〜f の英小文字からなる長さ 6 \leq |S_i| \leq 12 の文字列である。
  • 好ましさ P_i は正の整数であり、1 \leq P_i \leq 17000 を満たす。
  • すべての S_i は互いに異なる。

出力

設計したモデルにおいて、i 番目の状態に割り当てる文字を C_i、状態 i から状態 j への遷移確率を A_{i,j} としたとき、以下の形式で標準出力に出力せよ。

C_0 A_{0,0} \cdots A_{0,M-1}
\vdots
C_{M-1} A_{M-1,0} \cdots A_{M-1,M-1}
  • 各 C_i は a〜f のいずれかである。
  • 各 A_{i,j} は 0 \leq A_{i,j} \leq 100 を満たす整数で、すべての i に対して \(\sum_{j=0}^{M-1} A_{i,j} = 100\) を満たさなければならない。

解は複数回出力しても良い。 複数出力された場合、一番最後に出力された解のみが採点に用いられる。 Web版のビジュアライザを用いると、複数の解の比較が可能である。

例を見る

入力生成方法

\mathrm{rand}(L, U): L 以上 U 以下の整数値を一様ランダムに生成する。

文字列 S_i の生成

各 S_i の長さ \ell_i を \ell_i = \mathrm{rand}(6, 12) により決定し、長さ \ell_i の文字列を以下の手順で生成する：

  • アルファベット a〜f から \ell_i 回ランダムに選んで連結する。
  • 同じ文字が複数回現れてもよい。

生成した文字列 S_i がすでに生成した文字列と一致した場合、長さ \ell_i の生成からやり直す。

好ましさ P_i の生成

各文字列 S_i に対して、以下により対応する好ましさ P_i を生成する：

  • 最大値 U_i = \left\lfloor 1.5^{2 \cdot \ell_i} \right\rfloor を計算する。
  • P_i = \mathrm{rand}(1, U_i) により一様ランダムに生成する。

このようにして、N = 36 個の (S_i, P_i) の組を独立に生成する。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例 1

36 12 1000000
acafbafdb 166
baeebdacd 86
baaffdcf 76
cfddcba 251
acdecbbfddaf 12423
ebcebe 107
feddecdb 373
acadbc 40
dcfaabebefcd 15639
fcebaade 438
cbefcedaaf 2468
efcfafcbcaac 4414
dbddcfa 96
cabacbdb 219
cbdeadcbad 3110
bbdeacbbe 894
deafadebdad 7067
dceedaacfefa 6453
deffecdee 280
cfffaaeca 651
aeffcbcfec 1021
ccefdcddadfd 6189
ffcdcb 91
afddebceadc 2283
ffebaff 258
aeceafebd 1235
fbbfec 83
fcdeceffbaf 1787
ddfffeb 188
bebffddaa 238
eedbfbaed 500
cacbccdbd 1346
cafbfbedcff 393
eccbdecdfefa 4423
fdfaddae 522
befebddfe 507

出力例 1

e 66 0 0 0 0 12 0 0 0 0 9 13
e 36 12 0 0 0 0 0 0 0 11 0 41
d 0 20 0 56 0 0 0 0 5 0 19 0
a 0 8 12 79 1 0 0 0 0 0 0 0
f 0 0 0 0 0 0 41 0 0 10 37 12
c 0 0 0 31 0 0 0 53 15 0 1 0
b 0 0 0 0 23 0 65 1 0 0 0 11
f 34 0 8 0 0 0 0 0 0 14 0 44
e 21 0 0 0 10 57 0 0 0 12 0 0
f 0 41 18 0 0 22 0 0 0 0 19 0
a 6 0 0 46 0 0 16 0 0 0 32 0
b 12 0 0 21 24 43 0 0 0 0 0 0

Problem Statement

Takahashi has N favorite strings. The i-th string is denoted by S_i, and its preference is P_i. Each S_i consists only of lowercase English letters from a to f.

Recently, Takahashi has become interested in probabilistic models for generating strings. He wants to design a generation model, called the Lovely Language Model (LLM), that generates the strings he likes with high probability.

This model consists of M states. Assign a single lowercase letter C_i from a to f to each state i (0 \leq i < M). Additionally, for each pair of states (i, j), define the transition probability from state i to state j as an integer A_{i,j}, which represents a percentage value. These values must satisfy the following condition for all i:

\[ \sum_{j=0}^{M-1} A_{i,j} = 100 \]

The model starts from state 0 and stops after generating a string of length L. The first character of the generated string is the character assigned to state 0, namely C_0. Then, the model performs state transitions according to the transition probabilities, outputting the character assigned to each newly transitioned state in order.

For each string S_i, if it appears at least once as a contiguous substring in the generated string, Takahashi gains its corresponding preference P_i. Your task is to design the character assignment C_0, C_1, \dots, C_{M-1} and transition matrix A to maximize the expected total preference.

Scoring

Let Q_i be the probability that the generated string of length L contains the string S_i at least once as a contiguous substring.

Then, your score is calculated as follows:

\[ \mathrm{round}\left(\sum_{i=0}^{N-1} P_i \cdot Q_i\right) \]

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

N M L
S_0 P_0
S_1 P_1
\vdots
S_{N-1} P_{N-1}
  • N is the number of strings. It is fixed at N = 36 in all test cases.
  • M is the number of states in the model. It is fixed at M = 12.
  • L is the length of the string to be generated. It is fixed at L = 10^6.
  • Each S_i is a string consisting of lowercase English letters from a to f, with length satisfying 6 \leq |S_i| \leq 12.
  • Each preference P_i is a positive integer satisfying 1 \leq P_i \leq 17000.
  • All S_i are distinct.

Output

In the designed model, let C_i be the character assigned to state i, and A_{i,j} be the transition probability from state i to state j.

Then, output to Standard Output in the following format:

C_0 A_{0,0} \cdots A_{0,M-1}
\vdots
C_{M-1} A_{M-1,0} \cdots A_{M-1,M-1}
  • Each C_i must be one of the lowercase letters from a to f.
  • Each A_{i,j} must be an integer satisfying 0 \leq A_{i,j} \leq 100, and for every i, the following condition must hold:

\[ \sum_{j=0}^{M-1} A_{i,j} = 100 \]

Your program may output multiple solutions. If multiple solutions are output, only the last one is used for scoring. You can compare multiple solutions using the web version of the visualizer.

Show example

Input Generation

\mathrm{rand}(L, U): Generates a uniformly random integer between L and U, inclusive.

Generation of Strings S_i

For each S_i, determine its length \ell_i using \ell_i = \mathrm{rand}(6, 12), then generate a string of length \ell_i as follows:

  • Randomly select \ell_i characters from the letters a to f and concatenate them.
  • The same character may appear multiple times.

If the generated string S_i is identical to any previously generated string, restart the generation from the length selection step.

Generation of Preferences P_i

For each string S_i, generate its corresponding preference P_i as follows:

  • Compute the upper bound U_i = \left\lfloor 1.5^{2 \cdot \ell_i} \right\rfloor.
  • Generate P_i = \mathrm{rand}(1, U_i) uniformly at random.

Repeat this process independently to generate N = 36 pairs of (S_i, P_i).

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Sample Input 1

36 12 1000000
acafbafdb 166
baeebdacd 86
baaffdcf 76
cfddcba 251
acdecbbfddaf 12423
ebcebe 107
feddecdb 373
acadbc 40
dcfaabebefcd 15639
fcebaade 438
cbefcedaaf 2468
efcfafcbcaac 4414
dbddcfa 96
cabacbdb 219
cbdeadcbad 3110
bbdeacbbe 894
deafadebdad 7067
dceedaacfefa 6453
deffecdee 280
cfffaaeca 651
aeffcbcfec 1021
ccefdcddadfd 6189
ffcdcb 91
afddebceadc 2283
ffebaff 258
aeceafebd 1235
fbbfec 83
fcdeceffbaf 1787
ddfffeb 188
bebffddaa 238
eedbfbaed 500
cacbccdbd 1346
cafbfbedcff 393
eccbdecdfefa 4423
fdfaddae 522
befebddfe 507

Sample Output 1

e 66 0 0 0 0 12 0 0 0 0 9 13
e 36 12 0 0 0 0 0 0 0 11 0 41
d 0 20 0 56 0 0 0 0 5 0 19 0
a 0 8 12 79 1 0 0 0 0 0 0 0
f 0 0 0 0 0 0 41 0 0 10 37 12
c 0 0 0 31 0 0 0 53 15 0 1 0
b 0 0 0 0 23 0 65 1 0 0 0 11
f 34 0 8 0 0 0 0 0 0 14 0 44
e 21 0 0 0 10 57 0 0 0 12 0 0
f 0 41 18 0 0 22 0 0 0 0 19 0
a 6 0 0 46 0 0 16 0 0 0 32 0
b 12 0 0 21 24 43 0 0 0 0 0 0