ACM-ICPC 2010年 国内予選 問題C ポロック予想

問題C:ポロック予想(Inputの10^6が106に見えるので注意)

dp[n] = 「正整数nを表すために必要な正四面体数の個数の最小」とする。この時、dp[n] = min(dp[n-1], dp[n-4], dp[n-10], ... , dp[n - (n以下である、正四面体数の最大)]) + 1となる。

奇数の場合も同様に考える。

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

int tri[182];
int squ[182];//181*182*183/6 = 1004731 > 10^6

#define MAX 1000000
int dp[MAX], dp_odd[MAX];

int n;

int main()
{
    tri[0] = squ[0] = 0;
    for (int i = 1; i < 182; i++)
        tri[i] = tri[i-1] + i,
        squ[i] = squ[i-1] + tri[i];

    dp[0] = dp_odd[0] = 0;
    for (int i = 1; i < MAX; i++) {
        //少なくともsqu[1]=1をi個だけ用いて表せる。
        dp[i] = dp_odd[i] = i;

        for (int j = 1;; j++) {
            int t = squ[j];
            if (t > i)    break;

            dp[i] = min(dp[i], dp[i-t]+1);
            if (t&1)
                dp_odd[i] = min(dp_odd[i], dp_odd[i-t]+1);
        }
    }

    while (cin >> n, n)
        printf("%d %d\n", dp[n], dp_odd[n]);
    return 0;
}

ACM-ICPC 2010年 国内予選 問題B 迷図と命ず

問題B:迷図と命ず

文字列をそのまま読み込んで、幅探索。

#include <iostream>
#include <complex>
#include <queue>
#include <cstring>
using namespace std;

typedef complex<int> P;

int w, h;

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int d[30*2-1][30*2-1];

int main()
{
    while (cin >> w >> h, w|h) {
        cin.ignore();

        vector<string> ss(2*h-1);
        for (int i = 0; i < 2*h-1; i++)
            getline(cin, ss[i]);

        queue<P> que;
        que.push(P(0, 0));
        memset(d, 0, sizeof(d));
        d[0][0] = 1;
        int gy = (2*h-1)-1, gx = (2*w-1)-1;
        while (que.size()) {
            P p = que.front(); que.pop();
            for (int i = 0; i < 4; i++) {
                int py = p.real(), px = p.imag();
                if (px == gx && py == gy)        goto end;

                int nx = px + dx[i];
                int ny = py + dy[i];
                if (!(0 <= nx && nx < 2*w-1))    continue;
                if (!(0 <= ny && ny < 2*h-1))    continue;
                if (ss[ny][nx] == '1')           continue;

                int tx = nx + dx[i];
                int ty = ny + dy[i];
                if (d[ty][tx] != 0)              continue;

                d[ty][tx] = d[py][px] + 1;
                que.push(P(ty, tx));
            }
        }
end:
        cout << d[gy][gx] << endl;
    }
    return 0;
}