結果
問題 | No.233 めぐるはめぐる (3) |
ユーザー |
![]() |
提出日時 | 2023-01-03 12:56:04 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 1,000 ms |
コード長 | 2,364 bytes |
コンパイル時間 | 1,106 ms |
コンパイル使用メモリ | 143,892 KB |
実行使用メモリ | 13,568 KB |
最終ジャッジ日時 | 2024-11-27 01:50:19 |
合計ジャッジ時間 | 4,575 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;const char A[4] = {'i', 'e', 'a', 'u'};const char B[5] = {'n', 'b', 'm', 'g', 'r'};map<string, bool> memo;string ans;void dfs(string &str, int mask, int *counter, int a_count, bool insert_flg) {if (str.size() == 11) {if (memo.count(str) == 0) {ans = str;}return;}if (ans.size() > 0) return;if (str.size() == 0 || not insert_flg) {for (int i = 0; i < 4; ++i) {if (i <= 1 && counter[i] >= 1) continue;if (i >= 2 && counter[i] >= 2) continue;str.push_back(A[i]);counter[i]++;dfs(str, mask, counter, a_count + 1, (a_count > 0 || str.size() == 1));str.pop_back();counter[i]--;}if (str.size() == 0 || a_count > 0) {for (int i = 0; i < 5; ++i) {if (mask >> i & 1) continue;str.push_back(B[i]);int nmask = mask | (1 << i);dfs(str, nmask, counter, 0, insert_flg);str.pop_back();}}} else if(a_count == 0) {for (int i = 0; i < 4; ++i) {if (i <= 1 && counter[i] >= 1) continue;if (i >= 2 && counter[i] >= 2) continue;str.push_back(A[i]);counter[i]++;dfs(str, mask, counter, a_count + 1, insert_flg);str.pop_back();counter[i]--;}} else {if (not insert_flg) {for (int i = 0; i < 4; ++i) {if (i <= 1 && counter[i] >= 1) continue;if (i >= 2 && counter[i] >= 2) continue;str.push_back(A[i]);counter[i]++;dfs(str, mask, counter, a_count + 1, true);str.pop_back();counter[i]--;}}for (int i = 0; i < 5; ++i) {if (mask >> i & 1) continue;str.push_back(B[i]);int nmask = mask | (1 << i);dfs(str, nmask, counter, 0, insert_flg);str.pop_back();}}}int main() {int N;cin >> N;for (int i = 0; i < N; ++i) {string s;cin >> s;memo[s] = true;}int counter[4] = {0, 0, 0, 0};string str = "";dfs(str, 0, counter, 0, false);if (ans.size() == 0) {cout << "NO" << endl;} else {cout << ans << endl;}return 0;}