問題
問題文
高橋君は $2$ つの正の整数 $A$ と $B$ を持っています。
それらの和が $N$ であると分かっているとき、 $A$ の各位の和と $B$ の各位の和の合計として考えられる最小の値を求めてください。
制約
・$2 \le N \le 10^5$
・$N$ は整数
収録されている問題セット
回答
回答1 (AC)
問題文が少し理解しにくいですが、要は整数 n を2つの整数の和 a+b と表した時に、a と b の各桁の値の和の最小値を求めなさいということです。処理としては、変数 a を $1$ から順番に増大させ、整数 n を a+b に分割し、a と b の各桁の和を計算し、その最小値を求めれば良いでしょう。なお、a+b と b+a の各桁の和は同じなので、変数 a は $1$ から $n/2$ まで変化させれば十分です。計算量は $O(N/2)$ です。
コードでは各桁の和を計算する際に変数の値を変更してしまうので、変化させる変数 a に対し、分割には変数 aa と bb を使用しました。コードは以下のようになりました。
agc025a-1.cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int dmin = 10e8;
for ( int a=1; a<n/2+1; a++ ) {
int aa = a, bb = n-aa, sum = 0;
while ( aa>0 ) {
sum += aa%10;
aa /= 10;
}
while ( bb>0 ) {
sum += bb%10;
bb /= 10;
}
dmin = min( dmin, sum );
}
cout << dmin << endl;
}
aa と bb の各桁の合計を計算する処理を関数にすることもできますが、処理内容が簡単なため、上では関数を使用しませんでした。
調べたこと
AtCoder の解説 → コンテスト全体の解説
上記回答のようにループを回す必要がなく、最小になる場合があらかじめ求められるとのことでした。これなら計算量 $O(1)$ なので、一瞬ですね。なるほど。