Official

E - Digit Sum Divisible 2 Editorial by Nyaan

まず、この問題のような「条件を満たすものを構築して出力せよ」という問題は、構築 (または構成, 英語では constructive problem) というジャンル名で呼ばれています。構築問題はある種の閃きを要求する問題なので、通常の問題との違いに戸惑った方もいるかもしれませんし、逆にパズルに慣れている人はいつもより解きやすく感じたのではないかと思います。

この問題は閃き要素の大きい問題なので、 解法を考えたい読者のためにヒント形式で解説を書きます。

ヒント1 まず、$a + 1 \leq 2N$ という制約がない場合を考えてみます。どのような数が双子の良い整数になりますか？
分からない方は $(2024, 2025)$ が双子の良い整数になる仕組みを応用することを考えてみましょう。

ヒント2 $(2024, 2025)$ が双子の良い整数である仕組みを考えると、
  • $2024$ の桁和が $8$ で $2025$ の桁和が $9$ である。
  • $8$ の倍数判定は下 $3$ 桁が $8$ の倍数かどうかで判定できる。
  • $9$ の倍数判定は桁和が $9$ の倍数かどうかで判定できる。
  • 倍数判定法により $(2024,2025)$ は双子の良い整数であるとわかる。
という仕組みになります。

ヒント3 倍数判定法を考えると、一般に桁和が $1, 3, 9$ の正整数は良い整数になります。よって例えば
  • $a=(桁和が 2 である偶数)$, $a+1=(桁和が 3 である整数)$ や
  • $a=(桁和が 8 である 8 の倍数)$, $a+1=(桁和が 9 である整数)$
は双子の良い整数になります。これを利用しましょう。

ヒント4 例えば次のような整数の組は双子の良い整数になります。
  • $B$ を $3$ 以上の整数として、
    • $(2 \times 10^B + 24, 2 \times 10^B + 25)$
    • $(2 \times 10^B, 2 \times 10^B + 1)$
    • $(35 \times 10^B, 35 \times 10^B + 1)$
    • $(8 \times 10^B, 8 \times 10^B + 1)$
      $\vdots$
すなわち、上の方の桁で桁和を調整して、後ろに $0$ をたくさん並べて末尾を偶数 or $8$ の倍数にすればよいです。

ヒント5 いくつかの構築を思いついたら、それらを上手く組み合わせましょう。


解法 まず、$N \lt 10^6$ の場合は $N \leq a \leq 2N-1$ の範囲の $a$ を全探索することにします。計算量は $\mathrm{O}(N \log N)$ で十分高速に動作します。
以降では $N \geq 10^6$ の場合を考えます。倍数判定法を考えると、一般に桁和が $1, 3, 9$ の正整数は良い整数になることがわかります。よって、
  • $a=(桁和が 2 である偶数)$, $a+1=(桁和が 3 である整数)$ や
  • $a=(桁和が 8 である 8 の倍数)$, $a+1=(桁和が 9 である整数)$
は双子の良い整数になります。
これを利用すると、「上の方の桁で桁和を調整して、後ろに $0$ をたくさん並べる」という方法で巨大な良い整数の組をいくつか構築できることがわかります。具体的には、
  • $B$ を $3$ 以上の整数として、
    • $(2 \times 10^B, 2 \times 10^B + 1)$
    • $(35 \times 10^B, 35 \times 10^B + 1)$
    • $(62 \times 10^B, 62 \times 10^B + 1)$
    • $(107 \times 10^B, 107 \times 10^B + 1)$
      $\vdots$
は常に双子の良い整数になります。 あとは $N$ の値に応じて適切な双子の良い整数を出力すればよいです。具体的には $N$ の上 $2$ 桁を $x$ として、
  • $10 \leq x \leq 16$ の時 : $(17 \times 10^B, 17 \times 10^B + 1)$
  • $17 \leq x \leq 25$ の時 : $(26 \times 10^B, 26 \times 10^B + 1)$
  • $26 \leq x \leq 34$ の時 : $(35 \times 10^B, 35 \times 10^B + 1)$
  • $35 \leq x \leq 61$ の時 : $(62 \times 10^B, 62 \times 10^B + 1)$
  • $62 \leq x \leq 99$ の時 : $(107 \times 10^B, 107 \times 10^B + 1)$
を $(a, a+1)$ とすれば、$N \leq a \leq 2N-1$ となるように $B$ を選ぶことが必ず可能です。なお、あらかじめ $N \geq 10^6$ に限定しているため $10^B$ が必ず $8$ の倍数になる仕組みになっている点に留意してください。以上の内容を適切に実装すればこの問題を解くことができて、十分高速に動作します。

なお、この問題は想定解以外にも様々な解法が考えられると思います。例えば「末尾に $0$ が続いて、それ以外の桁は数桁を除いてほとんどの桁が $0$ であるような $a$ のみを候補として(ランダムあるいは決定論的に)探索する」という解法も考えられます。これは
  • 桁和が $d$ ($d$ は $2,3,5$ の倍数でない)の時はおよそ $1/d$ の確率で $d$ の倍数になるから、$d$ を可能な限り小さくした方が良いだろう
  • 桁和が $2, 5$ の倍数の場合に備えて末尾は $0$ の方が良いだろう
という予想に基づいたヒューリスティック的な解法です。 このように良い整数の性質に基づいて適切な探索を行えば、想定解のように実際に解を構築せずとも AC を得ることが可能でしょう。

posted:
last update: