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
AC × 31
WA × 27
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