AtCoder Beginner Contest 343 E,G問題メモ
E - 7x7x7
問題
- $7 \times 7 \times 7$ の立方体を3個、3次元空間上に配置する
- 「立方体を $(a,b,c)$ に配置する」とは、$[a,a+7),[b,b+7),[c,c+7)$ を満たす座標に配置することを意味する
- 以下の条件を満たすような置き方があるか判定し、存在する場合は一例を示せ
- ちょうど1つの立方体に含まれる部分の体積が $V_1$
- ちょうど2つの立方体に含まれる部分の体積が $V_2$
- ちょうど3つの立方体に含まれる部分の体積が $V_3$
- 配置場所 $(a_i,b_i,c_i)$（$i=1,2,3$）の絶対値は全て100以下
解法
ABC343で、$7^3=343$ であることにちなんだ問題。
立方体を置く座標を全探索するが、ある程度、枝刈りしないと間に合わない。
しかし、枝刈りしすぎて本来可能な配置を見落としてもいけない。
まず、最初に個数が合っているか確認する。$V_1+2V_2+3V_3=343 \times 3$ となっていなければおかしい。
以下、それを満たすとする。
相対的な位置関係が重要なので、1つめの立方体は原点に固定する。$(a_1,b_1,c_1)=(0,0,0)$
$z$ 軸を省略して、$x,y$ 軸の関係だけを考えると、$(a_2,b_2),(a_3,b_3)$ は、非負としてよい。
┌──┐ │┌─┼┐ 回転・反転すれば、どれかの正方形は、 ┌┼┼┐││ かならずx座標もy座標も最も小さい配置にできる │└┼┼┘│ （そうできない配置にするには、4つ必要） │ └┼─┘ └──┘
また、$0 \le a_2 \le 7, a_2 \le b_2 \le 7, a_2 \le a_3 \le a_2+7, a_2 \le b_3 \le b_2+7$ という条件を加えてもよい。
- $a_2,b_2,a_3,b_3$ のうち最も小さい座標が $a_2$ となるように、立方体を交換・回転させてよい
- 2つめの立方体は1つめから間を1以上開けて配置する意味は無い
- 3つめの立方体は2つめから間を1以上開けて配置する意味は無い
ただ、$z$ 軸は必ずしもそうではなく、$c_2$ は正に固定しても、$c_3$ は負になることがあり得る。
つまり、立方体が3つあると回転・反転しても、どの立方体も「$x$ 座標も $y$ 座標も $z$ 座標も最も小さい」ような配置にできない場合がある。
よって、$0 \le c_2 \le 7, -7 \le c_3 \le c_2+7$ の範囲を試す必要がある。
これで探索空間はざっくり $8*8*8*15*15*22=2.5 \times 10^6$ 程度となり、 その配置が $V_1,V_2,V_3$ と合うかの判定は $O(1)$ でできるので間に合う。
（ただ、実装のしやすさや、条件の見落としにくさなどを考慮した場合、 公式Editorialのように「2つめ、3つめの立方体は、どの座標も $-7～7$ の範囲を動く」とした方が賢いと思う）
一応、さらなる枝刈りの方法として、$V_3$ が表す領域は必ず1つの直方体になる。
x軸で3つが重なっている部分の長さは $d_x=\max(0,\min(a_1+7,a_2+7,a_3+7)-\max(a_1,a_2,a_3))$。
$d_y,d_z$ も同様に求めた時、$V_3=d_xd_yd_z$ になっていないといけない。
つまり、$V_3$ が正の場合、
- 3つの $x$ 軸を決めた時点で $d_x$ が $V_3$ の約数になってないといけない
- 続けて3つの $y$ 軸を決めた時点で $d_xd_y$ が $V_3$ の約数になってないといけない
このあたりを早期に判定すると、$V_3$ が正の場合に限るが、探索空間をさらに減らせる。
G - Compress Strings
問題
- $N$ 個の文字列 $S_1,...,S_N$ 全てを部分文字列として持つ文字列として、ありえるものの最小の長さを求めよ
- $1 \le N \le 20$
- $S_1,...,S_N$ は英小文字からなる文字列
- $S_1,...,S_N$ の長さの総和は $2 \times 10^5$ 以下
解法
$S_i$ が $S_j$ の中に完全に含まれるような2つの文字列は、 $S_j$ を入れたら勝手に $S_i$ も入ってくるので、予め $S_i$ は除いておく。
言語標準の文字列検索アルゴリズムは、被検索文字列を $S$、検索文字列を $T$ として $O(|S|+|T|)$ などで動作するので、$L=\sum_i{|S_i|}$ とすると、$O(N L)$ で調べられる。
以下、$N$ も $S_i$ も、除いた後の状態とする。
答えとなる文字列 $X$ 中に出現する順を固定したとき、その出現位置の左端と右端は必ず単調増加になる。
（そうなっていない場合、包含関係となってしまい、除いたという前提に矛盾する）
X : snukenshokudai S1: snuke 左端と右端はそれぞれ単調増加になる S2: kensho S3: shokudai
$S_1,S_2$ までを考慮した暫定の $X=$ snukensho に、$S_3=$ shokudai を加えたいとき、
$X$ の末尾と $S_3$ の先頭が重なるように置いて損しない。
S2: kenshoshosho S3: shoshoshokudai S3: shoshoshokudai 重ねられる位置が複数あっても、 S3: shoshoshokudai ←最も重なる文字数が多くなるように置いてよい
敢えて重ねる文字数を減らすことで、他が上手く重ねられて文字数が削減できる、というようなことは無い。
S2: kenshoshosho そのような場合、後に続く文字列は、 S3: shoshoshokudai S3だけでなく、S2とS3の関係性にまで影響を受けるということであり、 S4: hoshoshoshoku 右端がS3より短ければS2→S4→S3 と並べた場合を調べた時に考慮されるので大丈夫。 S5: hoshoshoshokudaira S3より長ければS3を包含しているので前提に矛盾する。
何文字重ねられるかは、直前（$S_3$ にとっての $S_2$）より前に何を置いたかに依らず、$S_2$ と $S_3$ だけで決まる。
あらかじめ、2つの文字列の組それぞれにつき、最大限重なる位置を求めておけばよい。
このような性質から、最短経路問題に帰着できる。
- $N$ 頂点ある
- 辺 $i→j$ のコストは、文字列 $S_i$ の末尾と $S_j$ の先頭を最大限重ねた後、はみ出る部分の文字数とする
kenshoとshokudaiなら sho を重ねてkudaiの5文字分がはみ出るsnukeとshokudaiなら重なる部分がないのでshokudaiの8文字分が全てはみ出る
- どこからスタートしてどこで終えてもよいので、全ての頂点を巡る最短パスの長さを求めよ
これは、巡回セールスマン（の始点に戻らない版）で、$O(2^NN^2)$ で求められる。
後は、コスト（$S_i$ と $S_j$ の重なる部分）の求め方である。
文字列 $S_j+S_i$ に対して Z-Algorithm を用いればよい。
|→
Sj+Si: s h o k u d a i k e n s h o
Z : 14 0 0 0 0 0 0 0 0 0 0 3 0 0
| ^
Si 由来の箇所のうち「Zの値 = そこ以右にある文字数」と
なっている箇所の中で、最も左にあるもの
計算量は、文字列結合も、Z-Algorithm も、その結果を調べるのも、文字列の長さに依存する。$O(|S_i+S_j|)$
1つの $S_i$ に対し、自分以外の全ての文字列を対象（$S_j$）として求めるので、合わせて $O(自身の長さ \times N + L)$。
これを全ての $S_i$ について合計すると、$O(NL)$ となる。
よって、全体を通して $O(NL+2^NN^2)$ で求められる。
