以下のケースについて考えてみましょう。

• あなたは、\(10\) 円玉を \(3\) 枚、\(1\) 円玉を \(14\) 枚持っている。
• これから \(22\) 円の買い物と \(13\) 円の買い物をその順に行う。

\(22\) 円の買い物をする方法として、以下の \(2\) つがあります。どちらが上手くいくでしょうか。もう片方が上手くいかない理由も考えてみましょう。

• \(10\) 円玉 \(2\) 枚、\(1\) 円玉 \(2\) 枚を使う。
• \(10\) 円玉 \(1\) 枚、\(1\) 円玉 \(12\) 枚を使う。

Hint 1 の考え方を以下の問題に応用してみましょう。

• あなたは \(1\) 円玉と \(10\) 円玉のみを持っている。
• \(N\) 個の店で順番に \(X_1, X_2, \dots, X_N\) 円の買い物を行う。

Hint 2 の考え方を、\(1, 5, 10, 50, 100, 500\) 円すべてがある場合に応用してみましょう。

00000 の状態から 00010 の状態にする方法を考えてみましょう。

00000 の状態から 01010 の状態にする方法を考えてみましょう。以下の \(2\) つの方法のうち、どちらがやりやすいでしょうか？

• 最初に 01000 にしてから 01010 にすることを目指す
• 最初に 00010 にしてから 01010 にすることを目指す

Hint 2 の考察を使って、0000000000 の状態から 0100100100 にする方法を考えてみましょう。

\(1\) が連続する場合はどうでしょうか。0000000000 の状態から 0110001100 にする方法を考えてみましょう。

ここまでの考察を、一般のケースの場合に応用してみましょう。

入力例 1 を手で解いてみましょう。条件 1 と条件 2 を独立に考えると、解きやすいです。

条件 1 しか満たさなくて良いとき、何回の塗り替えが必要かを計算する問題について、解法を考えてみましょう。ヒントとしては、最短経路問題に帰着させることができます。

距離 \(H+1\) 以上離れている電柱は、互いに影響を及ぼさないので、別々に考えることができます。たとえば入力例 \(2\) の場合、以下の \(2\) つに分けて考えることができます。

• 電柱 \(1\) と電柱 \(3\) のグループ
• 電柱 \(2\) と電柱 \(4\) のグループ

以下の図の例について考えましょう。\(64\) 回目の地震 (図の赤の電柱) で初めてすべての電柱が倒れる確率はいくつでしょうか。

それぞれの時刻 \(t\) について、時刻 \(t\) で初めて (そのグループの) すべての電柱が倒れる確率を高速に求める方法を考えてみましょう。

以下のケースを考えてみましょう。

• コンテストの問題数は \(3\) 問である。
• 選手 \(1\) は問 \(1\) を解いた。
• 選手 \(2\) は問 \(3\) を解いた。
• 選手 \(3\) は問 \(1, 2\) を解いた。

問 \(1\) の配点が \(1\) 点であるとします。問 \(2\) の配点を \(x\) 軸、問 \(3\) の配点を \(y\) 軸にとるとき、配点と順位 (選手 \(3 \geq 1 \geq 2\) など) の関係がどうなっているか、図示してみましょう。

Hint 1 のケースでは、以下の \(2\) 通りの配点しか考える必要がありません。なぜでしょうか。

• 問 \(1\) が \(1\) 点、問 \(2\) が \(1\) 点、問 \(3\) が \(1\) 点
• 問 \(1\) が \(1\) 点、問 \(2\) が \(1\) 点、問 \(3\) が \(2\) 点

Hint 1 で書いた図の「交点となっている座標」に着目してみましょう。

実は、「問題数 \(3\) 問」のどのようなケースでも、以下の \(2\) 通りの配点しか考える必要はありません。なぜでしょうか。

• 問 \(1\) が \(1\) 点、問 \(2\) が \(1\) 点、問 \(3\) が \(1\) 点
• 問 \(1\) が \(1\) 点、問 \(2\) が \(1\) 点、問 \(3\) が \(2\) 点

Hint 3 の考察を問題数 \(5\) 問の場合にも適用させてみましょう。

空間計算量 \(O(L^3)\) の動的計画法で、この問題を解く方法について考えてみましょう。

Hint 1 の動的計画法では \(O(L^3)\) 個の状態について計算しましたが、実は \(O(L \log^2 L)\) 個の状態しか計算する必要はありません。どの状態を削れるのでしょうか。