結果
問題 |
No.3299 K-th MMA String
|
ユーザー |
|
提出日時 | 2025-10-05 14:43:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,021 bytes |
コンパイル時間 | 2,010 ms |
コンパイル使用メモリ | 199,536 KB |
実行使用メモリ | 12,032 KB |
最終ジャッジ日時 | 2025-10-05 14:43:44 |
合計ジャッジ時間 | 3,517 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int INF = 1 << 29; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; array<array<int,4>,2> id; for(int i = 0; i < 2; i++) id[i].fill(-1); vector<array<array<int,4>,2>> dp(n, id); string ans(n, 'A'); auto rec = [&](auto rec, int p, int s, int S) -> int { if(p == n) return s; if(dp[p][s][S] != -1) return dp[p][s][S]; int ans = 0; for(int i = 0; i < 2; i++){ int NS = i * 4 + S; ans += rec(rec, p + 1, (NS == 0b011) | s, NS / 2); } return dp[p][s][S] = min(ans, INF); }; int S = 0, st = 0; for(int i = 0; i < n; i++){ int v = rec(rec, i + 1, st | (S == 0b011), S / 2); if(k <= v){ ans[i] = 'A'; }else{ S += 4; k -= v; ans[i] = 'M'; } st |= (S == 0b011); S /= 2; } cout << ans << '\n'; }