問題

問題文

高橋君は $2$ つの正の整数 $A$ と $B$ を持っています。
それらの和が $N$ であると分かっているとき、 $A$ の各位の和と $B$ の各位の和の合計として考えられる最小の値を求めてください。

制約

・$2 \le N \le 10^5$
・$N$ は整数

収録されている問題セット

AtCoder に登録したら次にやること (第05問類題)

回答

回答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)$ なので、一瞬ですね。なるほど。

リンク

前後の記事

前の記事 → AtCoderログ：0048 - ABC 212 に参加しました