intさわだんのBlack History

刹那的レジェンドになりたい。

ICPC 国内予選2013D 素数洞穴　AOJ 1189

ICPC国内予選 DP

解法：
大きめにとった二次元配列に1から10^6までの数の洞穴を書く。（たぶんここが一番めんどくさい
エラトステネスで素数をすぐ求められる配列を作っておく。
あとは最初に指定された位置から簡単なDPを解くだけ。（もはやDPと呼べるレベルではない気がするが、、、

#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[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int m[1600][1600];
int dp[1600][1600][2];
bool prime[1000010];

int main(){
    int a = 800,b = 800;
    int dir; //今向いている方向
    m[a][b] = 1;
    b += 1;
    m[a][b] = 2;
    a -= 1;
    dir = 1;
    for(int i = 3;i <= 1000000;i++){
        m[a][b] = i;
        if(dir == 0){ //→
            if(m[a-1][b] != 0){
                b += 1;
            }else{
                a -= 1;
                dir = 1;
            }
        }else if(dir == 1){ // ↑
            if(m[a][b-1] != 0){
                a -= 1;
            }else{
                b -= 1;
                dir = 2;
            }
        }else if(dir == 2){ //←
            if(m[a+1][b] != 0){
                b -= 1;
            }else{
                a += 1;
                dir = 3;
            }
        }else{ //↓
            if(m[a][b+1] != 0){
                a += 1;
            }else{
                b += 1;
                dir = 0;
            }
        }
    }

    prime[1] = true;
    for(int i = 2;i <= 1000000;i++){ //エラトス
        if(prime[i] == false){
            for(int j = 2;i*j <= 1000000;j++){
                prime[i*j] = true;
            }
        }
    }
    int mm,n;
    while(true){
        cin >> mm >> n;
        if(mm == 0 && n == 0)break;
        for(int i = 0;i < 1500;i++){
            for(int j = 0;j < 1500;j++){
                dp[i][j][0] = 0;
                dp[i][j][1] = 0;
                if(m[i][j] == n){
                    a = i;
                    b = j;
                }
            }
        }
        //cout << "a:" << a << ",b:" << b << endl;
        int aans = 0,bans = 0;
        if(prime[n] == false){
            dp[a][b][0] = 1;
            dp[a][b][1] = n;
            aans = 1;
            bans = n;
        }
        for(int i = a+1;i < 1500;i++){
            for(int j = b-(i-a);j <= b+(i-a);j++){
                if(m[i][j] == 0 || m[i][j] > mm)continue;
                int amax = 0,bmax = 0;
                for(int k = -1;k <= 1;k++){
                    if(amax < dp[i-1][j+k][0]){
                        amax = dp[i-1][j+k][0];
                        bmax = dp[i-1][j+k][1];
                    }else if(amax == dp[i-1][j+k][0] && bmax < dp[i-1][j+k][1]){
                        bmax = dp[i-1][j+k][1];
                    }
                }
                if(prime[m[i][j]] == false){
                    amax++;
                    bmax = m[i][j];
                }
                dp[i][j][0] = amax;
                dp[i][j][1] = bmax;
                if(aans < amax){
                    aans = amax;
                    bans = bmax;
                }else if(aans == amax && bans < bmax){
                    bans = bmax;
                }
            }
        }
        cout << aans << " " << bans << endl;
    }


}

ICPC 国内予選2005F Cleaning Robot AOJ 1140

ICPC国内予選

解法：ロボットとそれぞれの汚れたタイル間の距離を幅優先探索で求める。
この時点でロボットから到達できない汚れたタイルがあるかどうかわかるので-1の出力判定ができる。
あとはnext_permutationですべての汚れたタイルを回る順番を全通りためしてその中の最小値を求めればよい。（計算量は高々10!であるから余裕）

個人的には難易度350ぐらいかそれより簡単に感じた。（JOIer補正がかかっているのかもしれないが、、、
解法は自明であるので実装が重いから難易度が高くなっているのかもしれない

#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[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int d[12][12];
int place[12][2];

int main(){
    int w,h,m[25][25];
    while(true){
        cin >> w >> h;
        int dirt = 0;
        if(w == 0 && h == 0)break;
        for(int i = 0;i < 11;i++){
            for(int j = 0;j < 11;j++){
                d[i][j] = -1;
            }
        }
        for(int i = 0;i < h;i++){
            char tmp[25];
            cin >> tmp;
            for(int j = 0;j < w;j++){
                if(tmp[j] == 'o'){
                    m[i][j] = 0;
                    place[0][0] = i; place[0][1] = j;
                }else if(tmp[j] == 'x'){
                    m[i][j] = -2;
                }else if(tmp[j] == '*'){
                    dirt++;
                    m[i][j] = dirt;
                    place[dirt][0] = i; place[dirt][1] = j;
                }else{
                    m[i][j] = -1;
                }
            }
        }
        for(int i = 0;i <= dirt;i++){
            int flag[25][25];
            bool ch[25][25];
            for(int i = 0;i < 22;i++){ //init
                for(int j = 0;j < 22;j++){
                    flag[i][j] = -1;
                    ch[i][j] = false;
                }
            }
            flag[place[i][0]][place[i][1]] = 0;
            queue<P> que;
            int count = 0;
            que.push(P(place[i][0],place[i][1]));
            ch[place[i][0]][place[i][1]] = true;
            while(!que.empty()){
                P q = que.front(); que.pop();
           //     if(ch[q.fs][q.sc] == true)continue;
           //     ch[q.fs][q.sc] = true;
                int num = m[q.fs][q.sc];
                if(num >= 0 && num != i){
                    d[i][num] = flag[q.fs][q.sc];
                    count++;
                    if(count == dirt) break;               
                }
                for(int i = 0;i < 4;i++){
                    int ni = q.fs+dx[i],nj = q.sc+dy[i];
                    if(ni >= 0 && ni < h && nj >= 0 && nj < w && ch[ni][nj] == false && m[ni][nj] >= -1){
                        ch[ni][nj] = true;
                        flag[ni][nj] = flag[q.fs][q.sc] + 1;
                        que.push(P(ni,nj));
                    }
                }
            }
        }
/* 
        for(int i = 0;i <= dirt;i++){
            for(int j = 0;j <= dirt;j++){
                cout << d[i][j] << " ";
            }
            cout << endl;
        }
*/
        int ans = 0;
        for(int i = 1;i <= dirt;i++){
            if(d[0][i] == -1){
                ans = -1;
            }
        }
        if(ans == -1){
            cout << -1 << endl;
            continue;
        }
        vector<int> vec;
        ans = 10000000;
        for(int i = 1;i <= dirt;i++){
            vec.push_back(i);
        }
        do{
            int tmpans = d[0][vec[0]];
            for(int i = 0;i < dirt-1;i++){
                tmpans += d[vec[i]][vec[i+1]];
            }
            if(ans > tmpans) ans = tmpans;
        }while(next_permutation(vec.begin(),vec.end()));
        cout << ans << endl;
    }
}

ICPC 国内予選2016D　ダルマ落とし 　AOJ 1611

ICPC国内予選 DP

パッと見シミュレーションか貪欲法かなと思って考えていたが一向に解法が浮かばなかったので解説を見ました。DPという発想が出てこなかった。こういう問題がでたら確実に通したい。

解法：

  • 2個、4個、6個....連続で取り除けるかの情報をdp1[i][j]に保存する。j-iは偶数。dp1[1][4]が4の場合１，２，３，４番目のブロックは連続してすべて取り除けるということ。
  • dp2[i] = (dp2[k] + dp1[k+1][i]を0～k～iの範囲でfor文で回し、その中の最大値）

というようにすればよい。

#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[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int dp1[310][310];
int dp2[310];

int main(){
    int n,w[310];

    while(true){
        cin >> n;
        if(n == 0)break;
        for(int i = 0;i < 305;i++){ //初期化
            dp2[i] = 0;
            for(int j = 0;j < 305;j++){
                dp1[i][j] = 0;
            }
        }
        for(int i = 0;i < n;i++)cin >> w[i];
        for(int len = 1;len < n;len+=2){
            for(int i = 0;i+len < n;i++){
                int j = i + len;
                if(abs(w[i]-w[j]) <= 1 && (len == 1 || dp1[i+1][j-1] != 0)){
                    dp1[i][j] = dp1[i+1][j-1] + 2;
                }else{
                    for(int k = 1;i+k < j-1;k++){
                        if(dp1[i][i+k] != 0 && dp1[i+k+1][j] != 0){
                            dp1[i][j] = len+1;
                        }
                    }
                }
            }
        }
        for(int i = 1;i < n;i++){
            dp2[i] = dp1[0][i];
            for(int j = 0;j < i;j++){
                dp2[i] = max(dp2[i],dp2[j]+dp1[j+1][i]);
            }
        }
        cout << dp2[n-1] << endl;
    }
}

AOJ 1161 保留

保留 
#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[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


char s[14][12],alp[12];
int n;
int alpsum; //アルファベットの出現数
bool notzero[12];
int tmp[12];
int multi[12]; //掛け算の重さ

bool check(int k){
    bool num[12];
    for(int i = 0;i < 11;i++) num[i] = false;
    for(int i = 0;i < alpsum;i++){
        tmp[i] = k % 10;
        if(num[tmp[i]] == true) return true;
        num[tmp[i]] = true;
        if(tmp[i] == 0 && notzero[i] == true) return true;
        k /= 10;
    }

    return false;
}


int main(){
    while(true){
        cin >> n;
        if(n == 0)break;
        alpsum = 0;
        for(int i = 0;i < 11;i++){
            notzero[i] = 0;
            multi[i] = 0;
        }
        for(int i = 0;i < n;i++){
            cin >> s[i];
            int slen = strlen(s[i]);
            for(int j = 0;j < slen;j++){
                bool flag = true;
                if(alpsum != 0){
                    for(int k = 0;k < alpsum;k++){
                        if(alp[k] == s[i][j]){
                            flag = false;
                            int c = 1;
                            for(int l = 0;l < slen-j-1;l++){
                                c *= 10;
                            }
                            if(i == n-1)c *= -1;
                            multi[k] += c;
                            break;
                        }
                    }
                }
                if(flag == true){
                    alp[alpsum] = s[i][j];
                    int c = 1;
                    for(int l = 0;l < slen-j-1;l++) c *= 10;
                    if(i == n-1)c *= -1;
                    multi[alpsum] += c;
                    if(j == 0 && strlen(s[i]) != 1) notzero[alpsum] = true;
                    alpsum++;
                }
            }
        }
        int size = 1;
        int ans = 0;
        for(int i = 0;i < alpsum;i++) size *= 10;
        for(int i = size;i < size*2;i++){
            if(check(i) == true)continue;
            int total = 0;
            for(int j = 0;j < alpsum;j++){
                total += tmp[j] * multi[j];
            }
            if(total == 0)ans++;
        }
        cout << ans << endl;
    }
}

ICPC 国内予選2004C Unit Fraction Partition AOJ 1131

ICPC国内予選

解法
深さ優先探索で、（int 分子、int 分母、int 分母の積、int 今何個目の数か、int 現在の分母の値）を管理しながらやる。

ここで、n = 3の時、\frac{p}{q} = \frac{1}{x_1} +\frac{1}{x_2(\geqq x_1)} + \frac{1}{x_3(\geqq x_2)}
とすればよい。

#include <bits/stdc++.h>
#include <map>
#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<double, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
//const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


const double INF = 1000000.0;
const int MAX_V = 35;
struct edge{ int to,cost,rest;};
//typedef pair<int,int> P;
typedef pair<int, int> P;
typedef pair<double,T> PP;


int p,q,a,n;
int ans;

int check(int ss,int bb){
    if(p * bb == q * ss){
        return 0;
    }else if(p*bb > q*ss){
        return 1;
    }else{
        return -1;
    }
}

void dfs(int s,int b,int asum,int num,int x){
    int tmp = check(s,b);
    if(tmp == 0){ //same
        ans++;
        return;
    }else if(tmp == 1 && num != n){//continue
        for(int i = x;i <= a;i++){
            if(i * asum > a)break;
            dfs(s*i+b,b*i,asum*i,num+1,i);
        }
    }
    return;
}

int main(){
    while(true){
        cin >> p >> q >> a >> n;
        if(p + q + a + n == 0)break;
        ans = 0;
        for(int i = 1;i <= a;i++){
            dfs(1,i,i,1,i);
        }
        cout << ans << endl;
    }
}

LeetCode #1 Two Sum

LeetCode

問題：nums行列の中の整数値から和がtargetと同じ値になるものを二つ選ぶ。


解法：やるだけ。全探索。O(N)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for(int i = 0;i < nums.size();i++){
            for(int j = i + 1;j < nums.size();j++){
                if(nums[i] + nums[j] == target){
                    ans.push_back(i);
                    ans.push_back(j);
                }
            }
        }
        return ans;
    }
};

ICPC 離散的速度 AOJ1162

ICPC国内予選 保留

多少工夫してみたがMLEが取れないため保留
問題自体は解けたため次に進む

#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<double, int, int, int> T;
  
const ll MOD=1e9+7;
//const ll INF=1e18;
 
const double INF = 1000000.0;
  
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
 
struct edge{ int to,d,c;};
 
 
 
int n,m,s,g;
double d[35][35][35];
double mind;
 
int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0) break;
        cin >> s >> g;
        mind = INF;
        vector<edge> G[35];
        for(int i = 0;i < m;i++){
            int a1,a2,a3,a4;
            cin >> a1 >> a2 >> a3 >> a4;
            edge tmp1 = {a2,a3,a4};
            G[a1].push_back(tmp1);
            edge tmp2 = {a1,a3,a4};
            G[a2].push_back(tmp2);
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                for(int k = 0;k <= 31;k++){
                    d[i][j][k] = INF;
                }
            }
        }
		priority_queue<T,vector<T>,greater<T> > que2;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que2.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que2.empty()){
            T t = que2.top(); que2.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                double tmp = (double) a1 + (double)e.d;
                if(d[a4][e.to][1] < tmp)continue;
                d[a4][e.to][1] =  tmp;
                if(mind < tmp) continue;
                if(e.to == g && mind > tmp)mind = tmp;
                que2.push(make_tuple(tmp,1,a4,e.to));
            }
        }
        if(mind == INF){
            cout << "unreachable" << endl;
            continue;
        }
        //queue<T> que;
        //priority_queue<T,vector<T>,greater<T> > que;
		priority_queue<T> que;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que.empty()){
            //T t = que.front(); que.pop();
            T t = que.top(); que.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                for(int j = -1;j <= 1;j++){
                    int v = a2 + j;
                    double tmp = (double)( a1 + (double)e.d / (double)v);
            //      if(a4 == 5 && e.to == 6 && v == 1) cout << "tmp" << tmp << ",a1" << a1 <<endl;
                    if(v <= 0 || v > e.c || d[a4][e.to][v] < tmp ||tmp > mind) continue;
                    d[a4][e.to][v] =  tmp;
                    if(e.to == g && v == 1 && mind > tmp)mind = tmp;
                    que.push(make_tuple(tmp,v,a4,e.to));
                }
            }
         
         
        }
    //  cout << "ans" << d[4][5][2] << endl;
 
 
 
        double ans = INF;
        for(int i = 1;i <= n;i++){
            double tmp = d[i][g][1];
            if(ans > tmp) ans = tmp;
        //  ans = min(ans,d[i][g][1]);
        }
        if(ans == INF){
            cout << "unreachable" << endl;
        }else{
        //  cout << ans << endl;
            printf("%lf\n",ans);
        }
    }
}

#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<double, int, int, int> T;
  
const ll MOD=1e9+7;
//const ll INF=1e18;
 
const double INF = 1000000.0;
  
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
 
struct edge{ int to,d,c;};
 
 
 
int n,m,s,g;
double d[35][35][35];
double mind;
 
int main(){
    while(true){
        cin >> n >> m;
        if(n + m == 0) break;
        cin >> s >> g;
        mind = INF;
        vector<edge> G[35];
        for(int i = 0;i < m;i++){
            int a1,a2,a3,a4;
            cin >> a1 >> a2 >> a3 >> a4;
            edge tmp1 = {a2,a3,a4};
            G[a1].push_back(tmp1);
            edge tmp2 = {a1,a3,a4};
            G[a2].push_back(tmp2);
        }
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= n;j++){
                for(int k = 0;k <= 31;k++){
                    d[i][j][k] = INF;
                }
            }
        }
        //queue<T> que;
        priority_queue<T,vector<T>,greater<T> > que;
        for(int i = 0;i < G[s].size();i++){
            edge e = G[s][i];
            d[s][e.to][1] = (double) e.d;
            que.push(make_tuple((double)e.d,1,s,e.to));
        }
        while(!que.empty()){
            //T t = que.front(); que.pop();
            T t = que.top(); que.pop();
            double a1 = get<0>(t);
            int a2 = get<1>(t),a3 = get<2>(t),a4 = get<3>(t);
            if(d[a3][a4][a2] < a1 || a1 > mind)continue;
            for(int i = 0;i < G[a4].size();i++){
                edge e = G[a4][i];
                if(e.to == a3) continue;
                for(int j = -1;j <= 1;j++){
                    int v = a2 + j;
                    double tmp = (double)( a1 + (double)e.d / (double)v);
            //      if(a4 == 5 && e.to == 6 && v == 1) cout << "tmp" << tmp << ",a1" << a1 <<endl;
                    if(v <= 0 || v > e.c || d[a4][e.to][v] < tmp ||tmp > mind) continue;
                    d[a4][e.to][v] =  tmp;
                    if(e.to == g && v == 1 && mind > tmp)mind = tmp;
                    que.push(make_tuple(tmp,v,a4,e.to));
                }
            }
         
         
        }
    //  cout << "ans" << d[4][5][2] << endl;
 
 
 
        double ans = INF;
        for(int i = 1;i <= n;i++){
            double tmp = d[i][g][1];
            if(ans > tmp) ans = tmp;
        //  ans = min(ans,d[i][g][1]);
        }
        if(ans == INF){
            cout << "unreachable" << endl;
        }else{
        //  cout << ans << endl;
            printf("%lf",ans);
        }
    }
}

ICPC 国内予選2018D 全チームによるプレーオフ AOJ 1627

ICPC国内予選

深さ優先探索で全通り試せばいい。素直に全通り試すと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;

	}

}

ICPC 国内予選2011D そして，いくつになった？ AOJ1175

ICPC国内予選

円盤を取り除く順番によって取り除ける最大数が違ってくるので取り除く順番を深さ優先探索で全通り試す。
何も工夫せずにシンプルに解いたらTLEだったので、mapを使って状態を保存しておき同じ状態が訪れたら打ち切るようにしてAC。

#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};

map<int,int> m;

int n,d[30][30],abosum[30],ans;
bool abo[30][30],exist[30];

int check(bool tmp[30]){
	int ret = 0,bit = 1;
	for(int i = 1;i <= n;i++){
		if(tmp[i] == true){
			ret += bit;
		}
		bit *= 2;
	}
	return ret;
}

void solve(int tmpans,bool texist[30],int tabosum[30]){
	ans = max(ans,tmpans);
	int bit = check(texist);
	auto itr = m.find(bit);
	if(itr != m.end()) return;
	m[bit] = 1;
	for(int i = 1;i <= n;i++){
		for(int j = i+1;j <= n;j++){
			if(texist[i] == false || texist[j] == false)continue;
			if(tabosum[i] != 0 || tabosum[j] != 0) continue;
			if(d[i][3] != d[j][3]) continue;
			texist[i] = false; texist[j] = false;
			bit = check(texist);
			auto itr = m.find(bit);
			texist[i] = true; texist[j] = true;
			if(itr != m.end()) continue;
			bool tmpexist[30];
			for(int k = 1;k <= n;k++){
				tmpexist[k] = texist[k];
				if(k == i || k == j) tmpexist[k] = false;
			}
			int tmpabosum[30];
			for(int k = 1;k <= n;k++){
				tmpabosum[k] = tabosum[k];
				if( abo[i][k] == true && i < k )tmpabosum[k]--;
				if( abo[j][k] == true && j < k )tmpabosum[k]--;
			}
			solve(tmpans+2,tmpexist,tmpabosum);
		}
	}
}

int main(){
	while(true){
		cin >> n;
		if(n == 0)break;
		ans = 0;
		m.clear();
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				abo[i][j] = false;
			}
		}
		for(int i = 1;i <= n;i++){
			exist[i] = true;
			abosum[i] = 0;
			for(int j = 0;j < 4;j++){
				scanf("%d",&d[i][j]);
				//cin >> d[i][j];
			}
		}
		for(int i = 1;i <= n;i++){
			for(int j = i+1;j <= n;j++){
				if(  (d[i][0]-d[j][0])*(d[i][0]-d[j][0]) + (d[i][1]-d[j][1])*(d[i][1]-d[j][1]) < (d[i][2]+d[j][2])*(d[i][2]+d[j][2])    ){
					abo[i][j] = true; abo[j][i] = true;
					abosum[j]++;
				}
			}
		}
		solve(0,exist,abosum);

		cout << ans << endl;
	}
}

ICPC 国内予選2012C 偏りのあるサイコロ

ICPC国内予選

ただのやるだけ

#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 n,h[405][405],num[405][405];
int ss[][7] = {
	{ 0,0,0,0,0,0,0, },
	{ 0,0,3,5,2,4,0, },
	{ 0,4,0,1,6,0,3, },
	{ 0,2,6,0,0,1,5, },
	{ 0,5,1,0,0,6,2, },
	{ 0,3,0,6,1,0,4, },
	{ 0,0,4,2,5,3,0, },
};

int main(){
	while(true){
		cin >> n;
    	if(n == 0)break;
    	for(int i = 0;i < 400;i++){
      		for(int j = 0;j < 400;j++){
        		h[i][j] = 0;
        		num[i][j] = -1;
      		}
    	}
		for(int ii = 0;ii < n;ii++){
			int t,f;
			cin >> t >> f;
			int s = ss[t][f];
			int side[] = {f,s,7-f,7-s};
			int nmax = -1,rot = -1;
			int x = 200,y = 200;
			bool flag = false;
			for(int k = 0;k < 4;k++){
				if(side[k] >= 4 && side[k] > nmax && h[x][y] > h[x+dx[k]][y+dy[k]]){
					rot = k;
					nmax = side[k];
					flag = true;
				}
			}
			while(flag == true){
				flag = false;
				x = x + dx[rot]; y = y + dy[rot];
				if(rot == 0){
					int f_tmp = f;
					f = t;
					t = 7 - f_tmp;
				}else if(rot == 1){
					int s_tmp = s;
					s = t;
					t = 7 - s_tmp;
				}else if(rot == 2){
					int t_tmp = t;
					t = f;
					f = 7 - t_tmp;
				}else{
					int t_tmp = t;
					t = s;
					s = 7 - t_tmp;
				}
				nmax = -1; 
				rot = -1;
				side[0] = f; side[1] = s; side[2] = 7-f; side[3] = 7-s;
				for(int k = 0;k < 4;k++){
					if(side[k] >= 4 && side[k] > nmax && h[x][y] > h[x+dx[k]][y+dy[k]]){
						rot = k;
						nmax = side[k];
						flag = true;
					}
				}
			}
			h[x][y]++;
			num[x][y] = t;
		}
		int ans[7];
		for(int i = 1;i <= 6;i++) ans[i] = 0;
		for(int i = 0;i < 400;i++){
			for(int j = 0;j < 400;j++){
				if(num[i][j] >= 1) ans[num[i][j]]++;

			}
		}
		cout << ans[1];
		for(int i = 2;i <= 6;i++){
			cout << " " << ans[i];
		}
		cout << endl;
  	}
}