🔖

Kickstart 2022 RoundA: Challenge nine

2022/03/26に公開

C++

algorithm

kickstart

tech

問題

正の整数Nが与えられる。Nのどこかに一桁追加して、９の倍数である新しい数を作る。そのような数のうち、最も小さい値を求める。

アルゴリズム

問題の通りの操作を実行して生成した数を一つずつチェックする方法でも、Test set1であれば $1 \lt N \lt 10^5$ で、挿入する値も１０通り（0から９）のため、桁数x１０通りの計算で結果を求めることが出来る。Test set2では $1 \lt N \lt 10^{123456}$ となり、時間内に計算が出来ないので、別の方法が必要。ある数が９の倍数ということは、その数の全ての桁の和が９の倍数という性質を使えば、挿入する値をすぐに決めることが出来る。すでに9の倍数だった場合は、9か０のどちらかを足せば良いですが、答えを最小にするために０を選びます。求めた値を挿入する場所ですが、most significant digitから順に探して、挿入する値よりも大きい値が現れた位置に挿入します（2562に３を挿入する場合、32562 or 23562 or 25362 or 25632 or 25623で、23562が最小になるので、挿入位置は確かに正しそうです）。挿入する値、挿入場所、挿入後の値の計算はNの桁数をLとするとO(L)で、全体としてO(L)の計算量です。Note： pythonでは同じアルゴリズムでもTest set2でTLEとなりました。

#include <bits/stdc++.h>

using namespace std;

int which_digit_to_insert(string &s)
{
    int sum = 0;
    for (int i = 0; i < s.size(); ++i)
    {
        sum += int(s[i] - '0');
    }
    if (sum % 9 != 0)
    {
        return 9 - sum % 9;
    }
    else
    {
        return 0;
    }
}

vector<int> get_digits(string &s, int L)
{
    vector<int> digits;
    for (int i = 0; i < L; ++i)
    {
        digits.push_back(int(s[i] - '0'));
    }
    return digits;
}

int where_to_insert(string &s, int d)
{
    int k = 0;
    int L = s.size();
    vector<int> digits = get_digits(s, L);
    for (int i = 0; i < L; ++i)
    {
        if (digits[i] > d)
        {
            break;
        }
        k++;
    }
    if (d == 0 && k == 0)
    {
        k += 1;
    }
    return k;
}

string insert_digit_str(string &s, int d, int k)
{
    string before = s.substr(0, k);
    string after = s.substr(k);
    return before + to_string(d) + after;
}

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t < T + 1; ++t)
    {
        string s;
        cin >> s;
        int d = which_digit_to_insert(s);
        int k = where_to_insert(s, d);
        cout << "Case #" << t << ": " << insert_digit_str(s, d, k) << endl;
    }
}

問題

アルゴリズム

Discussion