ICPC 国内予選2018D 全チームによるプレーオフ AOJ 1627
深さ優先探索で全通り試せばいい。素直に全通り試すとO(2^36)となりなかなか厳しいが、全チームプレーオフにならないと分かったら探索を打ち切ればそこまで計算量は多くならない。
再帰では、今いる場所・それぞれのチームの勝利数・敗北数を渡していけばよい。
#include <bits/stdc++.h> #define chmin(a, b) ((a)=min((a), (b))) #define chmax(a, b) ((a)=max((a), (b))) #define fs first #define sc second #define eb emplace_back using namespace std; typedef long long ll; typedef pair<int, int> P; typedef tuple<int, int, int> T; const ll MOD=1e9+7; const ll INF=1e18; int dx[]={0, 1, 0, -1}; int dy[]={-1, 0, 1, 0}; int maxg,ans,n,t[10][10]; int getxy(int g){ int x=1,y; int plus = n-1; for(int i = n-1;plus >= 1;x++){ plus--; if(g <= i){ y = n - (i - g); break; } i += plus; } return (10*x+y); } void solve(int g,int l[10],int w[10]){ int xy = getxy(g); int x = xy / 10,y = xy % 10; int eq = (n-1)/2; if(g == maxg){ //finish solve if(t[x][y] == 1){ //win if(w[x] == eq && l[y] == eq){ ans++; } }else if(t[x][y] == -1){ if(w[y] == eq && l[x] == eq){ ans++; } }else{ if(w[x]+1 == eq && l[y]+1 == eq){ ans++; } if(w[y]+1 == eq && l[x]+1 == eq){ ans++; } } return; }else if(t[x][y] == 0){ if(w[x]+1 <= eq && l[y]+1 <= eq){ w[x]++; l[y]++; solve(g+1,l,w); w[x]--; l[y]--; } if(w[y]+1 <= eq && l[x]+1 <= eq){ w[y]++; l[x]++; solve(g+1,l,w); w[y]--; l[x]--; } }else if(t[x][y] == -1){ if(w[y] <= eq && l[x] <= eq){ solve(g+1,l,w); } }else{ if(w[x] <= eq && l[y] <= eq){ solve(g+1,l,w); } } return; } int d[40][2]; int l[10],w[10],g; int main(){ int m; while(true){ cin >> n; if(n == 0)break; cin >> m; maxg = 0; ans = 0; for(int i = n-1;i >= 1;i--){ maxg += i; } for(int i = 1;i <= n;i++){ l[i] = 0; w[i] = 0; for(int j = 1;j <= n;j++){ t[i][j] = 0; } } for(int i = 0;i < m;i++){ int x,y; cin >> x >> y; w[x]++; l[y]++; t[x][y] = 1; t[y][x] = -1; } solve(1,l,w); cout << ans << endl; } }