今日解いた競プロの問題。

ABC257-G: 自力AC。久々にこのレベル帯の過去問を自力で解けたので気分が良い。

明らかにDPで解くのが良さそうな問題なのでDPを考える。まず$DP[i]$を「Tの先頭i文字をSの接頭辞の連結で表した場合の最小連結数」と定義する。Tの先頭i文字がSの接頭辞x個で表現できるならば先頭i-1文字もx個で表現できるので、$DP[i]$は広義単調増加になる。この問題の答えは$DP[|T|]$になる。

計算をどうするかについて。最初は集めるDPで解こうと思ったが、これは筋が悪そうだった。$DP[i]$を$DP[j] (j<i)$を元に計算していくやり方だ。Tの先頭からj+1文字目～i文字目がSの接頭辞になっていれば$DP[i] \rightarrow \min(DP[i], DP[j] + 1)$とする遷移が考えられるが、この条件はjに対して単調ではないので、二分探索などでの高速化は厳しく見える。なので不採用。

配るDPの場合の方が都合が良い。Tの先頭からi文字目～i+j文字目がSの接頭辞になっているならば、という条件はjに対して単調だ。jがある値未満ならば真でありそれ以上は偽となる。なので二分探索による高速化が効く。配るDPゆえに更新が面倒だが、そこは双対セグ木を使えば良い。

部分文字列の比較処理が遅いので、そこをロリハで高速化すれば$O(|T|\log |T|)$で解ける。

• DP
• 双対セグ木
• ロリハ

といった道具を適切に組み合わせる必要がある良問だった。

ところで公式解説はZ-algorithmとかいう知らんやつだった。エー

---

「フランケンシュタイン」を読み進めた。例の怪物のやたら高い教養の源泉があきらかになった。失楽園とか若きウェルテルの悩みとか読んでたらしい。いろいろ納得がいった。若きウェルテルの悩みは読んだことないので知らんが、失楽園はまさにこの物語のテーマにぴったりだ。この怪物はいわば何の罪を犯したわけでもないのに生まれながら楽園から閉め出され、物語中で本人が言うようにイヴという仲間をもらうことも無かったわけなので(この視点はなかった！)、そりゃあフランケンシュタインはなじられるに決まっている。

フランケンシュタインは有名な作品なので「神の領域に手を出した報い」という大雑把なテーマは知っていたのであるが、具体的に怪物がフランケンシュタインに何を求めたのかは今まで知らなかった。「イヴをよこせ、創造主としての責務を果たせ」というのは何とも衝撃的で、なるほど～～そう来るのか～～～というカタルシスがあった。フランケンシュタインの言動の無責任さ、そしてそれの根幹にある等身大の人間としての脆さもテーマと絡み合って味が深い。

しかしこれ、「フランケンシュタインは創造主としての責務を果たさなかった」「じゃあ神は本当に責務を果たしたのか？」みたいな話になってくるとキリスト教的には色々危ういテーマでもある気がするんだが、そこんとこどうなんだろう。

話の本筋とは関係ないが、この怪物プレゼンが上手いな…

---

今週の胎界主を読んだ。

純子意外と出来る範囲でちゃんともの考えてそうだな…