ABC196 - sapphire15の日記

全完3ぺナ127位でした。全体的に難しいと感じました。最初Dに30分以上書けたあげくWAが出たときは焦りましたが何とか全完することができました。

A - Difference Max

$x-y$ を最大化するには $x$ はできるだけ大きく、 $y$ をできるだけ小さくしたいです。 $x, y$ は今独立に選べるので $x$ の最大、 $y$ の最小を選べばよく、すなわち答えは $b-c$ となります。

B - Round Down

$X$ が非常に大きい可能性があるので、浮動小数点数で扱うと丸め誤差によって正確な処理ができません。したがって、まず文字列として入力を受け取るとよいです。小数点以下を切り捨てるので.より左の文字列を出力すればいいです。 C++で実装する場合は１文字ずつなめるのがやりやすいと思います。

$x$ の前半と後半の文字列を整数として見たもの $y$ とすると $y$ の桁数は $x$ の半分です。ここで制約をみると、 $x$ が高々12桁の整数なので $y$ は高々6桁です。したがって、 $y$ を $1$ 以上 $10^7$ 未満の範囲で全探索してあげればいいです。これは十分高速ですが、 $y$ を文字列として2つ繋げた後、整数とみたものを $f(y)$ とすると $f(y)$ は単調増加なので二分探索を使えばより高速解くことができます。

1WAしましたがこれは探索範囲を $10^6$ までにしていました。

D - Hanjo

難しかったです。

制約が $HW \le 16$ と小さいので全探索できそうです。まず、 $2\times 1$ の畳がおければ（中途半端な置き方をしない限り）残りのマスに $1\times 1$ の畳は一意に置き方が決まるので $2\times 1$ の畳だけ考えればいいです。更に、

各マスについて下方向への畳を置く
右方向への畳を置く
何もしない

の３通りの操作を考えれば $2\times 1$ の畳の置き方を全部調べられるので、この操作の仕方を右上から適当な順序で全探索していけばいいです。計算量は $O(3^{HW})$ ですが実際は枝刈りが入るためこれよりかなり高速です。

1WAしましたがこれは $H$ と $W$ を取り違えてました。

E - Filters

個人的に今回のコンテストで最難に感じました。

$g_i(x) = f_i\dots f_2(f_1(x))\dots)$ と定義します。手元でいろいろ実験してみると $g_i(x)$ は必ず以下の形で表わされることが分かります。 $$ \begin{align} g_i(x) = \begin{cases} L_i + b_i & (x\le L_i) \\ x + b_i & (L_i \le x \le R_i) \\ R_i + b & (R_i\le x) \end{cases} \end{align}$$

ここで$b_i$は整数で、$L_i, R_i$は整数もしくは$\infty, -\infty$であり$L\le R$とします。グラフに書くと大体こんな感じです。（水平線の部分がない場合や、斜め線の部分がない場合があることに注意してください。） f:id:sapphire15:20210321002952p:plain 証明は数学的帰納法でよいでしょう。証明のポイントとしては$g_i(x)$が単調増加であることを使うと見通しがよいです。

このことを踏まえると、$L_0 = -\infty, R_0 = \infty, b_0 = 0$として$L_i, R_i, b_i$を順に計算していくとよいことが分かります。具体的には$t_{i+1} = 1$のとき、$L_{i+1} = L_i, R_{i+1} = R_i, b_{i+1} = b_i + a_i$、$t_{i+1} = 2, 3$のとき$L_{i+1} = f_{i+1}(L_i + b_i) - b_i, R_{i+1} = f_{i+1}(R_i + b_i) - b_i, b_{i+1} = b_i$となります。

よって、$L_N, R_N, b_N$を$\Theta(N)$で計算できたので$g_N(x)$を$\Theta(1)$でもとめられるようになり、全体で$\Theta(N+Q)$でこの問題を解くことができました。

SegTree beatというデータ構造を使うとライブラリをはるだけの問題になるそうです。

F - Substring 2

排他的論理和を使うと問題を簡単に記述できます。求めるべきは $$\min_{0\le i < |S|-|T|}\left\lbrace\sum_{j = 0}^{|S|-1}{S_i\oplus T_{i+j}}\right\rbrace$$ です。なんか見覚えのある形になりそうです。ここで$S$を反転してあげると $$ \min_{0\le i < |S|-|T|}\left\lbrace\sum_{j = 0}^{|T|-1}{S_{|S|-j-1}\oplus T_{i+j}}\right\rbrace = \\ \min_{0\le k < |S|-|T|}\left\lbrace\sum_{i+j = |S|-1, 0\le i, 0\le j}^{}{S_{i}\oplus T_{j+k}}\right\rbrace $$ 畳み込みの形になりました。これを高速に計算できればこの問題は解けることになります。

さて、排他的論理和が普通のかけ算なら畳み込みはFFTというアルゴリズムを用いて$O(NlogN)$（配列の長さを$N$とする）で計算できます。排他的論理和をそのままではFFTに持ち込めませんが、$a^2 = b^2 \neq ab $を満たすような$a, b$が存在するとそれぞれ1と0に対応づけることで排他的論理和での畳み込みを一回のFFTで計算できます。（FFTをした後に連立方程式を解けばよいです）実は$a = 1, b = -1$とすると上の式は満たされるのでこの問題を解くことができました。