#1176839 (C++23(gcc16)) No.3623 2-Letter Shiritori 2

• 問題: No.3623 2-Letter Shiritori 2
• ユーザー: kwm_t
• 提出日時: 2026-08-14 22:00:04
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 3,729 bytes
• コンパイル時間: 4,781 ms
• コンパイル使用メモリ: 364,384 KB
• 実行使用メモリ: 5,888 KB
• 最終ジャッジ日時: 2026-08-14 22:00:10
• 合計ジャッジ時間: 5,623 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
other	AC * 1

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
#ifndef KWM_T_GRAPH_EULERIAN_TRAIL_HPP
#define KWM_T_GRAPH_EULERIAN_TRAIL_HPP

#include <vector>
#include <algorithm>

namespace kwm_t::graph {

/**
 * @brief 開始点決定
 */
int find_eulerian_start(
	const std::vector<std::vector<std::pair<int, int>>>& graph,
	bool directed
) {
	int n = graph.size();

	std::vector<int> indeg(n, 0), outdeg(n, 0);

	for (int v = 0; v < n; ++v) {
		for (auto [to, _] : graph[v]) {
			outdeg[v]++;
			indeg[to]++;
		}
	}

	if (directed) {
		int s = -1, t = -1;
		for (int i = 0; i < n; ++i) {
			if (outdeg[i] - indeg[i] == 1) {
				if (s != -1) return -1;
				s = i;
			}
			else if (indeg[i] - outdeg[i] == 1) {
				if (t != -1) return -1;
				t = i;
			}
			else if (indeg[i] != outdeg[i]) {
				return -1;
			}
		}
		if (s != -1) return s;

		for (int i = 0; i < n; ++i) {
			if (outdeg[i] > 0) return i;
		}
		return 0;
	}
	else {
		int start = -1;
		int odd = 0;

		for (int i = 0; i < n; ++i) {
			if ((int)graph[i].size() % 2 == 1) {
				odd++;
				start = i;
			}
		}

		if (!(odd == 0 || odd == 2)) return -1;

		if (start != -1) return start;

		for (int i = 0; i < n; ++i) {
			if (!graph[i].empty()) return i;
		}
		return 0;
	}
}

/**
 * @brief オイラー路 / オイラー閉路の復元（Hierholzer）
 *
 * @details
 * graph[v] = { {to, edge_id}, ... }
 *
 * - edge_id は [0, edge_count) の一意な番号
 * - 無向グラフの場合は「両方向に同じ edge_id を貼る」
 *
 * @param graph 隣接リスト
 * @param edge_count 辺数
 * @param directed 有向グラフかどうか
 * @param start 開始頂点（-1なら自動）
 * @return オイラー路（頂点列）。存在しない場合は空
 *
 * @note
 * 計算量: O(V + E)
 *
 * Verified:
 *  https://atcoder.jp/contests/codequeen2025-final-Public/submissions/74426816
 */
std::vector<int> eulerian_trail(
	const std::vector<std::vector<std::pair<int, int>>>& graph,
	int edge_count,
	bool directed = false,
	int start = -1
) {
	if (start == -1) {
		start = find_eulerian_start(graph, directed);
		if (start == -1) return {};
	}

	std::vector<bool> used(edge_count, false);
	std::vector<int> res;

	auto dfs = [&](auto&& self, int v) -> void {
		for (auto [to, id] : graph[v]) {
			if (used[id]) continue;
			used[id] = true;
			self(self, to);
		}
		res.push_back(v);
	};

	dfs(dfs, start);

	if ((int)res.size() != edge_count + 1) return {};

	std::reverse(res.begin(), res.end());
	return res;
}

} // namespace kwm_t::graph

#endif
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int sz = 26;
	vector g(sz, vector<P>());
	int idx = 0;
	rep(i, sz)rep(j, sz) {
		//	if (i == j)continue;
		g[i].emplace_back(j, idx);
		idx++;
	}
	auto v = kwm_t::graph::eulerian_trail(g, idx, true);
	//cout << v.size() << endl;
	rep(i, v.size() - 1) {
		string s;
		s += v[i] + 'A';
		s += v[i + 1] + 'A';
		cout << s << endl;
	}
	return 0;
}