考察
桁和を8にそろえ、末尾に0を並べると、8で割り切れ、1を足した数も桁和9で割り切れる整数を作れる。あとは上位桁を選び、指定された範囲に収めればよい。小さい入力は全探索し、大きい入力をこの構成で解く。
小さい入力は候補をすべて調べる
求めるのは、整数 と がそれぞれ自身の桁和で割り切れ、 かつ を満たす組である。出力するのは だけでよい。
まず なら、 を順に調べる。各候補について二つの桁和を計算し、両方の割り算の余りが0なら、その を出力して終了する。最後まで見つからなければ -1 を出力する。候補は 個、調べる数も最大7桁なので、この範囲は直接処理できる。例えば では の全候補が失敗し、答えは -1 となる。
一方、入力は最大10万桁にもなるので、常に数値へ変換して全探索することはできない。以降は とし、桁の形を決めて必ず一つ作る。
桁和と末尾から、割り切れる形を作る
連続する二数を同時に扱う手掛かりは、問題文の例 にある。前者の桁和は8、後者は9である。8の倍数かどうかは下3桁で決まり、9の倍数かどうかは桁和で決まる。この組合せを使えば、巨大な整数全体で割り算をしなくても条件を保証できそうだ。
そこで、桁和が8の正整数 を上位桁として選び、その後ろに 個の0を付けた
を考える。 なら下3桁が000なので、 は8の倍数であり、桁和8で割り切れる。また、末尾が0なので1を足しても繰り上がりはなく、 の桁和は9になる。整数はその桁和と9で割った余りが等しいから、 も9で割り切れる。
これで割り切り条件は満たせた。残る自由度である と を、出力範囲に合わせて決める。
先頭二桁の区間を五つの候補で覆う
の桁数を 、先頭二桁を整数 とし、 と置く。すると で、
が成り立つ。 の残りの桁を見ずに範囲を保証するには、 をこの区間の右端以上、左端の2倍未満に置けばよい。つまり
を満たす、桁和8の を探す。
例えば は を覆うが、 では下限を保証できなくなる。次の候補として を使えば、 を覆える。同様に候補をつなぐと、次の表になる。
各候補の桁和は8で、表の区間は から まで途切れずに続く。各行で、区間の右端に1を足した値が 以下、左端の2倍が より大きいことを確認できる。例えば4行目では 、 なので、行内のすべての に対して必要な不等式が成り立つ。
手順は、入力を文字列として受け取り、7桁以上なら先頭二文字だけを整数 に変換する。表から を選び、その十進表記の後ろに 個の0を付けて出力すればよい。この場合は より なので、8の倍数にするための0も十分にある。
例えば なら 、、 で、出力は 10700000 となる。 は三桁でもよく、この場合は出力が入力より一桁長くなる。
典型の発動条件
constructive problemの有限パターン被覆
発動条件: 巨大な範囲から一例だけ求め、局所条件を末尾の形で保証できるとき。
末尾など一部の桁を固定して条件を満たし、残した上位桁の自由度で範囲を調整する。少数の候補で済ませるには、各候補が使える入力区間を求め、すべての区間を覆うことまで証明する。
桁和と倍数判定
発動条件: 桁和や連続する整数の割り切り条件が現れ、10進表記の規則性を使えるとき。
9の倍数性は桁和、8の倍数性は下3桁だけで判定できる。1を足す前後の桁和も使うなら、繰り上がりが起こるかを先に確かめる。
問題固有の要素
桁和8の上位桁として を使うと、先頭二桁の全範囲を覆える。桁和8と9の組を選ぶこと、これらの候補で覆えることが今回の構成の要点である。
巨大な整数を文字列として扱い、上位桁で大小範囲を、末尾の0で割り切り条件を満たす。同じ形を別の問題へ使うときも、それぞれの条件を分けて確認する。
正当性
の場合、範囲条件は整数 に対して と同値である。この全候補を調べ、二数がそれぞれ自身の桁和で割り切れる場合だけ出力するので、見つけた答えは有効であり、全候補が失敗した場合に限り -1 を返す。
の場合、表は先頭二桁 のすべてを覆い、選んだ は を満たす。従って、構成した について
かつ
である。 と は整数なので、後者の厳密不等式から も従う。よって二つの範囲条件を満たす。
さらに の桁和は8であり、 個の0を付けても桁和は変わらず、下3桁が000なので は8で割り切れる。 は繰り上がりなく桁和9となるので9で割り切れる。従って両数とも良い整数であり、大きい入力には必ず有効な答えを出力できる。
実装上の注意
- 分岐は入力文字列の長さで決められる。6桁以下なら数値へ変換して全探索し、7桁以上なら構成する。巨大な入力全体や を数値へ変換する必要はない。
- 小さい場合の探索上端は を含む。最小入力 では が条件を満たす。
-1 は全候補の失敗を確認してから出す。
- 表の境界は 。 の次は同じ桁数の ではなく、 の桁数が増えて 、 も1増える。
107 を選んでも付ける0は同じく 個である。出力を入力と同じ長さに切り詰めない。先頭0は付かず、最大 桁をそのまま出力する。
復習の核
- 一例だけ作ればよいときは、桁和や末尾を先に固定し、残った自由度で範囲を満たせないか考える。
- 候補の形を作れたら、「どの入力区間に使えるか」を不等式で求め、区間の切れ目と桁数が増える境界まで覆う。
- 連続する二数では、繰り上がりの有無と上端の1の差を忘れない。整数なら から へ進める。
計算量と制約
時間
入力桁数を とする。 では入力の読み込みに 、最大 候補それぞれの二数の桁和計算に かかり、全体で 。候補は 個未満、各数は最大7桁である。
では、読み込みと文字列出力を含めて 。表は固定の5行で前処理は不要であり、先頭二桁からの候補選択は 、出力文字列の生成は となる。
空間
入力文字列と、構成する最大 桁の出力文字列を含めて 。小さい場合の探索では、各候補と桁和だけを持ち、候補一覧を保存しない。
制約との対応
公式制約は 、実行時間制限2秒、メモリ制限1024 MiBである。入力は最大10万桁なので、大きい場合は文字列のまま扱う。閾値 で全探索を打ち切れば、構成側では 、 が保証され、末尾を使った8の倍数性が成立する。出力が入力より一桁長くなっても、上で示した範囲条件を満たせばよい。
出典