Eまで五完。Fも解けるべきだったが、最近ABCの成績が低迷したことを考えれば、まあ満足すべきか。
F - Weed
コンテスト後、
・青木君は配列の前と後ろのみ刈れば良いと勘違いしていた、
・DPを使う
というツイートを見たら分かってACできました。
前者は全く同じ勘違いをしていた。この勘違いがなければDPは思いつけたんじゃないか、とは思うけど、一度嵌ると抜けにくい勘違いな気もする。
まず、Aはソートしておく。
高橋君だけが草を刈ることを考えると、$A_i$を切るとき一つ前に切っているのは、$A_i*2$以下のもの。このようなもののうち最大のものを持つ配列を用意する。
まあ、ダブリングするときの、一番最初に用意する配列ですね。
これを用いて、DPする。
$DP[i][j]$で、高橋君が$i$回操作したとき、青木君は最低でも何本草を刈らねばいけないか、とする。
$i$が変わらないところは、1ずつ増えていく感じで。$i$が増える方向の遷移は、事前に用意した配列を使えばできます。
0 件のコメント:
コメントを投稿