Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

自作問題 「Stone Cleaner」

misteer.hatenablog.com

上の記事を書いている際に、以下のような問題に直面した。

 \{b_i\}に対して、「異なる2要素から 1ずつ引く」という操作を考える。この操作を繰り返すことで \{b_i\}を全て 0にできるとき、 \{b_i\}は「良い数列」である。


この問題を一般化したらどうなるか?ということで、以下の問題を考えた。


問題

 N枚の皿があり、 i番目の皿には a_i個の石が入っている。

以下の操作を何度か繰り返すことで、全ての皿に石が乗っていない状態にできるか判定せよ。

  • 少なくとも石が1個入っている皿を K枚選ぶ。
  • 選んだ K枚の皿から石を1つずつ取り除く。
    • 石が入っている皿が K枚ない場合は操作を行うことはできない。

制約

  •  1 \leq K \leq N \leq 10^5
  •  1 \leq a_i \leq 10^9


解説

結論を言うと、判定条件は以下の2条件が共に成り立つことと同値である。

  •  \sum a_i Kの倍数
  •  \max (a_i) \cdot K \leq \sum a_i

直感的には、後者は「石が程々にバランスよく乗っている」という条件と言える。


まずは必要性、つまり「2条件の一方でも成立しなければ不可能であること」を示す。

前者の必要性は、1回の操作でちょうど K個の石が取り除かれることから分かる。

後者の必要性を示す。 a_j \gt \frac{\sum a_i}{K}なる jが存在したとする。このとき j枚目の皿は a_j回選ぶ必要があるため、操作は少なくとも a_j回必要となる。 a_j \cdot K \gt \frac{\sum a_i}{K} \cdot K = \sum a_iより取り除かれるべき石の数は \sum a_i個を上回るが、これは不可能である。


次に十分性、つまり「2条件が共に成立していれば常に可能であること」を示す。

これは、「石の多い方から K枚の皿を選ぶ」という貪欲的な戦略によって達成できる。これを x = \frac{\sum a_i}{K}による数学的帰納法で示す。 \max (a_i) \cdot K \leq \sum a_iより常に \max (a_i) \leq xであることに注意。

 x = 0のときは \sum a_i = 0なので既に条件は達成されている。

 x = m  (m \geq 0)にて常に達成できると仮定する。 x = m + 1のとき、以下の場合分けをする。

  •  \max(a_i) \lt m + 1のとき

    操作後は \max(a_i) \leq m x = \frac{\sum a_i}{K} = mとなるので x = mの場合に帰着される。

  •  \max(a_i) = m + 1のとき

     \max (a_i) \cdot K \leq \sum a_iという条件より、 a_j = m + 1なる jは高々 K個。よって1回の操作で \max(a_i)は確実に1減り、上のケースと同様に x = mの場合に帰着される。

以上で十分性も示された。 \hspace{2ex} \square


感想

  • 非直感的な帰納法で、飲み込むのに時間がかかった。
  • 実験も困難だし、どうやったら上手く気づけるだろうか。
  • Twitterにて解答を送ってくださった方々、ありがとうございました。