結果

問題 No.936 Are
ユーザー otamay6otamay6
提出日時 2019-12-01 22:47:35
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 404 ms / 3,000 ms
コード長 5,847 bytes
コンパイル時間 2,009 ms
コンパイル使用メモリ 177,012 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-01 15:45:05
合計ジャッジ時間 6,773 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 392 ms
5,376 KB
testcase_02 AC 396 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 114 ms
5,376 KB
testcase_14 AC 323 ms
5,376 KB
testcase_15 AC 126 ms
5,376 KB
testcase_16 AC 234 ms
5,376 KB
testcase_17 AC 233 ms
5,376 KB
testcase_18 AC 85 ms
5,376 KB
testcase_19 AC 376 ms
5,376 KB
testcase_20 AC 379 ms
5,376 KB
testcase_21 AC 343 ms
5,376 KB
testcase_22 AC 208 ms
5,376 KB
testcase_23 AC 404 ms
5,376 KB
testcase_24 AC 394 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
constexpr ll mod = 1e9+7;

bool lose(int l,int r){
    return (l%5==0)&&(r%5==0);
}

void solve(){
    int N,K;
    cin>>N>>K;
    int L[2],R[2];
    cin>>L[0]>>R[0]>>L[1]>>R[1];
    ll dp[2][6][6][6][6]={};
    ll ans=0;
    dp[N][L[1]][R[1]][L[0]][R[0]]=1;
    REP(i,K+1){
        REP(a,5) REP(b,5) REP(c,5) REP(d,5){//a,b:高橋の左右、c,d:lotの左右
            if((a==0&&b==0)||(c==0&&d==0)||(a==5&&b==5)||(c==5&&d==5)) continue;
            ll now=dp[N][a][b][c][d];
            if(N&1){
                if(lose((a+c)%5,d)||lose((b+c)%5,d)||lose(c,(a+d)%5)||lose(c,(b+d)%5)) continue;//勝ち確定なので考えなくていい
                bool D=false;
                
                REP(l,5){//詰んでないときは常に分割できる
                    int r=a+b-l;
                    if(r<0) continue;
                    r%=5;
                    if(lose(l,r)||lose((l+c)%5,r)||lose((l+d)%5,r)||lose(l,(r+c)%5)||lose(l,(r+d)%5))  continue;//分割した結果負けるのはダメ
                    if(r==a&&l==b) continue;//分割の結果入れ替わるのはダメ
                    if(l==a&&r==b) continue;//分割の結果変わらないのはダメ
                    D=true;
                    (dp[0][l][r][c][d]+=now)%=mod;
                }
                //行動の結果負けないなら攻撃してよい
                if(a!=0){
                	if( !lose((a+d)%5,b) && !lose((a+c+a)%5,b) && c!=0){ 
                		(dp[0][a][b][(a+c)%5][d]+=now)%=mod;
                		D=true;
                	}
                    if( !lose((a+c)%5,b) && !lose((a+d+a)%5,b) && d!=0){
                    	(dp[0][a][b][c][(a+d)%5]+=now)%=mod;
                    	D=true;
                    }
                }
                if(b!=0){
                    if( !lose(a,(b+d)%5)&& !lose(a,(b+c+b)%5) && c!=0){
                    	(dp[0][a][b][(b+c)%5][d]+=now)%=mod;
                    	D=true;
                    }
                    if(!lose(a,(b+c)%5) && !lose(a,(b+d+b)%5) &&d!=0){
                    	(dp[0][a][b][c][(b+d)%5]+=now)%=mod;
                    	D=true;
                    }
                }
                //攻撃しかできないし、どう攻撃しても詰んでるなら全ての行動を取る
                if(!D){
                	if(a!=0){
                		if(c!=0) (dp[0][a][b][(a+c)%5][d]+=now)%=mod;
                    	if(d!=0) (dp[0][a][b][c][(a+d)%5]+=now)%=mod;
                	}
                	if(b!=0){
                    	if(c!=0) (dp[0][a][b][(b+c)%5][d]+=now)%=mod;
                    	if(d!=0) (dp[0][a][b][c][(b+d)%5]+=now)%=mod;
                	}
                }
            }
            else{//lot君はあらゆる手を取る
                if(c!=0){
                    if(a!=0) (dp[1][(a+c)%5][b][c][d]+=now)%=mod;
                    if(b!=0) (dp[1][a][(b+c)%5][c][d]+=now)%=mod;
                }
                if(d!=0){
                    if(a!=0) (dp[1][(a+d)%5][b][c][d]+=now)%=mod;
                    if(b!=0) (dp[1][a][(b+d)%5][c][d]+=now)%=mod;
                }
                REP(l,5){
                    int r=c+d-l;
                    if(r<0) continue;
                    r%=5;
                    if(l==0&&r==0) continue;
                    if(r==c&&l==d) continue;//分割の結果
                    if(l==c&&r==d) continue;//分割の結果変わらないのはダメ
                    (dp[1][a][b][l][r]+=now)%=mod;
                    
                }
            }
        }
        REP(a,5) REP(b,5) REP(c,5) REP(d,5){//lot君が勝つときを加算して使いまわすために初期化
            if(a==0&&b==0) (ans+=dp[N][a][b][c][d])%=mod;
            dp[N][a][b][c][d]=0;
        }
        N=1-N;
    }
    cout<<ans<<endl;
}

int main(){
    solve();
}

/*
まず、分割できるパターンが存在すれば攻撃できないならする必要はないし、分割できるパターンが存在しなければ攻撃する必要がある
例えば高橋くんの手が(0,1)の場合は自明で、必ず攻撃することになる
それ以外、例えば(3,3,1,1)などの場合高橋君は自分の手を(0,2)にしたりはしない、これも分割できないパターンとして扱う
大事なのは分割できないパターンでも両手が共に1以上ならば攻撃するだけで次のターンに負けないということで、これを留意して場合分けを行う(もちろん片手が0でも分割によって両手を共に1にできる)
明らかに分割できるパターンでは、高橋君は次のターン負けないことができる、そのため、攻撃することで次のターン負けるようならその攻撃はしなくてもよい
分割できないパターンにおいては、以下のような場合分けが行われる
・もしどう攻撃しても自分の負けになるならばあらゆる全ての行動をとることになる、このとき、分割することで負けになるパターンは存在せず、攻撃行動だけを考えてよい
・そうでなくて、何れかの手を選ぶことによって次のターンで負けるならば、その行動は選ぶ必要がない
・つまり、詰んでるとき以外は分割できるパターンにおける攻撃行動と全く同じ行動を取ればいいことが分かる
以上のまとめにより場合分けを実装できる
具体的には、分割、攻撃によって次のターン負けないことができるならばその行動を選択するし、そのような行動がないならば全ての攻撃行動を試せばよい
*/
0