\(7 \times 11\) の板チョコを持っているとき、以下のいずれかの条件を満たす場合は答えが絶対に No になります。空欄を埋めてください。

• \(1 \times 1\) 以上の板チョコを合計面積 \(??\) 以上渡す必要がある
• \(2 \times 2\) 以上の板チョコを合計面積 \(??\) 以上渡す必要がある
• \(4 \times 4\) 以上の板チョコを合計面積 \(??\) 以上渡す必要がある

\(7 \times 11\) の板チョコを持っているケースを考えます。Hint 1 の 3 条件をすべて満たさない場合、答えはどうなりますか。

Hint 1, 2 の考察を、一般の \(H, W\) に応用してみましょう。

\(K = 1\) の場合、答えがどうなるかを考えてみましょう。

\(K = 2\) の場合、答えがどうなるかを考えてみましょう。

\(K = 3\) の場合、答えがどうなるかを考えてみましょう。

Hint 1, 2, 3 の考察を、一般の \(K\) について応用してみましょう。

投票者 \(1\) が \(t\) 番目に投票するとします。\(t = 1, 2, \dots, N\) と動かしたとき、以下はどのように変化しますか。

• 開票結果の列の \(1\) 文字目
• 開票結果の列の \(2\) 文字目
• 開票結果の列の \(3\) 文字目 (以下同様)

いきなり元の問題を解くのは難しいので、まずは全点対のユークリッド距離を同じにしたい場合について考えてみましょう。特に、以下の問題について考えてみましょう。

• \(N = 3\)
• \(d(p_1, p_2) = d(p_1, p_3) = d(p_2, p_3)\)

Hint 1 の答えを少しだけずらすことで、以下の条件を満たすようにしてみましょう。

• \(N = 3\)
• \(d(p_2, p_3) < d(p_1, p_3) < d(p_1, p_2)\)

Hint 1, 2 の考察を \(N \geq 4\) の場合に応用してみましょう。

実は、制約を満たすどのような \(X\) についても、\(n^n \mod 10^9 = X\) となるような \(0\) 以上 \(10^9\) 未満の整数 \(n\) は \(1\) つだけ存在します。

実は、Hint 1 だけでなく、以下の性質が成り立ちます。

• \(\mathrm{gcd}(X, 10^2) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^2)\) についても、\(n^n \mod 10^2 = X\) となる \(0\) 以上 \(10^2\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^3) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^3)\) についても、\(n^n \mod 10^3 = X\) となる \(0\) 以上 \(10^3\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^4) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^4)\) についても、\(n^n \mod 10^4 = X\) となる \(0\) 以上 \(10^4\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^5) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^5)\) についても、\(n^n \mod 10^5 = X\) となる \(0\) 以上 \(10^5\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^6) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^6)\) についても、\(n^n \mod 10^6 = X\) となる \(0\) 以上 \(10^6\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^7) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^7)\) についても、\(n^n \mod 10^7 = X\) となる \(0\) 以上 \(10^7\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^8) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^8)\) についても、\(n^n \mod 10^8 = X\) となる \(0\) 以上 \(10^8\) 未満の整数 \(n\) は \(1\) つだけ存在する
• \(\mathrm{gcd}(X, 10^9) = 1\) を満たすどのような \(X\) \((0 \leq X < 10^9)\) についても、\(n^n \mod 10^9 = X\) となる \(0\) 以上 \(10^9\) 未満の整数 \(n\) は \(1\) つだけ存在する

Hint 2 をもとに、整数 \(n\) を下の桁から順に確定させていきましょう。

\(N = 20\) として、以下の \(2\) つの問題を解いてみましょう。

• XXXYXYYXXXYXXXXYYXXY の状態で交差点 \(1\) から \(39\) までのウォーキングを行った後の状態は何か
• XXXYXYYXXXYXXXXYYXXY の状態で交差点 \(13\) から \(28\) までのウォーキングを行った後の状態は何か

Hint 1 の \(2\) つの問題について、それぞれ開始状態と終了状態の文字列を比較してみましょう。一体何が起こっているでしょうか。

有名な「編集距離の問題」を思い出してください。よく似ていませんか？