問題リンク 解説 問題の要旨を見ればわかると思いますが、すべての注文について、「どの店が一番注文先に近いか」を求めることができればよいです。 円環なので少し実装が煩雑になりますが、これは店の位置をソートして二分探索してやればよいです。 ここか…

問題リンク 解説 動的計画法の問題です。 たとえば、 を 日目に、前日店 で買い物をし、そこでは 日連続で買い物をしている、という場合の最小の合計金額とすると、 で解くことができます。 このように、最終的な最適解が、条件を絞れば途中まででも必ず最適…

問題リンク 解説 蟻本にもほぼ同じ問題が載っていることで有名です。 解法の説明はおそらくそちらの方が詳しいので、そちらを参照していただければ良いと思います。 2本の矢を投げて作れる点数を で列挙しソートしたあとに、それらを探索しながら「和が を超…

問題リンク 解説 問題文中にもあるように、 が小さいことを利用します。 まず、行の裏返し方を全探索した上で、列の裏返し方を考えます。 行の裏返し方が決まっていれば、各列について、裏返すべきかそうでないかは一意に定まります。表になるおせんべいが多…