writerでした。読みにくいです。ごめんなさい。
問題
Writer解
https://www.hackerrank.com/contests/oupc-beta/challenges/powernumber/submissions/code/1321951027
Tester解見て気づきましたが、入力をひとつ受け取るごとに更新したほうがいいです。無駄なメモリがかなりあります。
略解
文字列の価値最大化なので、まず以下のようなDPが思い浮かぶ。
dp[i]:=i文字目まで見たとき最大スピリチュアル度
しかし、愚直に文字列検索すると明らかに時間が足りないので、工夫をする必要がある。原石の文字数が十分少ない（たかだか10文字*10）ことから、 あらかじめ全列挙して辞書作成 を使うことができる。全列挙したときの考えられる最大要素数は \(O( M * 2 ^{10})\) なので、連想配列に乗せることができる。この辞書は、いずれか一種類の原石をひとつだけ加工して作ることができる数字列をキーに、その最大スピリチュアル度をバリューとする。
以上のように作成した辞書にしたがって、10文字前（後）まで先読みして最初のdpテーブルを更新することで、この問題を解くことができる。計算量は、連想配列にハッシュテーブルを使った場合 \( O(M * 2^{|A|} + N * |A| ) \) （\(|A|\)は原石の長さ）となる。
詳細な解説
最初に、スピリチュアル度の計算式 \(V - D * B\) について、減少度合いは削った文字数にしか依存していないことが分かる。このことから以下が言える。
①ひとつの数字列のスピリチュアル度は、もとの原石のスピリチュアル度と削った文字数によってのみ決まる。
①はスピリチュアル度の計算式の言い換えに過ぎないが、重要な気づきだ。
ここで、一種類の原石をひとつ加工した場合に出来上がるものについて考える。ここでは \(11123\) という数字列を扱う。
\(11123\) を \(123\) に加工する場合、加工の仕方は [11123]、[11123]、[11123]の3通り存在する。しかし、ここで「①ひとつの数字列のスピリチュアル度は、原石のスピリチュアル度と削った文字数によってのみ決まる」という先の気づきと合わせて考えると、 3通りの加工はすべて同じスピリチュアル度を持つことが分かる。したがって以下が成り立つ。
②一種類の原石ひとつから生成されうる部分数字列のスピリチュアル度は、すべて一意に定まる。
一般的には、一種類の原石は定数のスピリチュアル度を持っているため、削った文字数が等しければスピリチュアル度も等しい、ということから導ける。
②より、最大のスピリチュアル度を持つ任意の数字列を求めるためには、i文字目においてi文字目以降の部分数字列に完全に一致する原石の切り方を1文字ごとに調べれば良いということが分かる。ここで、以下のようなdpが自然に思いつく。
dp[i]:=i文字目まで見たとき最大スピリチュアル度
このdpテーブルの更新は、 \( dp[i] := dp[i-k]+max(a[i-k]...a[i]\)に一致する原石（加工済）のスピリチュアル度\() \) である。しかし \(M\) が大きいため、これでは時間内に解を求めることができない。
ここで②を見返すと、「一意に定まる」という記述からdpにおけるmaxの部分を 最初から計算しておいても問題がない ことが分かる。連想配列などのデータ構造を使用して、最初の計算結果を(加工後の数字列, 実現できる最大価値)のように保存すれば、検索の計算量を改善してこの問題を解くことができるようになる。なお、dpの更新を1文字ごとに「この先10字ずつ見る」というようにすれば、最初の連想配列は原石ひとつ分見れば十分である。
講評
AC: 15名
FAはtsutajさんでした。おめでとうございます！！！
dpの前計算をbit全探索でやるというアイデアはあって、もっとひねったことをしたかったのだが、自分の力ではこれが限界だった。educationalであればよいのだが。
