ACM-ICPC 2011年 国内予選 問題C 同色パネル結合

問題C:同色パネル結合

色は5回まで変えられる。また、5回目に変える色は指定されている。だから、「1～4回目の色の組み合わせ+1色」についてパネルの強度を調べ、最大を求める。色の数が6色なので、大雑把に考えて計算量はO(6^4)となる。コードでは、色の組み合わせを6進数4桁の数として考え、解いている。

実際に提出したコードではなく、清書したものなので、確認した入力はサンプルインプットのみ。確認済。

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

int h, w, c;
int panel[10][10];
int buf[10][10];

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

int tl_corner;
int change;

void paint(int y, int x)
{
    if (change == tl_corner)    return;
    if (!(0 <= y && y < h))     return;
    if (!(0 <= x && x < w))     return;
    if (buf[y][x] != tl_corner) return;

    buf[y][x] = change;
    for (int i = 0; i < 4; i++)
        paint(y+dy[i], x+dx[i]);
}

int count(int y, int x)
{
    if (!(0 <= y && y < h))     return 0;
    if (!(0 <= x && x < w))     return 0;
    if (buf[y][x] != tl_corner) return 0;

    buf[y][x] = -1;
    int ans = 1;
    for (int i = 0; i < 4; i++)
        ans += count(y+dy[i], x+dx[i]);
    return ans;
}

int solve(int *colors)
{
    for (int i = 0; i < 5; i++) {
        tl_corner = buf[0][0];
        change = colors[i];
        paint(0, 0);
    }

    tl_corner = c;
    return count(0, 0);
}

int main()
{
    while (cin >> h >> w >> c, h|w|c) {
        for (int y = 0; y < h; y++)
            for (int x = 0; x < w; x++)
                cin >> panel[y][x];

        int ans = 0;
        for (int i = 0; i < 6*6*6*6; i++) {
            int colors[5];
            for (int t = i, j = 0; j < 4; j++, t /= 6)
                colors[j] = t%6 + 1;
            colors[4] = c;

            memcpy(buf, panel, sizeof(panel));
            ans = max(ans, solve(colors));
        }
        cout << ans << endl;
    }
    return 0;
}

ACM-ICPC 2011年 国内予選 問題B 世界の天秤

問題B:世界の天秤

TopCoderに出てきそうな問題。普通に解くだけの問題だけれども、もう少し美しいコードにできそうだ。

ただ、"([)]."は本来noと答えならなければならないが、yesと答えるものと勘違いしていて、時間をかけてしまった。

実際に提出したコードではなく、清書したものなので、確認した入力はサンプルインプットのみ。条件式に不具合があったので、修正して入力を確認した。

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

int ascii[128];

char str[200];
int l, r;

bool check(int current, int &p)
{
    int c;
    bool f = true;
    while (c = str[p], c && f) {
        switch (c) {
            case '(':
            case '[':
                l++;
                f &= check(c, ++p);
                break;
            case ')':
            case ']':
                r++;
                return current == ascii[c];
        }
        p++;
    }
    return f;
}

int main()
{
    ascii[')'] = '(';
    ascii[']'] = '[';

    for (;;) {
        scanf("%[^\n]%*c", str);
        if (str[0] == '.')
            break;

        l = r = 0;
        int pos = 0;
        bool f = (check(-1, pos) && l == r);
        cout << (f?"yes":"no") << endl;
    }
    return 0;
}

ACM-ICPC 2011年 国内予選 問題A チェビシェフの定理

問題A:チェビシェフの定理

エラトステネスの篩を用いて、素数表を作るだけの問題。2006年国内予選の問題Aも素数表を使う問題だったが、今回の方が簡単。

実際に提出したコードではなく、清書したものなので、確認した入力はサンプルインプットのみ。確認済。

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

int n;

#define MAX 300000
char primes[MAX];

void e()
{
    memset(primes, 1, sizeof(primes));
    primes[1] = 0;
    for (int i = 2; i < MAX; i++)
        for (int j = 2*i; j < MAX; j += i)
            primes[j] = 0;
}

int main()
{
    e();
    while (cin >> n, n) {
        int ans = 0;
        for (int p = n+1; p <= 2*n; p++)
            if (primes[p])
                ans++;
        cout << ans << endl;
    }
    return 0;
}

ACM-ICPC 2011年 国内予選

三問しか解けなかった。予選突破ならず。来年は、頑張る。

ところで、四問解いて、かつ、大学内順位が一位であっても予選突破できなかったチームがいるようですね。来年以降は四問を解くことが必須条件だろうか。

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

ACM-ICPC 2010年 国内予選 問題A 角角画伯，かく悩みき

問題A:角角画伯，かく悩みき

実際に正方形を並べる必要は無し。i番目の正方形の座標を保持しつつ、上下左右の端を更新するだけ。幅は(右-左+1)、高さは(上-下+1)となる。

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

int n;
int xs[200], ys[200];

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

int main()
{
    while (cin >> n, n) {
        int u, d, r, l;
        u = d = r = l = 0;
        xs[0] = ys[0] = 0;
        for (int i = 1; i < n; i++) {
            int s, t;
            cin >> s >> t;
            xs[i] = xs[s] + dx[t];
            ys[i] = ys[s] + dy[t];
            r = max(r, xs[i]);
            l = min(l, xs[i]);
            u = max(u, ys[i]);
            d = min(d, ys[i]);
        }
        printf("%d %d\n", r-l+1, u-d+1);
    }
    return 0;
}

BloggerにSyntaxHighlighterを導入

SyntaxHighlighter - Extensions & Integrationで紹介されている、Adding a Syntax Highlighter to your Blogger blogを見て入れた。

以下は、Cでのハイライト例。

#include <stdio.h>

int main(void)
{
    int i = 0;
    while (++i <= 100)
        if (i%15==0)
            puts("FizzBuzz");
        else if (i%3==0)
            puts("Fizz");
        else if (i%5==0)
            puts("Buzz");
        else
            printf("%d\n", i);
    return 0;
}

はじめ

初記事。日々にこなしたプログラミングの問題について、気ままに書く。