AtCoder Regular Contest 058

Submission #818354

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const ll mod=1e9+7;

int N,X,Y,Z;

int S;

ll dp[41][1<<16];
ll dfs(int now, int state)
{
    if(dp[now][state]>=0) return dp[now][state];

    if(now==N) return 1;

    //直前の状態を復元
    vector<int> b;
    int st=0;
    rep(i,S)
    {
        if(state>>i&1)
        {
            b.pb(i-st+1);
            st=i+1;
        }
    }

    ll ret=0;

    //次に選ぶ数
    for(int i=1; i<=10; ++i)
    {
        bool ok=true;
        //iを次に選んだ時にXYZを含まないかチェック
        //直前から順番に見ていき貪欲に足していく
        int x=0,y=0,z=i;
        int bidx=0;
        while(bidx<b.size() && z<Z) z+=b[bidx++];
        while(bidx<b.size() && y<Y) y+=b[bidx++];
        while(bidx<b.size() && x<X) x+=b[bidx++];
        if(x==X && y==Y && z==Z) ok=false;

        if(ok)
        {
            ret+=dfs(now+1, ((state<<i)+(1<<(i-1)))%(1<<S));
            ret%=mod;
        }
    }

    return dp[now][state]=ret;
}

int main()
{
    cin >>N >>X >>Y >>Z;
    S=X+Y+Z-1;

    ll p10=1;
    rep(i,N) p10=(p10*10)%mod;

    memset(dp,-1,sizeof(dp));
    //XYZを含まない数列の個数
    ll r=dfs(0,0);
    //全体から引く
    ll ans=(p10-r+mod)%mod;
    cout << ans << endl;
    return 0;
}

Submission

Task問題 E - 和風いろはちゃん / Iroha and Haiku
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1650 Byte
File nameファイル名
Exec time実行時間 2106 ms
Memory usageメモリ使用量 21248 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt
All 700 / 700 subtask0_sample_01.txt,subtask0_sample_02.txt,subtask0_sample_03.txt,subtask0_sample_04.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask1_20.txt,subtask1_21.txt,subtask1_22.txt,subtask1_23.txt,subtask1_24.txt,subtask1_25.txt,subtask1_max1.txt,subtask1_max2.txt,subtask1_max3.txt,subtask1_min1.txt,subtask1_min2.txt,subtask1_min3.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
subtask0_sample_01.txt AC 39 ms 21248 KB
subtask0_sample_02.txt AC 39 ms 21248 KB
subtask0_sample_03.txt AC 44 ms 21248 KB
subtask0_sample_04.txt AC 2106 ms 21248 KB
subtask1_01.txt AC 39 ms 21248 KB
subtask1_02.txt AC 85 ms 21248 KB
subtask1_03.txt AC 47 ms 21248 KB
subtask1_04.txt AC 54 ms 21248 KB
subtask1_05.txt AC 43 ms 21248 KB
subtask1_06.txt AC 39 ms 21248 KB
subtask1_07.txt AC 46 ms 21248 KB
subtask1_08.txt AC 39 ms 21248 KB
subtask1_09.txt AC 39 ms 21248 KB
subtask1_10.txt AC 41 ms 21248 KB
subtask1_11.txt AC 40 ms 21248 KB
subtask1_12.txt AC 120 ms 21248 KB
subtask1_13.txt AC 75 ms 21248 KB
subtask1_14.txt AC 42 ms 21248 KB
subtask1_15.txt AC 141 ms 21248 KB
subtask1_16.txt AC 735 ms 21248 KB
subtask1_17.txt AC 215 ms 21248 KB
subtask1_18.txt AC 491 ms 21248 KB
subtask1_19.txt AC 258 ms 21248 KB
subtask1_20.txt AC 92 ms 21248 KB
subtask1_21.txt AC 450 ms 21248 KB
subtask1_22.txt AC 244 ms 21248 KB
subtask1_23.txt AC 219 ms 21248 KB
subtask1_24.txt AC 128 ms 21248 KB
subtask1_25.txt AC 249 ms 21248 KB
subtask1_max1.txt AC 2039 ms 21248 KB
subtask1_max2.txt AC 1964 ms 21248 KB
subtask1_max3.txt AC 1001 ms 21248 KB
subtask1_min1.txt AC 39 ms 21248 KB
subtask1_min2.txt AC 39 ms 21248 KB
subtask1_min3.txt AC 38 ms 21248 KB