予選B-D 「天下一電卓英作文」

問題文はこちら。

部分点解法

与えられた単語を対応表の通りに置換し、左右反転したものを得点文字列と呼ぶことにします。

各得点文字列を連結したものを連結得点文字列、長さD以下で最大得点となる連結得点文字列を最大連結得点文字列と呼ぶことにします。

入力例1で説明します。

9
4
hELLO
hELL
EGG
ODD

hELLO の得点文字列は"07734"です。

hELL の得点文字列は"7734"です。

EGG の得点文字列は"997"です。

ODD の得点文字列は"000"です。

最大連結得点文字列は"773407734"であり、得点も同じです。

連結得点文字列の先頭から末尾まで全て'0'の場合、得点は0となります。

連結得点文字列の先頭が'0'で、2文字目以降に'0'以外の文字が含まれる場合、得点は小数になります。たとえば、連結得点文字列"077347734"の得点は0.77347734です。

このように、求める最大得点は0になるか、1未満の小数になるか、1以上の自然数になります。

これは以下のように簡単に判別できます。

1. 単語帳に得点が0の単語しか存在しない場合、最大得点は0になります。
2. 単語帳に得点が1以上の単語が存在すれば、最大得点は1以上の自然数になります。
3. 単語帳に得点が1以上の単語が存在しなければ、最大得点は1未満の小数になります。

1の場合、0を出力して終了です。

2及び3の場合、以下の方法で答えを求めていきます。

部分点の制約では、全通り連結得点文字列を作成することができます。

長さD以下となる連結得点文字列をすべて作り、一番得点が高いものを探します。

深さ優先探索や、C++言語ならstd::next_permutationという関数を使用することで全通り調べることができます。

全通り調べる中で、現状求まっている最大連結得点文字列と、新たに作成した連結得点文字列とどちらが大きいか比較する必要があります。比較は以下のように行います。

• 最大得点が1以上の自然数の場合: 文字列の長さで比較し長い方、長さが同じ場合辞書順比較で大きい方を選択します。ただし、新たに作成した連結得点文字列の1文字目が'0'の場合は無視します。
• 最大得点が1未満の小数の場合: 辞書順比較で大きい方を選択します。

求めた最大連結得点文字列を以下のように出力します。

• 最大得点が1以上の自然数の場合: 最大連結得点文字列をそのまま出力します。
• 最大得点が1未満の小数の場合: 最大連結得点文字列の先頭から2文字目に.を挿入し、末尾の連続する0を消去し出力します。

満点解法

ある2つの得点文字列s, tの両方が最大連結得点文字列に含まれると仮定した時、s+tとt+s(+は文字列結合を表す)を辞書順比較した結果が大きい方の、左側に置いた得点文字列を先に連結するべきです。

s="123"、t="123123"など、一方がもう一方の繰り返しになっている場合については、sとt両方が最大連結得点文字列に含まれるという仮定から、どちらを先に連結しても問題ありません。

上記の比較方法を使用して、すべての得点文字列を降順ソートします。

一見、ソートしたリストの先頭から順に連結して行けば良さそうですが、上記の比較方法はsとt両方を使用する場合についてのみ成り立つ為、先頭から貪欲に連結していくと以下のようなケースで誤った答えになります。

3
3
Oq
hOq
E

最大得点は904ですが、先頭から貪欲に連結すると903になってしまいます。

また、最初に最大幅となる所まで連結するという方法の場合も、以下のようなケースで同様に誤った答えになってしまいます。

3
3
Oq
EOq
h

最大連結得点文字列は、以下のような漸化式で動的計画法を使って求めることができます。

// ws[] := 単語を変換した得点文字列のリストを降順ソートしたもの
// dp[i][j] := wsの先頭からi番目まで使用して良い時、長さjとなる最大連結得点文字列
dp[i][j] = max(dp[i][j], dp[i - 1][j - len(ws[i])] + ws[i])

このままだと空間計算量がO(ND^2)程度になり、メモリを使いすぎてしまいます。 ループの順番を工夫し、jの大きい方から順番に配列を更新することにより配列を再利用でき、空間計算量をO(D^2)程度に落とす事ができます。

dp[j] = max(dp[j], dp[j - len(ws[i])] + ws[i])

計算後のdp配列の各要素の中から最大連結得点文字列を探します。 比較方法、出力方法は部分点解法と同じです。