AtCoder Beginner Contest 076: C - Dubious Document 2

solution

$L = |S|$として$O(L^2 \log L)$。

「$T$を配置できる最も後ろの位置に配置して残りをaで埋める」だと嘘で、すべて試して最小を取る必要がある。 しかしテストが弱かったらしく前者で通る。私は気付かず前者で通した。

Cは、最初、置き換えられる最後方のを置換してあとは a で埋めるのが最善だろって思ってしまったけど、実装した後で
?b??
ab
が
abab になってしまうけど、abaa のが良いことに気付いて、候補を全部持ってソートするように変えた。

— しさし (@shisashi) 2017年10月28日

implementation

#!/usr/bin/perl
chop($s=<>=~y/?/./r);chop($t=<>);$a=UNRESTORABLE;$p=substr($s,$_,$m=length$t),$t=~/^$p$/?$a=substr($s,0,$_).$t.substr($s,$_+$m):0for 0..length$s;print$a=~y/./a/r