AtCoder Beginner Contest 009

Submission #1589208

Source codeソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <set>
#include <iomanip>
#include <cmath>

using namespace std;

typedef long long int ll;
typedef std::numeric_limits<double> dbl;
const long long int LL_INF=1LL<<60;

vector<string> split(const string& input, char delimiter)
{
    stringstream stream(input);
    
    string field;
    vector<string> result;
    while (getline(stream, field, delimiter)) {
        result.push_back(field);
    }
    return result;
}

//#define DEBUG

ll A, B, M, N, D, K, Q, W, H, T, X, Y;

int main()
{
    cin >> N >> K;
    string stri; cin >> stri;
    multiset<char> rest;
    for (auto s : stri)
        rest.insert(s);
    
    vector<char> res;
    int diff = 0;
    for (int i = 0; i < N; ++i) {
        for (auto r : rest) {
            multiset<char> rrest = rest;
            auto itr = rrest.begin();
            while (*itr != r) itr++;
            rrest.erase(itr);
            cerr << "rrest : ";
            for (auto a : rrest) {
                cerr << a;
            }
            cerr << endl;
            cerr << "needed : ";
            for (int j = i+1; j < N; ++j) {
                cerr << stri[j];
            }
            cerr << endl;
            int cnt = (r == stri[i]) ? 0 : 1;
            vector<int> charNum(26);
            for (auto a : rrest)
                charNum[a-'a']++;
            vector<int> needed(26);
            for (int j = i + 1; j < N; ++j) {
                needed[stri[j]-'a']++;
            }
            for (int j = 0; j < 26; ++j) {
                cnt += max(0, needed[j] - charNum[j]);
            }
            cerr << "cnt: " << cnt << endl;
            if (cnt + diff <= K) {
                cerr << i << " okay : " << r << endl;
                if (r != stri[i]) diff++;
                res.push_back(r);
                multiset<char> nrest = rest;
                auto itr = nrest.begin();
                while (*itr != r) itr++;
                nrest.erase(itr);
                rest = nrest;
                break;
            }
        }
        cerr << "nextrest : ";
        for (auto r : rest)
            cerr << r;
        cerr << endl << endl;
    }

    for (auto r : res)
        cout << r;
    cout << endl;

    return 0;
}

Submission

Task問題 C - 辞書式順序ふたたび
User nameユーザ名 xoke
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2441 Byte
File nameファイル名
Exec time実行時間 143 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
hand_1_0.txt AC 1 ms 256 KB
hand_1_1.txt AC 1 ms 256 KB
hand_1_2.txt AC 1 ms 256 KB
hand_1_3.txt AC 1 ms 256 KB
hand_1_4.txt AC 1 ms 256 KB
hand_1_5.txt AC 1 ms 256 KB
hand_1_6.txt AC 1 ms 256 KB
hand_1_7.txt AC 1 ms 256 KB
hand_1_8.txt AC 1 ms 256 KB
hand_2_0.txt AC 2 ms 256 KB
hand_2_1.txt AC 1 ms 256 KB
hand_2_10.txt AC 1 ms 256 KB
hand_2_2.txt AC 2 ms 256 KB
hand_2_3.txt AC 2 ms 256 KB
hand_2_4.txt AC 1 ms 256 KB
hand_2_5.txt AC 1 ms 256 KB
hand_2_6.txt AC 1 ms 256 KB
hand_2_7.txt AC 1 ms 256 KB
hand_2_8.txt AC 1 ms 256 KB
hand_2_9.txt AC 1 ms 256 KB
hand_3_2.txt AC 1 ms 256 KB
hand_3_3.txt AC 1 ms 256 KB
hand_3_4.txt AC 1 ms 256 KB
hand_3_5.txt AC 1 ms 256 KB
hand_3_6.txt AC 1 ms 256 KB
hand_4_2.txt AC 3 ms 256 KB
hand_4_3.txt AC 3 ms 256 KB
hand_4_4.txt AC 2 ms 256 KB
hand_4_5.txt AC 2 ms 256 KB
hand_4_6.txt AC 2 ms 256 KB
random_1.txt AC 5 ms 256 KB
random_10.txt AC 112 ms 256 KB
random_11.txt AC 71 ms 256 KB
random_12.txt AC 78 ms 256 KB
random_13.txt AC 44 ms 256 KB
random_14.txt AC 14 ms 256 KB
random_15.txt AC 8 ms 256 KB
random_2.txt AC 12 ms 256 KB
random_3.txt AC 7 ms 256 KB
random_4.txt AC 23 ms 256 KB
random_5.txt AC 5 ms 256 KB
random_6.txt AC 30 ms 256 KB
random_7.txt AC 121 ms 256 KB
random_8.txt AC 143 ms 256 KB
random_9.txt AC 134 ms 256 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB
small_5.txt AC 1 ms 256 KB
small_6.txt AC 1 ms 256 KB
small_7.txt AC 1 ms 256 KB
small_8.txt AC 1 ms 256 KB
small_9.txt AC 1 ms 256 KB