#974498 (Java) No.2734 Addition and Multiplication in yukicoder (Hard)

• 問題: No.2734 Addition and Multiplication in yukicoder (Hard)
• ユーザー: ks2m
• 提出日時: 2024-04-19 23:05:53
• 言語: Java (openjdk 23)
• 結果: WA
• 実行時間: -
• コード長: 2,324 bytes
• コンパイル時間: 3,128 ms
• コンパイル使用メモリ: 78,796 KB
• 実行使用メモリ: 81,648 KB
• 最終ジャッジ日時: 2024-10-11 17:16:36
• 合計ジャッジ時間: 14,634 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 16 WA * 2 TLE * 1 -- * 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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    static List<List<String>> list;
    static int[] idx, size;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        list = new ArrayList<>(20);
        for (int i = 0; i < 20; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            list.get(sa[i].length()).add(sa[i]);
        }
        br.close();
        size = new int[20];
        for (int i = 0; i < 20; i++) {
            size[i] = list.get(i).size();
            Collections.sort(list.get(i));
        }
        int mod = 998244353;
        StringBuilder sb = new StringBuilder();
        idx = new int[20];
        for (int i = 0; i < n - 1; i++) {
            for (int j = 19; j > 0; j--) {
                if (idx[j] < size[j]) {
                    min = list.get(j).get(idx[j]);
                    mini = j;
                    break;
                }
            }
            for (int j = mini - 1; j > 0; j--) {
                if (idx[j] < size[j]) {
                    String s = list.get(j).get(idx[j]);
                    if (s.compareTo(min.substring(0, j)) < 0) {
                        min = s;
                        mini = j;
                    }
                }
            }
            for (int j = mini - 1; j > 0; j--) {
                if (idx[j] < size[j]) {
                    StringBuilder sb2 = new StringBuilder();
                    sb2.append(list.get(j).get(idx[j]));
                    idx[j]++;
                    dfs(sb2, j);
                    idx[j]--;
                }
            }
            sb.append(list.get(mini).get(idx[mini]));
            idx[mini]++;
        }
        for (int j = 1; j < 20; j++) {
            if (idx[j] < size[j]) {
                sb.append(list.get(j).get(idx[j]));
                break;
            }
        }
        long ans = 0;
        for (int i = 0; i < sb.length(); i++) {
            int d = sb.charAt(i) - '0';
            ans *= 10;
            ans += d;
            ans %= mod;
        }
        System.out.println(ans);
    }
    static String min;
    static int mini;
    static void dfs(StringBuilder sb, int f) {
        String s = sb.toString();
        if (sb.length() >= min.length()) {
            if (s.compareTo(min) < 0) {
                min = s;
                mini = f;
            }
            return;
        } else {
            if (s.compareTo(min.substring(0, s.length())) < 0) {
                min = s;
                mini = f;
                return;
            }
        }
        for (int i = 19; i > 0; i--) {
            if (idx[i] < size[i]) {
                sb.append(list.get(i).get(idx[i]));
                idx[i]++;
                if (sb.toString().compareTo(min) < 0) {
                    dfs(sb, f);
                }
                idx[i]--;
                sb.delete(sb.length() - i, sb.length());
            }
        }
    }
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX