結果

問題 No.3299 K-th MMA String
ユーザー 0214sh7
提出日時 2025-10-05 15:41:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 4,530 bytes
コンパイル時間 745 ms
コンパイル使用メモリ 79,572 KB
実行使用メモリ 12,032 KB
最終ジャッジ日時 2025-10-05 15:42:10
合計ジャッジ時間 1,397 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:159:29: warning: ‘prev’ may be used uninitialized [-Wmaybe-uninitialized]
  159 |         if(M < dp[N-(i-2)][2*prev]){
      |                            ~^~~~~
main.cpp:132:8: note: ‘prev’ was declared here
  132 |     ll prev;
      |        ^~~~

ソースコード

diff # 

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> PP;
// #define MOD 1000000007
#define MOD 998244353
#define INF 2305843009213693951ll
#define PI 3.141592653589
#define setdouble setprecision
#define REP(i,n) for(ll i=0;i<(n);++i)
#define OREP(i,n) for(ll i=1;i<=(n);++i)
#define RREP(i,n) for(ll i=(n)-1;i>=0;--i)
#define ORREP(i,n) for(ll i=(n);i>=1;--i)
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define chmin(k,m) k = min(k,m)
#define chmax(k,m) k = max(k,m)
#define GOODBYE do { cout << "-1" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl



int main(void){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll N,K;
    cin >> N >> K;

    if(0){
        ll c = 0;
        for(ll j=0;j<(1<<N);j++){
            string S(N,'-');
            REP(i,N){
                if((j>>i)%2==1){
                    S[N-i-1] = 'M';
                }else{
                    S[N-i-1] = 'A';
                }
            }

            bool ok = false;
            REP(i,N-2){
                if(S[i]=='M' && S[i+1]=='M' && S[i+2]=='A'){
                    ok = true;
                }
            }

            if(ok){
                c++;
                cout << c MM S << endl;
            }

        }

        cout << c << endl;
    }

    // dp[i][j] := i 文字見たときに、先頭の 3 文字が j のとき候補の個数
    // ただし 10^7 以上は管理しない
    vector<vector<ll>> dp(N+1,vector<ll>(8,0));
    dp[3][6] = 1;
    ll R = 2;
    for(ll i=4;i<=N;i++){
        REP(k,8){
            if(k==6)continue;
            ll y = k;if(y>=4)y-=4;y*=2;
            dp[i][k] = dp[i-1][y] + dp[i-1][y+1];
        }

        dp[i][6] += R;
        R = min(2*R,10'000'000ll);
        
        REP(k,8){
            chmin(dp[i][k],10'000'000ll);
        }
    }

    // vector<ll> dpsum(N+1,0);
    // REP(k,8){
    //     REP(j,3){cout << ((k>>(2-j))%2==1?'M':'A');}cout << " ";
    //     RREP(i,N+1){
    //         cout << dp[i][k] << " ";
    //         dpsum[i] += dp[i][k];
    //         chmin(dpsum[i],10'000'000ll);
    //     }
    //     cout << endl;
    // }
    // cout << "!!! ";
    // RREP(i,N+1){
    //     cout << dpsum[i] << " ";
    // }cout << endl;

    

    // dp2[i][j] := i 文字見たときに、先頭の 1 文字が j のとき候補の個数
    // ただし 10^7 以上は管理しない
    // vector<vector<ll>> dp2(N+1,vector<ll>(2,0));
    // REP(i,N+1){
    //     REP(k,8){
    //         dp2[i][k>=4] += dp[i][k];
    //     }
    //     REP(k,2){
    //         chmin(dp2[i][k],10'000'000ll);
    //     }
    // }


    // REP(k,2){
    //     cout << "AM"[k] << " ";
    //     RREP(i,N+1){
    //         cout << dp2[i][k] << " ";
    //     }
    //     cout << endl;
    // }
    // cout << "! ";
    // RREP(i,N+1){
    //     cout << dp2[i][0]+dp2[i][1] << " ";
    // }cout << endl;

    string Ans(N,'-');
    ll M = K-1;

    // 最初の 3 文字を決める
    ll c = 0;
    ll prev;
    REP(k,8){
        // cout << "? " << k MM c MM dp[N][k] MM M << endl;
        if(M < c + dp[N][k]){
            REP(j,3){
                Ans[j] = ((k>>(2-j))%2==1?'M':'A');
            }
            M -= c;
            prev = k;
            if(prev>=4){prev-=4;}
            break;
        }else{
            c += dp[N][k];
        }
    }

    for(ll i=3;i<=N;i++){
        // cout << i MM prev MM dp[N-(i-2)][2*prev] MM M << endl;
        if(Ans[i-3]=='M' && Ans[i-2]=='M' && Ans[i-1]=='A'){
            ll m = M;
            for(ll j=N-1;j>=i;j--){
                Ans[j] = 'A';
                if((m%2)==1){Ans[j] = 'M';}
                m /= 2;
            }
            break;
        }
        if(M < dp[N-(i-2)][2*prev]){
            Ans[i] = 'A';
        }else{
            Ans[i] = 'M';
            M -= dp[N-(i-2)][2*prev];
        }

        prev = 0;
        if(Ans[i-1]=='M')prev+=2;
        if(Ans[i]=='M')prev+=1;
        // cout << Ans << endl;
    }

    cout << Ans << endl;

    // ll M = K-1;
    // REP(i,N){
    //     cout << "! " << N-i MM M << endl;
    //     cout << "? " << dp2[N-i][0] MM dp2[N-i][1] << endl;
    //     if(M < dp2[N-i][0]){
    //         Ans[i] = 'A';
    //     }else{
    //         Ans[i] = 'M';
    //         M -= dp2[N-i][0];
    //     }
    // }
    
    // cout << Ans << endl;
    return 0;
    
}
0