結果

問題 No.2734 Addition and Multiplication in yukicoder (Hard)
ユーザー ks2m
提出日時 2024-04-19 23:01:48
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,214 bytes
コンパイル時間 5,763 ms
コンパイル使用メモリ 78,540 KB
実行使用メモリ 69,384 KB
最終ジャッジ日時 2024-10-11 17:08:47
合計ジャッジ時間 15,264 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 2 TLE * 1 -- * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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) {
        if (sb.length() >= min.length()) {
            String s = sb.toString();
            if (s.compareTo(min) < 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
0