ABC144 バチャメモ - tinumu's reminder

atcoder.jp
引越し作業でTwitterばっかりやってた頭をリフレッシュ！

A - 9x9

A <= 9 && B <= 9 を見ればいいね

B - 81

setとかに入れてやると直感的っぽさがある
自分は i で割り切れるかと N / i <= 9 かをみた

C - Walk on Multiplication Table

約数を全列挙するときは $\sqrt{N}$ だけ回せば十分
あとはやると、できます

D - Water Bottle

方程式をときます！(終) 長方形としてみると楽になるかもしれないです

E - Gluttony

操作後の $A'$ を考える。
このとき、 $A'$ が昇順、 $F$ が降順になってると最適(どっちも単調増加のところがあると、Aのその2要素をswapすると、必ず得をするため)。

操作前の $A$ も、昇順に並べると最適である。
昇順に並んでいる状態なら $A'$ が必ず作れ、操作回数が最小になる(そもそも $A'$ が作れる時点で操作回数はどれも変わらない)ためである。

あとは、最小コストを求めればいいが、 $A'_i F_i \leq cost$ となるように $cost$ を決め打ちすると、 $A$ を $A'$ にするための最小の操作回数が定まり(条件を満たす $A'_i$ を最大化すれば良い)、これは単調減少である。そのため、操作回数が $K$ 以下になる最小の $cost$ を見つければ良いので、二分探索を使って $cost$ を求めることができる。

F - Fork in the Road

このグラフはDAG(Directed Acyclic Graph)である。 $s_i < t_i$ だから閉路が存在しないんだね。
まず、頂点 $1$ から頂点 $N$ までの経路の長さの期待値はどのようにしたら求められるだろうか(メタいことをいうと、DAGだしDPなんだろうな)。
そこで、ある頂点 $u$ から頂点 $N$ に行くための経路の長さの期待値を求めるとする。
$u$ から直接接続されている頂点でかつ、その頂点から頂点 $N$ へ向かうことができるものの集合を $V$ 、そのような頂点の数を $num$ とする。
頂点 $i$ の期待値を $E_i$ とすると、
$E_u = (\sum\nolimits_{v \in V} E_v) / num + 1$ になる。
頂点 $v$ に、 $1/num$ の確率でいくため、頂点 $v$ の期待値の重みは $1/num$ になる。それらを足していって、最後に $v$ に行くためのコスト $1$ を追加することで、前述の式が得られる。
$u \lt v$ より、頂点 $N$ から頂点 $1$ へ順に期待値を求めていけば、DPができる。
これにかかる計算量は $O(M)$ である。
これを辺を一つ消したものを考慮して全部見ていくと、 $O(M^2)$ となってしまい間に合わない。

ここで、頂点 $u$ につながる辺を一つ消すときのことを考える。
dpは右側から求めているので、 $u \lt w \leq N$ である $E_w$ の値は何も変化していないことがわかる。
$E_u$ はできるだけ小さくしておきたいので、 $\mathrm max_{v \in V} E_v$ である $v$ と繋がっている辺を削除すれば一番小さくなることがわかる。
このような辺は $1$ 頂点につき $1$ つ存在するので、消すべき辺の候補は $N$ 個以下に絞ることができる。
よって、 $N$ 回試せばよく、 $O(NM)$ でこの問題を解くことができた。

なんか見積もり2億とかでもいまだとかんたんに通るんだね

ソース

A : https://atcoder.jp/contests/abc144/submissions/10564376
B : https://atcoder.jp/contests/abc144/submissions/10564395
C : https://atcoder.jp/contests/abc144/submissions/10564444
D : https://atcoder.jp/contests/abc144/submissions/10564821
E : https://atcoder.jp/contests/abc144/submissions/10566829
F : https://atcoder.jp/contests/abc144/submissions/10568764

感想

やっぱりちょっとやってないだけでも鈍るな
いろいろな問題が出てくるから楽しいね
Dとか面白かった　高校数学
DPの考え方として、他の値をどう使うとできるのかってところがあって、その使い方に慣れていかないとなーって感じた
まだ、全完ができないセットがたくさんあるので、ちゃんとFの復習をしてちゃんと説いていきたいと思う。