Submission #1369878
Source Code Expand
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.IO; using System.Linq; using System.Text; namespace ABC009 { class MainClass { public static void Main(string[] args) { new MainClass().solve(); } Scanner cin; int N, K; string S; string MIN; string ans; void solve() { cin = new Scanner(); N = cin.nextInt(); K = cin.nextInt(); S = cin.next(); char[] tmp = S.ToCharArray(); Array.Sort(tmp); MIN = new string(tmp); ans = ""; //アプローチ //前半部と後半部に分けて考える //辞書順最優先で前半部を決定。 //初期配置とのずれが許容範囲内か調査 //現実性優先で後半部を決定 //後半部を残りの許容範囲のずれに収めることができるか調査 for (int i = S.Length-1; i >= 0; i--) { int diff = check(i); if (diff > K) continue; if (!verif(i, K - diff)) continue; ans += MIN.Substring(0, i + 1); char[] cs = S.Substring(i + 1, S.Length - i - 1).ToCharArray(); List<char> cm = new List<char>(MIN.Substring(i+1,S.Length-i-1).ToArray()); cm.Sort(); for (int j = 0; j < cs.Length ; j++) { if (!cm.Remove(cs[j])) { cs[j] = '0'; } } //後半部代入処理 for(int j = 0; j < cs.Length; j++) { if (cs[j] != '0') { ans += cs[j]; } else { ans += cm[0]; cm.RemoveAt(0); } } break; } Console.WriteLine(ans); } //前半部並び替えにおける初期配置とのずれ int check(int n) { int diff = 0; for (int i=0; i <= n; i++) if (S[i] != MIN[i]) diff++; return diff; } //後半部並び替えが可能か bool verif(int n,int k) { int diff=0; char[] s=S.Substring(n+1,S.Length-n-1).ToCharArray(); char[] min = MIN.Substring(n + 1, MIN.Length - n-1).ToCharArray(); for(int i = 0; i < s.Length; i++) { if (Array.IndexOf(min, s[i])<0){ diff++; } } return (diff <= k); } } class Scanner { string[] nextBuffer; int BufferCnt; char[] cs = new char[] { ' ' }; public Scanner() { nextBuffer = new string[0]; BufferCnt = 0; } public string next() { if (BufferCnt < nextBuffer.Length) return nextBuffer[BufferCnt++]; string st = Console.ReadLine(); while (st == "") st = Console.ReadLine(); nextBuffer = st.Split(cs, StringSplitOptions.RemoveEmptyEntries); BufferCnt = 0; return nextBuffer[BufferCnt++]; } public int nextInt() { return int.Parse(next()); } public long nextLong() { return long.Parse(next()); } public double nextDouble() { return double.Parse(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | C - 辞書式順序ふたたび |
User | rui0422 |
Language | C# (Mono 4.6.2.0) |
Score | 0 |
Code Size | 3811 Byte |
Status | WA |
Exec Time | 27 ms |
Memory | 13396 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | WA | 27 ms | 9556 KB |
hand_1_1.txt | WA | 27 ms | 11348 KB |
hand_1_2.txt | AC | 26 ms | 11232 KB |
hand_1_3.txt | AC | 26 ms | 11232 KB |
hand_1_4.txt | AC | 26 ms | 11232 KB |
hand_1_5.txt | AC | 26 ms | 13280 KB |
hand_1_6.txt | AC | 26 ms | 13280 KB |
hand_1_7.txt | AC | 24 ms | 9172 KB |
hand_1_8.txt | AC | 25 ms | 9300 KB |
hand_2_0.txt | WA | 23 ms | 9300 KB |
hand_2_1.txt | WA | 26 ms | 11348 KB |
hand_2_10.txt | AC | 25 ms | 11348 KB |
hand_2_2.txt | AC | 27 ms | 13396 KB |
hand_2_3.txt | AC | 26 ms | 11232 KB |
hand_2_4.txt | AC | 26 ms | 13280 KB |
hand_2_5.txt | WA | 26 ms | 11348 KB |
hand_2_6.txt | AC | 26 ms | 11232 KB |
hand_2_7.txt | AC | 26 ms | 9184 KB |
hand_2_8.txt | AC | 24 ms | 9300 KB |
hand_2_9.txt | AC | 24 ms | 9172 KB |
hand_3_2.txt | WA | 26 ms | 13280 KB |
hand_3_3.txt | WA | 26 ms | 11232 KB |
hand_3_4.txt | AC | 26 ms | 9184 KB |
hand_3_5.txt | WA | 26 ms | 11232 KB |
hand_3_6.txt | AC | 25 ms | 9184 KB |
hand_4_2.txt | WA | 26 ms | 11232 KB |
hand_4_3.txt | WA | 26 ms | 9184 KB |
hand_4_4.txt | WA | 26 ms | 13268 KB |
hand_4_5.txt | WA | 26 ms | 9184 KB |
hand_4_6.txt | WA | 26 ms | 11232 KB |
random_1.txt | WA | 26 ms | 13280 KB |
random_10.txt | WA | 26 ms | 13280 KB |
random_11.txt | WA | 26 ms | 11232 KB |
random_12.txt | WA | 26 ms | 11232 KB |
random_13.txt | WA | 26 ms | 9300 KB |
random_14.txt | WA | 25 ms | 9184 KB |
random_15.txt | AC | 25 ms | 11220 KB |
random_2.txt | AC | 26 ms | 11232 KB |
random_3.txt | AC | 26 ms | 13268 KB |
random_4.txt | WA | 26 ms | 9184 KB |
random_5.txt | AC | 24 ms | 9300 KB |
random_6.txt | WA | 26 ms | 11232 KB |
random_7.txt | AC | 26 ms | 11232 KB |
random_8.txt | WA | 26 ms | 9184 KB |
random_9.txt | WA | 26 ms | 11232 KB |
sample_1.txt | AC | 25 ms | 11220 KB |
sample_2.txt | AC | 26 ms | 11232 KB |
sample_3.txt | AC | 24 ms | 9300 KB |
sample_4.txt | AC | 26 ms | 11232 KB |
small_1.txt | AC | 25 ms | 11348 KB |
small_2.txt | AC | 25 ms | 11348 KB |
small_3.txt | WA | 23 ms | 9300 KB |
small_4.txt | WA | 24 ms | 11232 KB |
small_5.txt | AC | 24 ms | 9300 KB |
small_6.txt | WA | 23 ms | 9172 KB |
small_7.txt | WA | 23 ms | 11232 KB |
small_8.txt | AC | 25 ms | 11348 KB |
small_9.txt | AC | 25 ms | 11220 KB |