AtCoder Grand Contest 030 B 「Tree Burning」

問題文

B - Tree Burning

 

Editorialが何を言っているのかわからなくて困ってたら、Codeforcesの記事のコメントに出会って救われたのでメモ。

 

結論から言えば、最適な動き方は、「はじめて進む向きを変えたあとは燃やしていない木に出会うたびに進む向きを変える」というものになる。以下では、この理由を説明する。

最後に燃やす木Xというものを固定してみる。そうすると残りの木は、家から木Xまで時計回りに進むときに出会うグループと、家から木Xまで反時計周りに進むときに出会うグループに分類できる。

f:id:Div9851P:20190101213758p:plain

図1 木を二つにグループに分類した

図1を見ると、赤のグループの木を燃やしたら次は青のグループの木を燃やす、というように交互に燃やしていくのが最適だとわかる。

 

赤のグループ、青のグループに含まれる木のうち、それぞれk本の木で、燃やしたあとに進む向きを変えるとする。例えばk=3のときは、図2のような動き方がある(番号順に燃やしていく)。このとき、進む距離は(家から、進む向きを変える木までの距離の和)×2+(家から木Xまでの距離)になるので、それぞれのグループのうち家から遠い方からk本を選ぶべきであることがわかる。また、kは大きければ大きいほどいいので、k=min(赤に含まれる木の本数,青に含まれる木の本数)とすべきこともわかる。

f:id:Div9851P:20190101221203p:plain

図2 k=3のときの例

ところで、k=min(赤に含まれる木の本数,青に含まれる木の本数)とし、それぞれのグループのうち家から遠い方からk本を選んだとき、どういう動き方になるだろうか?これは、図2からもわかるように、「はじめて進む向きを変えたあとは燃やしていない木に出会うたびに進む向きを変える」という動き方になる。こうして、何故この動き方が最適なのか、という謎が解決した。

実は赤のうちk本で進む向きを変え、青のうちk+1本で進む向きを変える、等のケースもあるのだが、本質は同じなので簡単のため無視した。

「最後に燃やす木を固定する」というのが鍵になっていて、これさえ出来ればあとはひらめかなくてもちゃんと考えれば解法にたどり着けたはず。実験をしてわかるのも重要だけど、汎用的なアイディアがあると嬉しそうなので説明してみた。