Maximise Concatnated Number

解法

左から順に、結合した文字列が表す整数を最大にするように選ぶ貪欲法で解けます。 ただし、すでに選んだ部分に非ゼロの数字が含まれるかどうかで、比較方法が変わります。

まだ非ゼロの数字が現れていない場合

ここまでに選んだ文字はすべて先頭の余分な 0 になるため、今回の候補も先頭の 0 を除いて比較します。

先頭の 0 を除いた後は、次の基準で選べます。

• 長さが異なるなら、長い方を選ぶ。
• 長さが同じなら、辞書順で大きい方を選ぶ。

たとえば 002 と 3 なら、2 と 3 を比較して 3 を選びます。 すべての文字が 0 である候補は、空文字列として扱います。

すでに非ゼロの数字が現れている場合

この場合、今回の候補の先頭にある 0 も、答えの桁数に数えられます。 そのため、先頭の 0 を除かずに、長さを優先し、同じ長さなら辞書順で比較します。

たとえば、ここまでに作った文字列が 3 で、次の候補が 1 と 01 なら、結合後はそれぞれ 31 と 301 です。 したがって、長い方の 01 を選びます。

正当性の証明

まず、途中までに作った整数を大きくする選択が、その後の選択によって不利にならないことを示します。

途中までの整数が $p$ と $q$ で、$p \ge q$ とします。 この後に同じ文字列 $S$ を結合し、その長さを $m$、整数としての値を $s$ とすると、結合後の値はそれぞれ

$$p \times 10^m + s,\qquad q \times 10^m + s$$

です。 $p \ge q$ より、

$$p \times 10^m + s \ge q \times 10^m + s$$

が成り立ちます。 したがって、途中までの整数が最大となる選び方だけを残して構いません。

次に、今回の選択によって途中までの整数を最大にする方法を考えます。

ここまでの値が $0$ なら、結合後の値は今回選ぶ文字列の整数としての値と等しくなります。 よって、先頭の 0 を除き、長さ、辞書順の順に比較すれば最大の値を選べます。

ここまでの値が正なら、その桁数を $d$、今回選ぶ文字列の長さを $\ell$ とすると、結合後の桁数は $d+\ell$ です。 したがって、長い文字列を選ぶ方が大きな値になります。 長さが同じ場合は、すでに選んだ部分が共通なので、今回の文字列が辞書順で大きい方を選べばよいことになります。

以上より、各位置で述べた比較を行うことで、途中までの整数を常に最大に保てます。 最後まで処理した結果が、求める最大値です。

実装方法

答えを文字列 ans として持ち、最初は空文字列にします。

各位置で、次の処理を行います。

1. ans が空なら、両方の候補から先頭の 0 をすべて除く。
2. 長さが長い方を選び、同じ長さなら辞書順で大きい方を選ぶ。
3. 選んだ文字列を ans の末尾に追加する。

ans が空であることは、まだ非ゼロの数字を選んでいないことを表します。 最後まで空のままなら、答えとして 0 を出力します。

答えは最大 $10N$ 桁になるため、整数型に変換せず文字列のまま扱います。

計算量

各文字列の長さの上限を $L$ とします。 各位置で行う比較と追加には $O(L)$ 時間かかるため、1 テストケースあたりの時間計算量は $O(NL)$ です。 列 $A$ と答えを保存する空間計算量も $O(NL)$ です。

この問題では $L=10$ なので、いずれも $O(N)$ です。

実装例（C++17）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<string> A(N);
        for (auto& s : A) cin >> s;

        string ans;
        ans.reserve(10 * N);

        for (int i = 0; i < N; ++i) {
            string x = A[i], y;
            cin >> y;

            if (ans.empty()) {
                // 全文字が '0' の場合は空文字列になる。
                x.erase(0, x.find_first_not_of('0'));
                y.erase(0, y.find_first_not_of('0'));
            }

            if (x.size() < y.size() ||
                (x.size() == y.size() && x < y)) {
                x.swap(y);
            }

            ans += x;
        }

        cout << (ans.empty() ? "0" : ans) << '\n';
    }
}