titiaのノート: AtCoder Beginner Contest 203（Sponsored by Panasonic）

2021年5月31日月曜日

　Eまで五完。Fも解けるべきだったが、最近ABCの成績が低迷したことを考えれば、まあ満足すべきか。

F - Weed

　コンテスト後、

・青木君は配列の前と後ろのみ刈れば良いと勘違いしていた、

・DPを使う

　というツイートを見たら分かってACできました。

　前者は全く同じ勘違いをしていた。この勘違いがなければDPは思いつけたんじゃないか、とは思うけど、一度嵌ると抜けにくい勘違いな気もする。

　まず、Aはソートしておく。

　高橋君だけが草を刈ることを考えると、

$A_i$ を切るとき一つ前に切っているのは、

$A_i*2$ 以下のもの。このようなもののうち最大のものを持つ配列を用意する。

　まあ、ダブリングするときの、一番最初に用意する配列ですね。

　これを用いて、DPする。

$DP[i][j]$ で、高橋君が

$i$ 回操作したとき、青木君は最低でも何本草を刈らねばいけないか、とする。

$i$ が変わらないところは、1ずつ増えていく感じで。

$i$ が増える方向の遷移は、事前に用意した配列を使えばできます。