1回の手紙を持っていくのに途中で曲がるのは無駄なので縦移動か横移動しかない、ということを考察してDPを考え、 DPをSegment Treeで高速化するテクがこんな時代からIOIに出ていたとは…… AtCoderをみると他の人300ms弱とかで通しているのですが、こんな実行…