ABC 387 E — Digit Sum Divisible 2

考察

桁和を8にそろえ、末尾に0を並べると、8で割り切れ、1を足した数も桁和9で割り切れる整数を作れる。あとは上位桁を選び、指定された範囲に収めればよい。小さい入力は全探索し、大きい入力をこの構成で解く。

小さい入力は候補をすべて調べる

求めるのは、整数 aa と a+1a+1 がそれぞれ自身の桁和で割り切れ、N≤aN\leq a かつ a+1≤2Na+1\leq 2N を満たす組である。出力するのは aa だけでよい。

まず N<106N<10^6 なら、a=N,N+1,…,2N−1a=N,N+1,\ldots,2N-1 を順に調べる。各候補について二つの桁和を計算し、両方の割り算の余りが0なら、その aa を出力して終了する。最後まで見つからなければ -1 を出力する。候補は NN 個、調べる数も最大7桁なので、この範囲は直接処理できる。例えば N=21N=21 では 21≤a≤4121\leq a\leq 41 の全候補が失敗し、答えは -1 となる。

一方、入力は最大10万桁にもなるので、常に数値へ変換して全探索することはできない。以降は N≥106N\geq 10^6 とし、桁の形を決めて必ず一つ作る。

桁和と末尾から、割り切れる形を作る

連続する二数を同時に扱う手掛かりは、問題文の例 (2024,2025)(2024,2025) にある。前者の桁和は8、後者は9である。8の倍数かどうかは下3桁で決まり、9の倍数かどうかは桁和で決まる。この組合せを使えば、巨大な整数全体で割り算をしなくても条件を保証できそうだ。

そこで、桁和が8の正整数 pp を上位桁として選び、その後ろに BB 個の0を付けた

a=p⋅10Ba=p\cdot 10^B

を考える。B≥3B\geq 3 なら下3桁が000なので、aa は8の倍数であり、桁和8で割り切れる。また、末尾が0なので1を足しても繰り上がりはなく、a+1a+1 の桁和は9になる。整数はその桁和と9で割った余りが等しいから、a+1a+1 も9で割り切れる。

これで割り切り条件は満たせた。残る自由度である pp と BB を、出力範囲に合わせて決める。

先頭二桁の区間を五つの候補で覆う

NN の桁数を LL、先頭二桁を整数 xx とし、B=L−2B=L-2 と置く。すると 10≤x≤9910\leq x\leq 99 で、

x⋅10B≤N<(x+1)⋅10Bx\cdot 10^B\leq N<(x+1)\cdot 10^B

が成り立つ。NN の残りの桁を見ずに範囲を保証するには、a=p⋅10Ba=p\cdot 10^B をこの区間の右端以上、左端の2倍未満に置けばよい。つまり

x+1≤p<2xx+1\leq p<2x

を満たす、桁和8の pp を探す。

例えば p=17p=17 は 10≤x≤1610\leq x\leq 16 を覆うが、x=17x=17 では下限を保証できなくなる。次の候補として p=26p=26 を使えば、17≤x≤2517\leq x\leq 25 を覆える。同様に候補をつなぐと、次の表になる。

NN の先頭二桁 xx選ぶ上位桁 pp
10≤x≤1610\leq x\leq 161717
17≤x≤2517\leq x\leq 252626
26≤x≤3426\leq x\leq 343535
35≤x≤6135\leq x\leq 616262
62≤x≤9962\leq x\leq 99107107

各候補の桁和は8で、表の区間は 1010 から 9999 まで途切れずに続く。各行で、区間の右端に1を足した値が pp 以下、左端の2倍が pp より大きいことを確認できる。例えば4行目では 61+1=6261+1=62、62<2⋅3562<2\cdot 35 なので、行内のすべての xx に対して必要な不等式が成り立つ。

手順は、入力を文字列として受け取り、7桁以上なら先頭二文字だけを整数 xx に変換する。表から pp を選び、その十進表記の後ろに L−2L-2 個の0を付けて出力すればよい。この場合は L≥7L\geq 7 より B≥5B\geq 5 なので、8の倍数にするための0も十分にある。

例えば N=6 200 000N=6\,200\,000 なら L=7L=7、x=62x=62、p=107p=107 で、出力は 10700000 となる。pp は三桁でもよく、この場合は出力が入力より一桁長くなる。

典型の発動条件

constructive problemの有限パターン被覆

発動条件: 巨大な範囲から一例だけ求め、局所条件を末尾の形で保証できるとき。

末尾など一部の桁を固定して条件を満たし、残した上位桁の自由度で範囲を調整する。少数の候補で済ませるには、各候補が使える入力区間を求め、すべての区間を覆うことまで証明する。

桁和と倍数判定

発動条件: 桁和や連続する整数の割り切り条件が現れ、10進表記の規則性を使えるとき。

9の倍数性は桁和、8の倍数性は下3桁だけで判定できる。1を足す前後の桁和も使うなら、繰り上がりが起こるかを先に確かめる。

問題固有の要素

桁和8の上位桁として 17,26,35,62,10717,26,35,62,107 を使うと、先頭二桁の全範囲を覆える。桁和8と9の組を選ぶこと、これらの候補で覆えることが今回の構成の要点である。

巨大な整数を文字列として扱い、上位桁で大小範囲を、末尾の0で割り切り条件を満たす。同じ形を別の問題へ使うときも、それぞれの条件を分けて確認する。

正当性

N<106N<10^6 の場合、範囲条件は整数 aa に対して N≤a≤2N−1N\leq a\leq 2N-1 と同値である。この全候補を調べ、二数がそれぞれ自身の桁和で割り切れる場合だけ出力するので、見つけた答えは有効であり、全候補が失敗した場合に限り -1 を返す。

N≥106N\geq 10^6 の場合、表は先頭二桁 10≤x≤9910\leq x\leq 99 のすべてを覆い、選んだ pp は x+1≤p<2xx+1\leq p<2x を満たす。従って、構成した a=p⋅10Ba=p\cdot 10^B について

N<(x+1)⋅10B≤p⋅10B=aN<(x+1)\cdot 10^B\leq p\cdot 10^B=a

かつ

a=p⋅10B<2x⋅10B≤2Na=p\cdot 10^B<2x\cdot 10^B\leq 2N

である。aa と 2N2N は整数なので、後者の厳密不等式から a+1≤2Na+1\leq 2N も従う。よって二つの範囲条件を満たす。

さらに pp の桁和は8であり、B=L−2≥5B=L-2\geq 5 個の0を付けても桁和は変わらず、下3桁が000なので aa は8で割り切れる。a+1a+1 は繰り上がりなく桁和9となるので9で割り切れる。従って両数とも良い整数であり、大きい入力には必ず有効な答えを出力できる。

実装上の注意

  • 分岐は入力文字列の長さで決められる。6桁以下なら数値へ変換して全探索し、7桁以上なら構成する。巨大な入力全体や 2N2N を数値へ変換する必要はない。
  • 小さい場合の探索上端は 2N−12N-1 を含む。最小入力 N=1N=1 では a=1a=1 が条件を満たす。-1 は全候補の失敗を確認してから出す。
  • 表の境界は 16/17,25/26,34/35,61/6216/17,25/26,34/35,61/62。x=99x=99 の次は同じ桁数の x=100x=100 ではなく、NN の桁数が増えて x=10x=10、BB も1増える。
  • 107 を選んでも付ける0は同じく L−2L-2 個である。出力を入力と同じ長さに切り詰めない。先頭0は付かず、最大 L+1L+1 桁をそのまま出力する。

復習の核

  • 一例だけ作ればよいときは、桁和や末尾を先に固定し、残った自由度で範囲を満たせないか考える。
  • 候補の形を作れたら、「どの入力区間に使えるか」を不等式で求め、区間の切れ目と桁数が増える境界まで覆う。
  • 連続する二数では、繰り上がりの有無と上端の1の差を忘れない。整数なら a<2Na<2N から a+1≤2Na+1\leq 2N へ進める。

計算量と制約

時間

入力桁数を LL とする。N<106N<10^6 では入力の読み込みに O(L)O(L)、最大 NN 候補それぞれの二数の桁和計算に O(log⁡(N+1))O(\log(N+1)) かかり、全体で O(L+Nlog⁡(N+1))O(L+N\log(N+1))。候補は 10610^6 個未満、各数は最大7桁である。

N≥106N\geq 10^6 では、読み込みと文字列出力を含めて O(L)O(L)。表は固定の5行で前処理は不要であり、先頭二桁からの候補選択は O(1)O(1)、出力文字列の生成は O(L)O(L) となる。

空間

入力文字列と、構成する最大 L+1L+1 桁の出力文字列を含めて O(L)O(L)。小さい場合の探索では、各候補と桁和だけを持ち、候補一覧を保存しない。

制約との対応

公式制約は 1≤N<101000001\leq N<10^{100000}、実行時間制限2秒、メモリ制限1024 MiBである。入力は最大10万桁なので、大きい場合は文字列のまま扱う。閾値 10610^6 で全探索を打ち切れば、構成側では L≥7L\geq 7、B≥5B\geq 5 が保証され、末尾を使った8の倍数性が成立する。出力が入力より一桁長くなっても、上で示した範囲条件を満たせばよい。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Digit Sum Divisible 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 成立証明から構成解を復元する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 構成解・witness復元

    補助タグ: 有界全列挙・有限case分解

    執筆: abc-explanation-author1.1.1 / revision 4

    学習の位置

    体系上の位置: 成立証明から構成解を復元する

    • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

    先に読む単元:

    この解説で扱わないこと:

    • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題