Atcoder解いてみた AtCoder Beginner Contest D - Adjacent Distinct String

AtCoder Beginner Contest D - Adjacent Distinct String

問題はこちら

回答

各テストケースで入力される文字列の文字数を|S|とする
素直に並び替えるとかはできないので、O(|S|), O(|S| log|S|)あたりの計算量となる方法を考える
|S|の中で最も多い文字の数が、(|S|+1)/2+1を超えていたらNoを出す
Noじゃない場合、Sを構成する文字から以下の文字を選択していき、並び替え後の文字列S'を作る

貪欲に、直前に選ばれた文字とは異なる文字の中で、Sの中で最も文字数の多い文字
※一番最初は、単純にSの中で最も多い文字を選ぶ そのために、直前に選ばれた文字の初期値はあり得ない文字Aを設定する

multisetも活用することでO(|S| log|S|)で解くことができる

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int T;


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> T;
	std::vector<std::string> ans;

	for (int t = 0; t < T; t++) {
		std::string S;

		std::cin >> S;

		std::vector<std::vector<int>> wordIdx(26);

		// 各文字のインデックスを格納
		for (int i = 0; i < S.size(); i++) {
			wordIdx[S[i] - 'a'].push_back(i);
		}

		// 降順
		std::multiset<std::pair<int, char>, std::greater<std::pair<int, char>>> ms;
		for (int i = 0; i < wordIdx.size(); i++) {
            // 0個の文字はmsにinsertしない
            if (!wordIdx[i].empty()) {
    			std::pair<int, char> p = std::make_pair(wordIdx[i].size(), i); // 各文字の数と、文字に対応する番号 (文字の数が同じな場合、文字でソート)
    			ms.insert(p);
            }
		}

		// 一番多い文字がth以上だったらアウト
		int th = (S.size() + 1) / 2 + 1;
		if (ms.begin()->first >= th) {
			ans.push_back("No");
			continue;
		}

		// 隣り合う文字が異なる文字列を生成
		// 貪欲に最も多い文字かつ、直前と異なる文字を選んでつなげる
		// 最も多い文字かつ、直前と異なる文字を取得→msから削除→答えにくっつける→最も多い文字の文字数を1減らす→msに追加
		// O(logN)
		std::string Sd;
		char select = 'A'; // 直前に選ばれる文字(最初はありない文字)
		for (int i = 0; i < S.size(); i++) {
			auto itr = ms.begin();

			// 直前に選ばれた文字と異なる文字の中で、最も文字数の多い文字を選択
			while(true) {
				// 直前に選ばれた文字と異なる文字
				if (select != itr->second + 'a') {
					// 直前に選ばれた文字の更新
					select = itr->second + 'a';
					break;
				}
				itr++;
			}

			// 直前に選ばれた文字と異なる文字の中で、最も文字数の多い文字を含むpairを取得
			std::pair<int, char> p = *itr;
			ms.erase(p);

			char word = p.second + 'a'; // 文字に戻す
			Sd += word;
			p.first--;
			ms.insert(p);
		}

		ans.push_back("Yes");
		ans.push_back(Sd);
	}

	for (std::string strAns : ans) {
		std::cout << strAns << std::endl;
	}

	return 0;
}

より、シンプルに、バグりにくいコードを書くなら以下
multiset使わない
英小文字は26種類なため、毎回26文字ループしてもOK

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int T;


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> T;

	for (int t = 0; t < T; t++) {
		std::string S;

		std::cin >> S;

        std::vector<int> cnt(26, 0);
        for (char c : S) cnt[c - 'a']++;

        int n = S.size();
        int mx = *std::max_element(cnt.begin(), cnt.end());

        if (mx > (n + 1) / 2) {
            std::cout << "No\n";
            continue;
        }

        std::string ans;
        char prev = '#';

        for (int i = 0; i < n; i++) {
            int best = -1;

            for (int c = 0; c < 26; c++) {
                if (cnt[c] == 0) continue;
                if ('a' + c == prev) continue;

                if (best == -1 || cnt[c] > cnt[best]) {
                    best = c;
                }
            }

            ans += char('a' + best);
            prev = char('a' + best);
            cnt[best]--;
        }

        std::cout << "Yes\n";
        std::cout << ans << "\n";
	}

	return 0;
}