結果
問題 |
No.3299 K-th MMA String
|
ユーザー |
![]() |
提出日時 | 2025-10-05 14:36:53 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 806 ms / 2,000 ms |
コード長 | 3,060 bytes |
コンパイル時間 | 3,243 ms |
コンパイル使用メモリ | 291,288 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-10-05 14:37:01 |
合計ジャッジ時間 | 8,051 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#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; } template <class T, class F> T binarySearch(T ok, T ng, const F &f) { while (abs(ok - ng) > 1) { T mid = (ok + ng) / 2; (f(mid) ? ok : ng) = mid; } return ok; } vector<int> g(int x, int sz) { vector<int>ret; while (x) { ret.push_back(x % 2); x /= 2; } ret.resize(sz); reverse(all(ret)); return ret; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, k; cin >> n >> k; // A = 0,M = 1; auto f = [&](const long long x)->bool { // AA~MM * no/yes auto x01 = g(x, n); // for (auto e : x01)cout << e; // cout << endl; // // eq/min // no/has // AA~MM(0,1,2,3) vector dp(2, vector(2, vector<long long>(4))); dp[0][0][0] = 1; rep(i, x01.size()) { vector ndp(2, vector(2, vector<long long>(4))); // 0->0 int tmp = x01[i]; { rep(j, 2)rep(k, 4) { int ni = 0; int nj = j; if (nj == 0 && (k == 3) && (tmp == 0))nj = 1; int nk = (k % 2) * 2 + tmp; ndp[ni][nj][nk] += dp[0][j][k]; } } // 0->1 if (tmp == 1) { int add = 0; rep(j, 2)rep(k, 4) { int ni = 1; int nj = j; if (nj == 0 && (k == 3) && (add == 0))nj = 1; int nk = (k % 2) * 2 + add; ndp[ni][nj][nk] += dp[0][j][k]; } } // 1->1 { rep(j, 2)rep(k, 4)rep(add, 2) { int ni = 1; int nj = j; if (nj == 0 && (k == 3) && (add == 0))nj = 1; int nk = (k % 2) * 2 + add; ndp[ni][nj][nk] += dp[1][j][k]; } } swap(dp, ndp); { //long long val = 0; //rep(i, 2)rep(j, 2)rep(k, 4)if (true) { // val += dp[i][j][k]; //} //cout << val << endl; } } long long val = 0; rep(i, 2)rep(j, 2)rep(k, 4)if (j == 1) { val += dp[i][j][k]; } // cout << x << "_" << val << endl; return val >= k; }; int lim = 1; rep(i, n) { lim *= 2; if (lim > INF) { lim = INF; break; } } //rep(i, 16) { // f(i); //} //return 0; //f(11); //f(12); //f(13); //return 0; //cout << lim << endl; auto tmp = binarySearch(lim, 0, f); // cout << tmp << endl; vector<int>v; while (tmp) { v.push_back(tmp % 2); tmp /= 2; } v.resize(n); reverse(all(v)); string ans; rep(i, v.size()) { if (v[i] == 0)ans += 'A'; else ans += 'M'; } cout << ans << endl; return 0; }