提出 #70622350

---

ソースコード 拡げる

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            String s = sc.next();
            if (n <= 10) {
                @SuppressWarnings("unchecked")
                Set<Integer>[] sets = new Set[n];
                for (int i = 0; i < n; i++) sets[i] = new HashSet<Integer>();
                int[] nums = new int[n];
                for (int i = 0; i < n; i++) nums[i] = i + 1;
                generatePerms(nums, 0, s, sets);
                for (int i = 0; i < n; i++) {
                    System.out.print(sets[i].size());
                    if (i < n - 1) System.out.print(" ");
                }
                System.out.println();
            } else {
                int[] min = new int[n + 1], max = new int[n + 1];
                Arrays.fill(min, 1);
                Arrays.fill(max, n);
                boolean changed = true;
                while (changed) {
                    changed = false;
                    for (int i = 0; i < n - 1; i++) {
                        int a = i + 1, b = i + 2;
                        if (s.charAt(i) == 'R') {
                            int newMin = Math.max(min[b], min[a] + 1);
                            int newMax = Math.min(max[a], max[b] - 1);
                            if (newMin != min[b] || newMax != max[a]) {
                                min[b] = newMin; max[a] = newMax; changed = true;
                            }
                        } else {
                            int newMin = Math.max(min[a], min[b] + 1);
                            int newMax = Math.min(max[b], max[a] - 1);
                            if (newMin != min[a] || newMax != max[b]) {
                                min[a] = newMin; max[b] = newMax; changed = true;
                            }
                        }
                    }
                    for (int i = n - 2; i >= 0; i--) {
                        int a = i + 1, b = i + 2;
                        if (s.charAt(i) == 'R') {
                            int newMin = Math.max(min[b], min[a] + 1);
                            int newMax = Math.min(max[a], max[b] - 1);
                            if (newMin != min[b] || newMax != max[a]) {
                                min[b] = newMin; max[a] = newMax; changed = true;
                            }
                        } else {
                            int newMin = Math.max(min[a], min[b] + 1);
                            int newMax = Math.min(max[b], max[a] - 1);
                            if (newMin != min[a] || newMax != max[b]) {
                                min[a] = newMin; max[b] = newMax; changed = true;
                            }
                        }
                    }
                }
                int[] result = new int[n + 1];
                for (int num = 1; num <= n; num++) {
                    if (min[num] <= max[num]) {
                        for (int pos = min[num]; pos <= max[num]; pos++) {
                            result[pos]++;
                        }
                    }
                }
                for (int i = 1; i <= n; i++) {
                    System.out.print(result[i]);
                    if (i < n) System.out.print(" ");
                }
                System.out.println();
            }
        }
        sc.close();
    }
    
    static boolean isValid(int[] arr, String s) {
        int[] pos = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) pos[arr[i]] = i;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'R') {
                if (pos[i + 2] <= pos[i + 1]) return false;
            } else {
                if (pos[i + 2] >= pos[i + 1]) return false;
            }
        }
        return true;
    }
    
    static void generatePerms(int[] nums, int start, String s, Set<Integer>[] sets) {
        if (start == nums.length) {
            if (isValid(nums, s)) {
                for (int i = 0; i < nums.length; i++) sets[i].add(nums[i]);
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            generatePerms(nums, start + 1, s, sets);
            swap(nums, start, i);
        }
    }
    
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
    }
}

提出情報

ジャッジ結果