ABC009 C問題のWAを解決したい

Question

前提・実現したいこと

ABC009 C問題のWAを解決したいです。

問題へのリンク

C - 辞書式順序ふたたび

発生している問題

下記ソースコードを提出したところ、半分以上のテストケースが通らない状況です。
7時間ほど格闘しましたがダメなところを自分では見つけることができませんでした。
ご教授お願いします。

該当のソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(void) {
	int N, K;
	cin >> N >> K;

	string s;
	cin >> s;
	
	map<char, int> alphabet;
	for (char i = 'a'; i <= 'z'; i++)
	{
		alphabet[i] = 0;
	}

	for (int i = 0; i < N; i++)
	{
		alphabet[s[i]] += 1;
	}

	string ans = "";
	for (int i = 0; i < N; i++)
	{
		for (char i = 'a'; i <= 'z'; i++)
		{
			if (alphabet[i])
			{
				string tmp_ans = ans;
				map<char, int> tmp_alphabet = alphabet;

				int changed_count = 0;

				//ansとalphabetの内容を仮決め
				tmp_ans += i;
				tmp_alphabet[i]--;

				//すでに決まっている部分の変化数をカウント
				for (int j = 0; j < tmp_ans.size(); j++)
				{
					if (tmp_ans[j] != s[j])
					{
						changed_count++;
					}
				}

				//まだ決まってない部分の最小変化数をカウント
				for (int j = tmp_ans.size(); j < N; j++)
				{
					if (!tmp_alphabet[s[j]])
					{
						changed_count++;
					}
				}

				//変化量がK以下なら仮決めしていたansとalphabetを確定する
				if (changed_count <= K)
				{
					ans = tmp_ans;
					alphabet = tmp_alphabet;
					break;
				}
			}

			//zまでたどり着いても確定できなかった場合は終了
			if (i == 'z')
			{
				cout << ans << endl;
				return 0;
			}
		}
	}

	cout << ans << endl;
	return 0;
}

Comments

[episteme]

ところでコンパイラ/デバッガはあなたのPCにインストールされてるんですよね?

[退会済みユーザー]

はい、私のPCにインストールされています
次回からそういった情報も載せておきます！この記事に反応してくださり誠にありがとうございましたm(__)m

[episteme]

いや、実行/デバッグ環境が用意されているのは「アタリマエ」なのでわざわざ載せるに及びません。
7時間もの間"何"と格闘してたんだろ... まさかコードとにらめっこ? デバッガの使い方知らない? とか思ったもので。

[退会済みユーザー]

わかりました！では次回からも載せません！
Visual Studio使ってるのでデバッガは使ってます！
ただブレークオフポイントつけたりステップインしながら変数に入ってる値の変化を確認したりといったことしかしてないので、もっとうまい使い方を勉強しようと思います！
”何”と格闘していたかは、"正しく論理を組めない自分の頭"と格闘していたといったところでしょうか！
反応ありがとうございますm(__)m

Answer 1

失敗するテストケースは見つけましたので、バグ取りがんばってください

4 2
braa

Comments

[退会済みユーザー]

ありがとうございます！
がんばってみます！！

Answer 2

解決できました！
変化した部分のカウントをカウントアップからカウントダウンに変更して、
まだ決まってない部分の最小変化数をカウントする際にminを使って英字を総なめする方針で行くと全部通りました！

元のコードは、同じ文字が文字列に含まれている場合に、まだ決まってない部分の最小変化数をカウントするループ中でalphabetが持つ値を更新しなければならないことを見落としていたためにできなかった感じです！このやり方はいろんな変数の更新頻度が多くなり煩雑だったのでカウントダウンへ方針転換したところすっきりしました！

皆様ありがとうございました！

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int main(void) {
	int N, K;
	cin >> N >> K;

	string s;
	cin >> s;

	map<char, int> alphabet;
	for (char i = 'a'; i <= 'z'; i++)
	{
		alphabet[i] = 0;
	}

	for (int i = 0; i < N; i++)
	{
		alphabet[s[i]] += 1;
	}

	string ans = "";
	for (int i = 0; i < N; i++)
	{
		for (char i = 'a'; i <= 'z'; i++)
		{
			if (alphabet[i])
			{
				string tmp_ans = ans;
				map<char, int> tmp_alphabet = alphabet;

				int changed_count = N;

				//ansとalphabetの内容を仮決め
				tmp_ans += i;
				tmp_alphabet[i]--;

				//すでに決まっている部分の変化数をカウント
				for (int j = 0; j < tmp_ans.size(); j++)
				{
					if (tmp_ans[j] == s[j])
					{
						changed_count--;
					}
				}

				//まだ決まってない部分の最小変化数をカウント
				for (char k = 'a'; k <= 'z'; k++)
				{
					changed_count -= min<int>(count(s.begin() + tmp_ans.size(),s.end(),k),tmp_alphabet[k]);
				}

				//変化量がK以下なら仮決めしていたansとalphabetを確定する
				if (changed_count <= K)
				{
					ans = tmp_ans;
					alphabet = tmp_alphabet;
					break;
				}
			}

			//zまでたどり着いても確定できなかった場合は終了
			if (i == 'z')
			{
				cout << ans << endl;
				return 0;
			}
		}
	}

	cout << ans << endl;
	return 0;
}