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

DP回
100-200-0-400-500-0で0ペナ4完1200点。

A - Slot

$C_1 = C_2$ と $C_2 = C_3$ が真なら、 $C_1 = C_3$ も真である。if文で判定すると解ける。

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

$i$ 番目のお酒を飲んだ時のアルコールの摂取量は、 $V_i\times \dfrac{P_i}{100}$ ml で求められる。 $1$ 番目から $i$ 番目までのお酒をすべて飲んだ時のアルコールの摂取量を計算していき、初めて $X$ を超えたときの $i$ が答えである。 $100$ で割ると誤差が出て怖いので、 $P_i$ を $100$ で割るかわりに $X$ を $100$ 倍すると整数のまま計算できる。

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

C - Mandarin Orange

解けなかった。いや、解けてたんだけど制約を見て $O(N^2)$ 解は通らないと判断して書かなかった（いいわけ）。

$l, r$ を決めたとき、区間 $[l, r]$ の最小値を $x$ とすれば、各皿ごとに $x$ 個のみかんを食べることができる。 $l$ を固定して考えたとき、 $r$ を増やしたときの最小値は $x\gets \min (x, A_{r})$ で更新できる。すべての $l, r$ について全探索して最大値を求めると、計算量は $O(N^2)$ となる。

実はこの問題は「ヒストグラムの最大長方形」の面積を求める問題に帰着できて（というかそのまま）、DPを使うことで $O(N)$ で解けるらしい。へ～

参考：
algorithms.blog55.fc2.com

D - Logical Expression

DP。
$x_0 \land x_1 \lor x_2 ...x_N$ という感じの式を考える（ただし前から順に評価していく）。 $i$ 回目の計算が終わった時点での答えはTrueかFalseのどちらかである。それぞれの答えとなるような変数の割り当て型の個数をそれぞれ $T_i, F_i$ とすると、 $i+1$ 回目の計算が終わった時点での答えも計算できる。

計算量は、 $O(N)$ 。 $N\le 60$ は、答えがオーバーフローしないための制約らしい。

E - Rotate and Flip

とりあえず、点 $(x, y)$ を回転させたり線対称な位置に移動させたりする更新を式で表す。

時計回りに $90$ 度回す

$x\gets y$
$y\gets -x$

反時計回りに $90$ 度回す

$x\gets -y$
$y\gets x$

$x=p$ を軸に対称移動させる

$x\gets -x+2p$
$y\gets y$

$y=p$ を軸に対称移動させる

$x\gets x$
$y\gets -y+2p$

これらの式を眺めてみると、点の位置の更新は
$x\gets Ax+By+C$
$y\gets Dx+Ey+F$
という式で表せることがわかる。さらに、これらの更新する式は重ねることができる。 $(x, y)$ の更新をする式を関数 $f((x, y), A, B, C, D, E, F)$ と見ると、関数の合成 $f(f(A', B', C', D', E', F'), A, B, C, D, E, F)$ は次のように表せる。
$x\gets A(A'x+B'y+C')+B(D'x+E'y+F')+C$
$y\gets D(A'x+B'y+C')+E(D'x+E'y+F')+F$

式を整理して
$x\gets (AA'+BD')x+(AB'+BE')y+C$
$y\gets (DA'+ED')x+(DB'+EE')y+F$
とすれば、関数の合成を $f(AA'+BD', AB'+BE', C, DA'+ED', DB'+EE', F)$ と一つの関数と見ることができる！（なげえ）