Submission #1777474
Source Code Expand
import java.util.*; import java.io.*; public class Main { private static IO io = new IO(); private static String S; private static char c[]; public static void main(String[] args) { int n = io.nextInt(); int k = io.nextInt(); S = io.next(); c = S.toCharArray(); Arrays.sort(c); /* * 原則なるべく小さい文字から(ソート済みのcのなるべく手前の文字から)詰めて、使用済みの文字は' 'で埋めておく * 例えば k=3, S="program" (-> agmoprr) について * 最初の3文字が"aro"で確定している状態で4文字目を考える場合 残っている文字はgmpr * まずgを入れていいかを考える * gを仮確定すると、確定している部分では1文字目がSと異なっているので、 * 残ったprog"ram"の部分について、mprをうまく並び替えて差異を2文字以内に抑えられるならgで確定していいことになる */ StringBuilder sb = new StringBuilder(); root: for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (c[j]!=' ' && count(sb, c[j]) <= k) { sb.append(c[j]); c[j] = ' '; continue root; } } } System.out.println(sb.toString()); } // Tの末尾にchを追加し、その後残った文字を適切にTに追加していったときにどうしてもSと異なってしまう文字の個数を求める private static int count(StringBuilder T, char ch) { int ans = 0; // まずはいま確定している部分だけで何箇所ズレているかカウント for (int i=0; i<T.length(); i++) { if (S.charAt(i)!=T.charAt(i)) ans++; } if (ch!=S.charAt(T.length())) ans++; // 未確定の文字をうまく並び替えたとしてもSと異なってしまう文字の数をカウント int a[] = new int[26]; // 残っている文字の個数を文字ごとに記録 for (char b:c) if (b!=' ') a[b-'a']++; // chは仮確定して上のカウントで考慮済みだから抜く a[ch-'a']--; // 未確定の文字を一つ一つ見ていき、残っている文字で埋められるなら埋め、 // 埋められないなら差異としてカウント for (int i = T.length()+1; i < S.length(); i++) { int in = S.charAt(i)-'a'; if (a[in]>0) a[in]--; else ans++; } return ans; } private static class IO extends PrintWriter { private final InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public IO() { this(System.in);} public IO(InputStream source) { super(System.out); this.in = source;} private boolean hasNextByte() { if (ptr < buflen) { return true; }else{ ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;} private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;} private static boolean isNewLine(int c) { return c == '\n' || c == '\r';} private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;} private void skipNewLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++;} public boolean hasNext() { skipUnprintable(); return hasNextByte();} public boolean hasNextLine() { skipNewLine(); return hasNextByte();} public String next() { if (!hasNext()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public char[] nextCharArray(int len) { if (!hasNext()) { throw new NoSuchElementException(); } char[] s = new char[len]; int i = 0; int b = readByte(); while(isPrintableChar(b)) { if (i == len) { throw new InputMismatchException(); } s[i++] = (char) b; b = readByte(); } return s; } public String nextLine() { if (!hasNextLine()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(!isNewLine(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) { throw new NoSuchElementException(); } long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while(true){ if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; }else if(b == -1 || !isPrintableChar(b)){ return minus ? -n : n; }else{ throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] arrayInt(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;} public long[] arrayLong(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;} public double[] arrayDouble(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;} public void arrayInt(int[]... a) {for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();} public int[][] matrixInt(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = arrayInt(m); return a;} public char[][] charMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;} public void close() { super.close(); try { in.close(); } catch (IOException ignored) {} } } }
Submission Info
Submission Time | |
---|---|
Task | C - 辞書式順序ふたたび |
User | creep04 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 100 |
Code Size | 6221 Byte |
Status | AC |
Exec Time | 93 ms |
Memory | 25172 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | hand_1_0.txt, hand_1_1.txt, hand_1_2.txt, hand_1_3.txt, hand_1_4.txt, hand_1_5.txt, hand_1_6.txt, hand_1_7.txt, hand_1_8.txt, hand_2_0.txt, hand_2_1.txt, hand_2_10.txt, hand_2_2.txt, hand_2_3.txt, hand_2_4.txt, hand_2_5.txt, hand_2_6.txt, hand_2_7.txt, hand_2_8.txt, hand_2_9.txt, hand_3_2.txt, hand_3_3.txt, hand_3_4.txt, hand_3_5.txt, hand_3_6.txt, hand_4_2.txt, hand_4_3.txt, hand_4_4.txt, hand_4_5.txt, hand_4_6.txt, random_1.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, small_8.txt, small_9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
hand_1_0.txt | AC | 69 ms | 21204 KB |
hand_1_1.txt | AC | 69 ms | 21204 KB |
hand_1_2.txt | AC | 68 ms | 18644 KB |
hand_1_3.txt | AC | 68 ms | 20564 KB |
hand_1_4.txt | AC | 68 ms | 18004 KB |
hand_1_5.txt | AC | 68 ms | 21204 KB |
hand_1_6.txt | AC | 70 ms | 22356 KB |
hand_1_7.txt | AC | 70 ms | 22996 KB |
hand_1_8.txt | AC | 68 ms | 18004 KB |
hand_2_0.txt | AC | 69 ms | 19028 KB |
hand_2_1.txt | AC | 93 ms | 18388 KB |
hand_2_10.txt | AC | 69 ms | 20564 KB |
hand_2_2.txt | AC | 68 ms | 19412 KB |
hand_2_3.txt | AC | 70 ms | 21076 KB |
hand_2_4.txt | AC | 70 ms | 22612 KB |
hand_2_5.txt | AC | 69 ms | 20052 KB |
hand_2_6.txt | AC | 69 ms | 19156 KB |
hand_2_7.txt | AC | 69 ms | 18132 KB |
hand_2_8.txt | AC | 77 ms | 21204 KB |
hand_2_9.txt | AC | 68 ms | 21332 KB |
hand_3_2.txt | AC | 67 ms | 19284 KB |
hand_3_3.txt | AC | 69 ms | 24788 KB |
hand_3_4.txt | AC | 69 ms | 19156 KB |
hand_3_5.txt | AC | 68 ms | 15828 KB |
hand_3_6.txt | AC | 69 ms | 21076 KB |
hand_4_2.txt | AC | 69 ms | 19284 KB |
hand_4_3.txt | AC | 70 ms | 25172 KB |
hand_4_4.txt | AC | 71 ms | 19796 KB |
hand_4_5.txt | AC | 69 ms | 21460 KB |
hand_4_6.txt | AC | 70 ms | 18260 KB |
random_1.txt | AC | 72 ms | 21332 KB |
random_10.txt | AC | 91 ms | 20308 KB |
random_11.txt | AC | 78 ms | 19412 KB |
random_12.txt | AC | 88 ms | 21972 KB |
random_13.txt | AC | 85 ms | 23508 KB |
random_14.txt | AC | 88 ms | 20052 KB |
random_15.txt | AC | 70 ms | 21332 KB |
random_2.txt | AC | 71 ms | 19156 KB |
random_3.txt | AC | 74 ms | 20948 KB |
random_4.txt | AC | 83 ms | 19156 KB |
random_5.txt | AC | 70 ms | 19284 KB |
random_6.txt | AC | 81 ms | 19028 KB |
random_7.txt | AC | 92 ms | 22200 KB |
random_8.txt | AC | 81 ms | 19412 KB |
random_9.txt | AC | 93 ms | 19540 KB |
sample_1.txt | AC | 69 ms | 22612 KB |
sample_2.txt | AC | 69 ms | 23124 KB |
sample_3.txt | AC | 68 ms | 21204 KB |
sample_4.txt | AC | 69 ms | 17748 KB |
small_1.txt | AC | 69 ms | 18644 KB |
small_2.txt | AC | 69 ms | 20564 KB |
small_3.txt | AC | 66 ms | 22996 KB |
small_4.txt | AC | 70 ms | 18644 KB |
small_5.txt | AC | 69 ms | 21076 KB |
small_6.txt | AC | 68 ms | 18772 KB |
small_7.txt | AC | 68 ms | 17492 KB |
small_8.txt | AC | 67 ms | 19284 KB |
small_9.txt | AC | 70 ms | 19156 KB |