Submission #1369989

---

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();
        }
        const int alph = 'z' - 'a' + 1;

        Scanner cin;

        int N, K;
        string S;

        int[] f, origin;

        string ans;
        void solve() {
            cin = new Scanner();

            N = cin.nextInt();
            K = cin.nextInt();
            S = cin.next();

            f = new int[alph];
            origin = new int[alph];
            for (int i = 0; i < alph; i++)
                f[i] = 0;
            for (int i = 0; i < alph; i++)
                origin[i] = 0;

            ans = "";

            //文字ごとの文字数カウント
            for (int i = 0; i < N; i++) {
                f[S[i] - 'a']++;
                origin[S[i] - 'a']++;
            }

            //入力に対する処理
            for (int i = 0; i < N; i++) {
                origin[S[i] - 'a']--;
                //早い順に処理
                for (int j = 0; j < alph; j++) {
                    //Sに含まれる文字だった時実行
                    if (f[j] > 0) {
                        f[j]--;
                        if (S[i] != (char)(j + 'a'))
                            K--;

                        int diff = 0;

                        for (int k = 0; k < alph; k++)
                            diff += Math.Abs(origin[k] - f[k]);

                        //処理時++と--が行われるのでdiffの値は、
                        //ずれ1つにつき2増える。
                        if (diff / 2 <= K) {
                            ans += (char)(j + 'a');
                            break;
                        } else {

                            if (S[i] != (char)(j + 'a'))
                                K++;
                            f[j]++;
                        }
                    }
                }
            }
            Console.WriteLine(ans);
        }
    }
    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

Judge Result