時間がかかってBまでの二完でした。その後、CやEを考えていました。振り返ると、コンテスト中に、Cはほぼ正しい解法が思い付いていたようではあるのですが……。
コンテストへのリンク
A. NEKO's Maze Game
縦、横、斜めを見て遮っている部分があるかどうか更新していく。その個数を更新する実装が分かりやすかったようです。
コンテスト中は、setに遮っているindexのpairを放り込む実装をしていました。
B. Aroma's Search
($x_i$, $y_i$)達が一直線にあるときを考えると、どこかの点に行って、右か左か一方向へ進むのが最善そう。
今回は一直線上には存在していませんが、同じように考えても問題ないです。
公式解説では、その理由として、d(i, j)を($x_i$, $y_i$)と($x_j$, $y_j$)のマンハッタン距離としたとき、d(u, v)+d(v, w)=d(u, w)となることを言っていますね。
なるほど。ちゃんと考えていませんでした。が、まあ、証明できていなくても、正しいことを考えてはいたので、まあ良いかな、という気持ち。
C. Xenon's Attack on the Gangs
0、1、……と小さい重みから重みごとに別々に考える発想ができれば、ある葉から葉までのpath上に重みを割り振ることがベストだし、重みwまで割り振った後、次の重みはそれまでに割り振ったedgeと隣接しているedgeに割り振った方が良いことが分かる。
これは、
けんちょんさんのブログの記事に詳しく書いてあります。ここまではコンテスト中に分かっていたし、だから区間DPをすればいいだろう、という方針も立っていた。問題は実装だと思う。
まず、部分木に含まれる頂点の個数が欲しい。これは、全方位木DPが必要そうに思えるけど、求めた値を全部の頂点個数から引くことで、普通の木DPで求まる。
その後、けんちょんさんの記事では、点を追加する向き（根に対して遠ざかる方向か、近付く方向か）を求めるのにLCAを使う＆再帰を使って実装しているみたい。
これは非常に関心しました。結構実装の大変な問題だと感じたけど、そういう方針でやればある程度機械的にできそう。
ただ、PyPyで通そうと思うと、logがつくと厳しそうだし、再帰を使っても多分ダメ。で、まず、向きを求める方は、
・木の辺の向きは親の方向により定まる
です。そもそも、根を一つ定めたとき、辺の向きは根へ向かう方向か、遠ざかる方向かの二通りしかない。なので、各頂点の親の頂点を記録しておけば向きも分かる。親に対する相対的な向きが欲しいので、思い付いてしまえば当たり前なのだけど、私はなかなか気付けなかった。
再帰については、普通の直線上の区間DPと同様に、幅1の区間から順番に広げていけば再帰を使わずに書ける。幅1の区間をdequeへ入れておき、BFSの要領でそこから一つずつ広げていく実装が可能。
さらに、区間両方を広げられるか試す必要はなく、片側は固定しても良い。
いわゆる考察部分はそれほど難しくないと思うけど、実装は結構大変だし、PyPyで通そうと思うと意外と辛い問題でした。