2014-06-27

AOJ 1165

AOJ

この問題で、答えを出すにあたって必要な要素は縦横の長さです。
0枚目の正方形から4方向へ最大どのくらい図形が大きくなったかを保持して出力しす。

また問題では、N-1枚目の正方形がn枚目の正方形からｄ方向へ移動しているので
、ｎ枚目の正方形が0枚目の座標からどんくらい離れているかが重要な要素になります。

以上をこれをコードにします。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair <int,int> P;

int main()
{
    int n;
    while (cin >> n, n) {
        vector<P> v;
        v.push_back(P(0, 0));
        int R = 0, L = 0, T = 0, B = 0;
        for (int i = 1; i < n; i++) {
            int t1, t2;
            cin >> t1 >> t2;
            int x = v[t1].first, y = v[t1].second;
            if (t2 == 0) y--;
            else if (t2 == 1) x--;
            else if (t2 == 2) y++;
            else if (t2 == 3) x++;
            v.push_back(P(x, y));
            if (x > T) T = x;
            else if (x < B) B = x;
            else if (y > R) R = y;
            else if (y < L) L = y;
        }
        cout << (R - L + 1) << " " << (T - B + 1) << endl;
    }

    return 0;
}

2014-06-06

D - 三角パズル

AtCoder

D: 三角パズル - WUPC 2012 | AtCoder

・DP

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
using namespace std;

typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;

int main()
{
    int dp[101][101];
    int n[101][101];
    int N;
    cin >> N;
    for (int i = 0; i <= N; i++)
        for (int j = 1; j <= i; j++)
            cin >> n[i][j];

    int res = 0;
    dp[0][1] = n[0][1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] += (n[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]));
            if (i == N) res = max(res, dp[i][j]);
        }
    }
    cout << res << endl << endl;

    for (int i = 0; i <= N; i++) {
        cout  << endl;
        for (int j = 0; j <= N; j++) {
            cout << dp[i][j] << " ";
        }
    }


    return 0;
}

2014-06-02

AOJ 0119

AOJ

問題

・幅優先探索

・部屋に入った順にランク付けを行う
・この問題では証言をしていない者がいる
　-> 探索が途切れる場面がある
　-> すべての証言者から辿り、ランク付けをする必要がある

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
using namespace std;

typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;

const int MAX = 20;

int n, m, p1, p2;
V v[MAX + 1];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> p1 >> p2;
        v[p1].push_back(p2);
    }
    int res[MAX + 1], maxR = 0;
    for (int i = 1; i <= n; i++) res[i] = 1; //initialize rank

    int s;
    Q q;
    for (int j = 1; j <= n; j++) {
        q.push(j);
        while (q.size()) {
            s = q.front(); q.pop();
            for (int i = 0; i < v[s].size(); i++) {
                if (res[s] >= res[v[s][i]]) {
                    res[v[s][i]] = res[s] + 1;
                    maxR = max(maxR, res[v[s][i]]);
                    q.push(v[s][i]);
                }
            }
        }
    }

    for (int i = 1; i <= maxR; i++)
        for (int j = 1; j <= n; j++)
            if (res[j] == i)
                cout << j << endl;

    return 0;
}

ps. 最近、幅優先探索しか書いてない気がする（汗

2014-06-01

AOJ 0117

AOJ

問題

・幅優先探索
・最短経路問題

#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <cstring>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
using namespace std;

typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;

const int MAX = 21;
const int INF = 999999;

int n, m, f[MAX][MAX];
V d[MAX];

int bfs (int start, int goal) {
    int s[MAX];
    memset(s, INF, sizeof(s));
    Q q;
    q.push(start);
    s[start] = 0;

    while (q.size()) {
        int t1 = q.front(); q.pop();

        for (int i = 0; i < d[t1].size(); i++) {
            int t2 = d[t1][i];
            if (s[t2] > s[t1] + f[t1][t2]) {
                s[t2] = s[t1] + f[t1][t2];
                q.push(t2);
            }
        }
    }

    return s[goal];
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c, dd;
        scanf("%d,%d,%d,%d", &a, &b, &c, &dd);
        f[a][b] = c;
        f[b][a] = dd;

        d[a].push_back(b);
        d[b].push_back(a);
    }
    int x1, x2, y1, y2;
    scanf("%d,%d,%d,%d", &x1, &x2, &y1, &y2);

    int res = y1 - y2;
    res -= bfs(x1, x2);
    res -= bfs(x2, x1);

    cout << res << endl;

    return 0;
}

2014-05-31

AOJ 0595

AOJ

問題

幅優先探索（今回の解法）
DP？（←多分これでも解ける）

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
using namespace std;
  
typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;
  
const int MOD = 10007;
const int J = 4, O = 2, I = 1;
string str;
int n, attendA[8], attendB[8];
  
int changeNumber(char s) {
    if (s == 'J') return J;
    else if (s == 'O') return O;
    else return I;
}
  
int bfs() {
    Q q;
    q.push(J);
    int res = 0;
    int day = 0;
    attendB[J] = 1;
    while (day < n) {
        while (q.size()) {
            int befor = q.front(); q.pop();
            for (int i = 1; i < 8; i++) {
                if ((befor & i) && (changeNumber(str[day]) & i))
                    attendA[i] += attendB[befor];
            }
        }
        for (int i = 1; i < 8; i++) {
            attendB[i] = attendA[i];
            if (attendB[i] > 0) q.push(i);
            attendA[i] = 0;
            attendB[i] %= MOD;
        }
        day++;
    }
    for (int i = 1; i < 8; i++)
        res += (attendB[i] % MOD);
    res %= MOD;
  
    return res;
}
  
int main()
{
    cin >> n >> str;
    cout << bfs() << endl;
    return 0;
}

2014-05-31

AOJ 0116

AOJ

解いたので、何となく載せてみました。
問題

#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
using namespace std;

typedef list<int> L;
typedef pair <int,int> P;
typedef vector<int> V;
typedef queue<int> Q;
typedef stack<int> S;
typedef map<string,int> M;

int main()
{
    int H, W;
    
    while (cin >> H >> W, H) {
        char d[H][W];
        int ansW, ansH, ans = 0;
        for (int i = 0; i < H; i++)
            for (int j = 0; j < W; j++)
                cin >> d[i][j];

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (d[i][j] == '.') {
                    ansH = 0;
                    ansW = 9999;
                    while (d[i + ansH][j] == '.' && i + ansH < H) {
                        int m = 0;
                        while (d[i + ansH][j + m] == '.' && j + m < W) m++;
                        ansW = min(ansW, m);
                        ansH++;
                        ans = max(ans, ansW * ansH);
                    }
                }
            }
        }
        cout << ans << endl;
    }
    
    
    return 0;
}

2014-03-28

QUPCの結果！！

ドイツから帰国して、久しぶりのプロコンでした。
出来から言えば力技で解ける問題しか解けず、ICPCへの道が遠く感じる結果になりました。
解説も出ましたが、自分のコードを上げたと思います。

・A問題
　この問題は最低合格人数でその時の最高点を求める問題なので、問題の意図通り最高点から段々得点を小さくして、最低合格人数を超える最高合格点を見つけます。

#include <iostream>
#define MAX 11
using namespace std;

int main()
{
     int a, b, c, d;
     int data[MAX][MAX];
     cin >> a >> b >> c >> d;
     for (int i = 0; i < c; i++) {
	  for (int j = 0; j < a; j++) {
	       cin >> data[i][j];
	  }
     }

     int res;

     for (res = 100; res >= 0; res--) {
	  int count = 0;
	  for (int j = 0; j < c; j++) {
	       int tmp = 0;
	       for (int k = 0; k < a; k++) {
		    if (data[j][k] >= res) tmp++;
	       }
	       if (tmp >= b) count++;
	  }
	  if (count >= d) break;
     }
     cout << res << endl;

     return 0;
}

・B問題
　この問題は言われたことをそのままやります。百の位と十の位の時に数字が９である時に例外処理を施します。問題そのままです。

#include <iostream>
#include <string>
using namespace std;

const string small_str_one[10] = {"nilium", "unium", "bium", "trium", "quadium", "pentium", "hexium", "septium", "octium", "ennium"};
const string small_str_un_one[10] = {"nil", "un", "bi", "tri", "quad", "pent", "hex", "sept", "oct", "enn"};
const string large_str_un_one[10] = {"Nil", "Un", "Bi", "Tri", "Quad", "Pent", "Hex", "Sept", "Oct", "Enn"};
const string small_un_str = "en";
const string large_un_str = "En";
     
int main()
{
     int N;
     cin >> N ;
     string ans;
     int n1 = N % 10;
     N /= 10;
     int n2 = N % 10;
     N /= 10;
     int n3 = N % 10;

     if (n3 == 9) {
	  if (n2 == 0 || n2 == 1) {
	       ans += large_un_str;
	  } else {
	       ans += large_str_un_one[9];
	  }
     } else {
	  ans += large_str_un_one[n3];
     }

     if (n2 == 9) {
	  if (n1 == 0 || n2 == 1) {
	       ans += small_un_str;
	  } else {
	       ans += small_str_un_one[9];
	  }
     } else {
	  ans += small_str_un_one[n2];
     }

     ans += small_str_one[n1];

     cout << ans << endl;
     
	       

     return 0;
}

・C問題
　この問題は答えが２６個しか存在しないと分かっているので、そのことを利用してmapで辞書化しておきます。道案内の質問に対してキー（A~Z）を使って座標を引き出し、引き出せない場合は"NA"を返します。

#include <iostream>
#include <map>
#include <string>
#define MAX 1000
using namespace std;

typedef pair<int,int> P;
typedef map<int,P> M;

int main()
{
     M s;
     int n, m, q;
     cin >> n >> m >> q;
     string str[MAX];
     for (int i = 0; i < n; i++) {
	  cin >> str[i];
     }
     for (int i = 0; i < n; i++) {
	  for (int j = 0; j < m; j++) {
	       if (str[i][j] != '*') s[str[i][j] - 'A'] = P(i + 1,j + 1);
	  }
     }
     for (int i = 0; i < q; i++) {
	  char que;
	  cin >> que;
	  P p = s[que - 'A'];
       if (p.first && p.second) {
	    cout << p.first << " " << p.second << endl;
       } else {
          cout << "NA" << endl;
        }
     }
	  

     return 0;
}

今回はD問題以降のアルゴリズムとデータ構造が必要になる問題が解けなかったので、まだまだ競技プログラミングの入門レベルを超えられていない気がします。

wanimaru47's diary

プログラミング等々