AtCoder Beginner Contest 196参加記（～E問題）

水色なのにCでWA出たのでだめです
f:id:mmnkblog:20210321031700p:plain

A - Difference Max

$x$ を大きくすると $x-y$ の値も大きくなる。逆に、 $y$ を大きくすると $x-y$ の値は小さくなる。なので、 $x-y$ の値を最大化する場合、 $x$ は最大に、 $y$ は最小にすればよい。つまり $b-c$ が答え。
最大化するときの基礎的な考えが問われる良問。

計算量は、 $O(1)$ 。

B - Round Down

C++を使ってる前提で話すと、 $10^{100}$ なんてデカい数は扱えない。文字列で受け取れば、「小数点以下を切り捨て」したいので、文字列の先頭からピリオドが登場する手前までを切り取って出力すればよいことがわかる。先頭から1文字ずつピリオドかどうか判定しながらちまちま出力すればよい。

計算量は、 $O(\log N)$ 。

C - Doubled

解けなかった。
制約がある程度大きいので $O(1)$ で解こうと思ったがどこかで実装をバグらせたらしくWAが出た。想定解は前半の桁だけ全探索して $N$ 以下か判定するというもの。発想としては全く難しくない。過去に類題も出てるのになぜその発想に至らなかったのか…。

計算量は、 $O(\sqrt N)$ 。

制約が小さいので、ピースの置き方を全探索する。再帰関数によるDSFを書いた。残りの畳の枚数と現在の敷き詰め状態を引数として渡す。もし空白のマスが存在していたら、そこに「縦長」「横長」「正方形」の3種類を敷き詰めた状態をそれぞれ作って再帰呼び出しする。もう置けない状態なら1を返す。こう書くと、返ってきた値の総和が求める通り数になる。状態数は超ざっくり見積もって最悪でも $3^{16} = 43,046,721$ 通りしかない（実際にはさらに少ない）ので全探索しても実行時間制限に十分間に合う。

E - Filters

考察を書く。間違っている可能性が大いにある。

$\max(x, a_i)$ もしくは $\min(x, a_i)$ が登場するまでに $x$ に足された数の合計を $S$ とすると、 $\max(x + S, a_i)=\max(x, a_i - S) + S$ である。クエリが来る前段階で $a_i - S$ は定数なのでこの答えはすぐに求められる。さらに $\min(x + S, a_i) = -\max(-x, -a_i+S)-S$ と書ける。さらにさらに、 $\max$ 関数の定義から、 $x$ のほうが選ばれなければそれ以降 $x$ が解に干渉してくることはない、つまり前から見て $k$ 番目の $\max$ 関数で $x$ のほうが採択されなかったときの答えは事前に計算しておくことが可能である（計算量の話はあとで考える）。なので、 $x$ と $-x$ のどちらかがある定数より小さいことが判明すれば、その時点で解が定まる。 $\max$ 関数が $K$ 個あったとすれば、数直線が $K+1$ 個の区間に分割され、さらにクエリで与えられる数値はその区間のどこかに必ず含まれる。

つまりどういうことかというと、「クエリで与えられた $x_i$ 」と「 $\max$ 関数のしきい値」をソートして前から見ていけば $O( (N+Q)\log(N+Q) )$ で答えが求まるのではないか？ということだ。
この「数直線を $K+1$ 個の区間に分割する」ことで先ほどの前計算（ $x$ が絡まない場合）の解も求められそう。（ここが求められずに時間が来てしまった）

ここで脳みそが疲れたのでやめた。
公式解説によると、この定義の関数は合成することができるらしく、「定数（低）」「 $x+\alpha$ 」「定数（高）」の3パターンしかないとのこと。クエリの数がバカ多いので合成できそうだとは思ったが合成した後のグラフの形がなぜエスカレーターみたいになるのかはわからなかった。

F - Substring 2

問題文がシンプルで簡単そうだがFFTを使うらしい。FFTってなんですか？

感想

コンテスト終了後もE問題を粘って解いていたが頭が腐っていたので解けなかった。レートが20くらい無くなった

3匹の猫

みみねこの競プロ精進メモ