Codeforces Round #311 Div2 E: Ann and Half-Palindrome
解法
半回文の文字列の洗い出しと、K番目の文字列の探索は、各で求めることができるので時間内に終わる。
しかし、kmjpさんのコードを写経してみたところJavaでは時間内に終わらなかったため、時間を計測してみたところ、ArrayDequeにaddする時に非常に多く時間が使われていることが分かった。
そこでMyDequeとして必要最小限の実装を行ったところ、うまく時間内に収まった。(10倍速くなった)
コード
import java.util.Scanner; public class Main { public void solve() { Scanner scanner = new Scanner(System.in); char[] string = scanner.next().toCharArray(); int K = scanner.nextInt(); scanner.close(); int L = string.length;// 文字列の長さ // dp[i][j]:= iからjまでの部分文字列が半回文かどうか boolean[][] dp = new boolean[L][L]; // deques[x]:= xを始点にした半回文が長さ順に並んでいる MyDeque[] deques = new MyDeque[L]; for (int i = 0; i < L; i++) { deques[i] = new MyDeque(L); } // 短い方から半回文を列挙する for (int length = 0; length < L; length++) { for (int x = 0; x + length < L; x++) { int y = x + length; if (string[x] == string[y] && (length <= 3 || dp[x + 2][y - 2])) { dp[x][x + length] = true; deques[x].add(y); } } } StringBuilder ans = new StringBuilder(); for (int i = 0; i < L; i++) { // i文字目を決める int finished = 0;// 解答の文字列とi-1文字目まで同じで、長さがi-1の文字列の数 int a = 0;// i文字目が 'a' となる文字列の合計 for (int x = 0; x < L; x++) { if (deques[x].isEmpty()) { continue; } if (deques[x].peek() < x + i) { // i文字より小さい文字列は削除しておく finished++; deques[x].poll(); } if (!deques[x].isEmpty() && string[x + i] == 'a') { a += deques[x].size(); } } if (K <= finished) { break; } K -= finished;// 終末に達してしまった文字列は除外する if (K <= a) { // i文字目がaとなる場合 ans.append('a'); // i文字目が 'b'となる文字列は、もう候補になりえないので全て削除する for (int x = 0; x + i < L; x++) { if (!deques[x].isEmpty() && string[x + i] == 'b') { deques[x].clear(); } } } else { // i文字目がbとなる場合 K -= a;// i文字目がaの文字列の文も引いておく ans.append('b'); // i文字目がaとなる文字列は全て削除する for (int x = 0; x + i < L; x++) { if (!deques[x].isEmpty() && string[x + i] == 'a') { deques[x].clear(); } } } } System.out.println(ans.toString()); } public static void main(String[] args) { new Main().solve(); } } // ArrayDequeを自分で作る class MyDeque { int[] nums; int size, cur; public MyDeque(int N) { this.nums = new int[N]; this.size = 0; this.cur = 0; } public void add(int a) { nums[size] = a; size++; } public int poll() { if (size == 0) { return -1; } cur++; size--; return nums[cur - 1]; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public int peek() { if (size == 0) { return -1; } return nums[cur]; } public void clear() { size = 0; cur = 0; } }