AtCoder Beginner Contest 196のきろく - Flkanjin’s 競プロ録

A - Difference Max (100点)
B - Round Down (200点)
C - Doubled (300点)
D - Hanjo (400点)
E - Filters (500点)
F - Substring 2 (600点、実行時間制限: 3 sec)
結果、感想

A - Difference Max (100点)

$x - y$ は $x$ について狭義単調増加、 $y$ について狭義単調減少であるため、 $x = b,$ $y = c$ のとき $x - y$ は最大値をとります。

B - Round Down (200点)

文字列として'.'が出てくるまで1文字ずつ出力すればOKです。
'.'が存在しなければ元から整数なのでそのまま出力します。

C - Doubled (300点)

$1 ≤ N < 10^{12}$ より全探索では間に合いません。ただし、 $N$ 以下で問題文の条件を満たすものは繰り返し文字列が高々 $10^6 - 1$ より、条件を満たすものを小さいものから順に $N$ より大きくなるまで個数をカウントすれば答えが出ます。

また、公式解説にある $O(1)$ の解法として、次のように繰り返す整数の数を求める方法が考えられます。
$N$ の桁数を $d$ とします。
$d$ が奇数の時は $1$ から $\underbrace{99\dots99}_{\frac{d - 1}{2}\ 桁}$ までの $\displaystyle 10^{\frac{d - 1}{2}} - 1$ 個の整数が条件を満たす数を生成します。
$d$ が偶数の時は $N$ の前半部 $n_1$ と後半部 $n_2$ について、 $n_1 \leq n_2$ のとき $1$ から $n_1$ までの $n_1$ 通り、 $n_1 \gt n_2$ のとき $1$ から $n_1 - 1$ までの $n_1 - 1$ 通りです。

D - Hanjo (400点)

公式解説のように全ての敷き詰め方をDFSで確かめる方法がありますが、少し別の方法を用いました。
重なりやはみ出ることを無視すると長方形の畳の配置方法は各畳の左上の位置とどちら向きに置くかの $2^A {}_{HW}\mathrm{C}_{A}$ 通りで、このうち、重なりやはみ出しのないものが条件を満たす敷き詰め方です。ここで各畳の左上の位置の ${}_{HW}\mathrm{C}_{A}$ 通りの列挙についてある状態から次の状態へ $O(1)$ で遷移できるならば $O(2^A {}_{HW}\mathrm{C}_{A} HW)$ で答えを求めることができます。

集合 $\{0,\,1,\,\dots,\,n-1\}$ の大きさ $k$ の部分集合の列挙は蟻本にある通り以下のようにして処理をすることができます。

int bit = (1 << k) - 1;
while(bit < (1 << n)){
    // 各集合についての処理をここに書く
    int x = bit & -bit, y = bit + x;
    bit = (((bit & ~y) / x) >> 1) | y;
}

この問題のコードを書くのに少し時間がかかってしまい、EやF問題に避ける時間が少なくなってしまいました。

またこっちの解法では長方形の畳が存在しない $A = 0$ のケースがコーナーとなってしまうことに注意しましょう(1敗)。

E - Filters (500点)

途中で $\max$ がある場合、定義域のうちある値以上については像の上限に、 $\min$ がある場合は定義域のうちある値以下については像の下限となるため、このような上下限に挟まれる範囲を「有意な範囲」と呼ぶことにします。このとき、函数 $f_i(x)$ についての有意な範囲と像の幅は等しくなります。

$f_0(x) = {\mathrm{id}}_{\mathbb{R}}(x) = x$ とし、 $i \leq j$ について $(f_i \circ f_{i-1} \circ \dots \circ f_1 \circ f_0)(x)$ の像を $[c_i,\,d_i],$ 有意な範囲を $[c_i - s_i,\,d_i - s_i]$ とします。

$\begin{align} (f_i \circ f_{i-1} \circ \dots \circ f_1 \circ f_0)(x) &= \left\{ \begin{array}{ll} c_i & (x \lt c_i - s_i)\\ x + s_i & (c_i \leq x \leq d_i)\\ d_i & (x \gt d_i - s_i) \end{array} \right\}\\ &= \max\{\min\{x + s_i,\,d_i\},\,c_i\} \end{align}$

となるので $c_N,$ $d_N,$ $s_N$ を求めればいいことが分かります。

$f_0$ については恒等写像であるため始域、有意な範囲、像が全て一致し、 $c_0 = -10^9,$ $d_0 = 10^9,$ $s_0 = 0$ となります。

$i - 1$ $(1 \leq i \leq N)$ 番目まで求まっていたとき、 $i$ 番目のそれぞれの値を求めましょう。このとき $f_i(x)$ の始域は $[c_{i-1},\,d_{i-1}]$ とみなすことができます。

$ t_i = 1 $ のとき

$f_i(x) = x + a_i$ のため、有意な範囲は変化せず、像は $[c_{i-1} + a_i,\,d_{i-1}+ a_i]$ です。よって、 $c_i = c_{i - 1} + a_i,$ $d_i = d_{i - 1} + a_i,$ $s_i = s_{i - 1} + a_i$ となります。

$ t_i = 2 $ のとき

$f_i(x) = \max\{x,\,a_i\}$ で、像は $[\max\{c_{i-1},\,a_i\},\,\max\{d_{i-1},\,a_i\}]$ となるため $c_i = \max\{c_{i-1}, a_i\},$ $d_i = \max\{d_{i-1}, a_i\},$ $s_i = s_{i-1}$ となります。また、 $f_i$ の有意な範囲は像と等しくなり、全体の有意な範囲は $[\max\{c_{i-1},\,a_i\} - s_{i-1},\,\max\{d_{i-1},\,a_i\} - s_{i-1}]$ となります。

$ t_i = 3 $ のとき

$f_i(x) = \min\{x,\,a_i\}$ で、像は $[\min\{c_{i-1},\,a_i\},\,\min\{d_{i-1},\,a_i\}]$ となるため $c_i = \min\{c_{i-1}, a_i\},$ $d_i = \min\{d_{i-1}, a_i\},$ $s_i = s_{i-1}$ となります。また、 $f_i$ の有意な範囲は像と等しくなり、全体の有意な範囲は $[\min\{c_{i-1},\,a_i\} - s_{i-1},\,\min\{d_{i-1},\,a_i\} - s_{i-1}]$ となります。

F - Substring 2 (600点、実行時間制限: 3 sec)

コンテスト中には解けませんでした...
文字列ですが整数列して扱います。答えは $\displaystyle \min_{0 \leq i \leq |S| - |T|} \sum_{j = 1}^{|T|} (S_{i + j} \oplus T_j)$ となります( $\oplus$ はXOR演算です)。 $T$ を反転させた配列を $T'$ とすると、 $\displaystyle \sum_{j = 1}^{|T|} (S_{i + j} \oplus T_j) = \sum_{j = 1}^{|T|} (S_{i + j} \oplus {T'}_{|T| - 1 - j})$ となるので畳み込み $\displaystyle \left( c_i = \sum_{j = 0}^{i} a_j b_{i-j} \right)$ のような式になるので、どうにかして積の和に変換できるとAC-Libararyのconvolutionが利用できるので、そのようにできるかを考えます。