AtCoder Beginner Contest 343 E,G問題メモ

AtCoder Beginner Contest 343

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$ が正の場合に限るが、探索空間をさらに減らせる。

Python3

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 を用いればよい。

• 【図解】線形時間の文字列アルゴリズム「Z algorithm」をイラストとアニメーションでかみ砕く #C++ - Qiita

                       |→
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)$ で求められる。

Python3