外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

V - Sandbox

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、trueryob

配点 550 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

別のねこが最後に通過した時間より、最後に掃除された時間が後であることが、ねこがその線を通過可能である必要十分条件です。

通る線と重なっている、平行な線(11本)と垂直な線(NN本)について考えます。

平行な線の最後の掃除時間が、他すべて(N+1N+1本)の線の最後の通過時間より後であるとき、明らかに達成可能です。

そうでないとき、垂直な線の最後の掃除時間が、それぞれ、すべてそれらの最後の通過時間より後であり、尚且つ、その最後の掃除時間の最古が、平行な線の最後の通過時間より後であるとき、達成可能です。

ほかの場合は、通過ができません。

これは、例えば、セグメント木を44本活用することで解くことができます。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。