ACM-ICPC 2007年 国内予選 問題A ICPC 得点集計ソフトウェア

問題A:ICPC 得点集計ソフトウェア

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

int main()
{
    int n;
    while (cin >> n, n) {
        int buf, sum, sz;
        vector<int> s;

        while(n--) {
            cin >> buf;
               s.push_back(buf);
        }
        sort(s.begin(), s.end());

        sum = 0;
        sz = s.size();
        for (int i = 1; i < sz-1; i++)
            sum += s[i];
        cout << sum/(sz-2) << endl;
    }
    return 0;
}

Project Euler Problem 10

Problem 10

エラトステネスの篩を使って、総和の計算をするだけ。

Schemeのコードは、Scheme:数遊び:素数列に載せられているgemmaさんのコードを参考、もとい、パクらせていただいた。

Scheme

(use srfi-1)
(use srfi-42)
(use numbers)

(define (primes n)
  (let loop ((l (unfold (lambda (x) (> x n)) values (lambda (x) (+ x 2)) 3))
             (primes-list '(2)))
    (let ((m (car l)))
      (if (> (* m m) n)
          (append primes-list l)
          (loop (remove (lambda (x) (zero? (modulo x m))) l)
                (cons m primes-list))))))

(define (p010)
  ;リストが長すぎて、applyを呼び出すとエラーが起きる……
  ;(print (apply + (primes 2000000)))
  (print (sum-ec (: i (primes 2000000)) i)))

(p010)

C++

#include <cstdio>
#include <cstring>

#define LIM 2000000
char primes[LIM+1];

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

int main()
{
    long long ans;

    e();
    ans = 0;
    for (int i = 1; i <= LIM; i++)
        if (primes[i])
            ans += i;

    printf("%lld\n", ans);
    return 0;
}

EGGXを用いたマンデルブロ集合の色付き描画

前回の記事のプログラムを少々変更してマンデルブロ集合の図を色付けした。

数列の発散、収束を計算していた関数と、それに関連する部分を少しだけ変えたプログラムを次に示す。発散する点においては、発散するまでに計算した回数を利用して色付けした。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0

int calc(complex<double> c)
{
    int n;
    complex<double> z;
    for (n = 0; n < MAX_ITER; n++) {
        z = z*z + c;
        if (abs(z) >= INF)
            return n%15+1;
    }
    return EGGX_BLACK;
}

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            int color = calc(complex<double>(re, im));
            newpen(win, color);
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
} 

EGGXを用いたマンデルブロ集合の描画

EGGXを使ってマンデルブロ集合を描く。

結論から示す。マンデルブロ集合を描いたとき、次のような図となる。

以下、どのようにこの図を描いていくのかを説明する。

まず、複素数列{Zn}を次のように定義する。
Zn+1 = (Zn)ˆ2 + C
Z0 = 0
ただし、Z0は初項であり、Zn+1におけるCは複素平面上の一点を意味する。

このときマンデルブロ集合は、「数列{Zn}においてn->∞としたとき、その数列が発散しないような複素数C全体の集合」と定義される。

では、マンデルブロ集合を図として描くときの手順を示す。
(1) 実部の区間を[-2, 1]、虚部の区間を[-1, 1]とし、その区間を描画領域とする。
(2) (1)の区間内にある全ての点を、上述の数列{Zn}のCとして与える。
(3) (2)で決めた数列{Zn}においてn->∞としたとき、{Zn}が発散するならば白、収束するならば黒で複素平面上の点であるCの位置に、点を描く。

以上が、基本的な手順となる。ただ、マンデルブロ集合は{Zn}が収束するような点全体として定義されるので、発散する点はマンデルブロ集合に含まれない。けれども、手順(3)からも判るように、ここでは発散する点を白で描いている。

マンデルブロ集合を描く、EGGXを用いたC++のソースコードを次に示す。実際にEGGXを用いてコンパイルする場合は、拡張子を.ccにすること。

#include <complex>
#include <eggx.h>
using namespace std;

#define BASE_SCALE 300

#define RE_START -2
#define RE_END 1
#define RE_LENGTH (RE_END - RE_START)
#define RE_STEP ((double)RE_LENGTH/WIDTH)
#define RE2X(r) (int)((r-RE_START)*BASE_SCALE)

#define IM_START -1
#define IM_END 1
#define IM_LENGTH (IM_END - IM_START)
#define IM_STEP ((double)IM_LENGTH/HEIGHT)
#define IM2Y(i) (int)((i-IM_START)*BASE_SCALE)

#define WIDTH (BASE_SCALE * RE_LENGTH)
#define HEIGHT (BASE_SCALE * IM_LENGTH)

#define INF 2
#define MAX_ITER 1000

#define EGGX_BLACK 0
#define EGGX_WHITE 1

bool not_inf(complex<double> c)
{
    complex<double> z;

    /*
        数列{Zn}を実際にn->∞として計算することは無理なので、
        n->MAX_ITERとして計算している。
    */
    for (int n = 0; n < MAX_ITER; n++) {
        z = z*z + c;

        /*
            |Zn|が2以上に達したら|Zn+1| > |Zn|なので、
            数列は必ず発散する。
        */
        if (abs(z) >= INF)
            return false;
    }
    return true;
}

/*
//C版(複素数を使わず書く)
//引数のa,bはC++版の
//複素数cをc = a + i*bと表したときのa, b。
int not_inf(double a, double b)
{
    int n;
    double re, im;
    re = im = 0;
    for (n = 0; n < MAX_ITER; n++) {
        double tr = re, ti = im;
        re = tr*tr - ti*ti + a;
        im = 2*tr*ti + b;

        if (sqrt(re*re+im*im) >= INF)
            return 0;
        //また、上のif文は以下と同値
        //if (re*re+im*im >= INF*INF)
        //  return 0;
    }
    return 1;
}
*/

void draw(int win)
{
    double re, im;
    for (re = RE_START; re <= RE_END; re += RE_STEP) {
        for (im = IM_START; im <= IM_END; im += IM_STEP) {
            bool f = not_inf(complex<double>(re, im));
            newpen(win, f?EGGX_BLACK:EGGX_WHITE);

            /*
                RE2X,IM2Yを呼び出し、複素平面内の点を
                ウィンドウの座標に変換して描いている。
            */
            pset(win, RE2X(re), IM2Y(im));
        }
    }
}

int main()
{
    int win;

    gsetinitialbgcolor("gray");
    win = gopen(WIDTH, HEIGHT);

    draw(win);

    ggetch();
    gclose(win);
    return 0;
}

なお、ウェブ上に載せられているマンデルブロ集合の図は、たいてい、周囲が色付けされている。通常は、数列が無限大に発散するまでに計算された回数を用いて色付けする。上述のプログラムに色付けの機能を加えるためには、上に示した手順(3)において「{Zn}が発散するならば白」としている部分の処理を変えればよい。

Project Euler Problem 9

Problem 9

a, b, cは全て自然数で、a < b < cかつa + b + c = 1000であるから、
0 < a < 1000/3, a < b < (1000-a)/2, c = 1000 - (a+b)という条件の下で調べれば良い。

証明:
a + b + c = 1000より、c = 1000 - (a+b)となり、b < cに代入すると、
b < 1000 - (a+b)
<=> b < (1000-a)/2
よって、a < b < (1000-a)/2となる。
またこれより、
a < (1000-a)/2
<=> a < 1000/3
よって、0 < a < 1000/3となる。

Scheme

(use srfi-42)

(define n 1000)
(define (p009)
  (print (car (list-ec (: a (floor (/ n 3)))
                       (: b a (floor (/ (- n a) 2)))
                       (:let c (- n a b))
                (if (eq? (+ (* a a) (* b b)) (* c c)))
                (* a b c)))))

(p009)

C++

#include <cstdio>

int main()
{
    for (int a = 1; a < 1000/3; a++)
    for (int b = a; b < (1000-a)/2; b++)
    {
        int c = 1000-(a+b);
        if (a*a+b*b==c*c) {
            printf("%d\n", a*b*c);
            goto end;
        }
    }
end:
    return 0;
}

Project Euler Problem 8

Problem 8

Schemeのコードが、すこぶる醜い。入力数値のリストを作り、先頭から5つ、二番目から5つ、,,,、(リストの要素数-4)番目から5つ、と数値を取って全ての並びを求めている。そうして求めた各リストに対して積を計算し、最大を得た。けれども並びの求め方が、醜い。もっとうまく書けそうだ。

Scheme

(use srfi-1)

(define (p008)
  (define (integer->digit c) (- c (char->integer #\0)))
  (define (input-digits)
    (let ((c (read-char)))
      (cond ((eof-object? c) '())
            ((char-numeric? c)
              (cons (integer->digit (char->integer c)) (input-digits)))
            (else (input-digits)))))
  (define (split-list ls)
    (map (lambda (x) 
           (receive (_ t) (split-at ls x)
             (take t 5)))
         (iota (- (length ls) 4))))
  (print (apply max (map (lambda (x) (apply * x)) (split-list (input-digits))))))

(p008)

C++

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int main()
{
    char c;
    int xs[5], ma;

    ma = 0;
    memset(xs, 0, sizeof(xs));
    while ((c = getchar()) != EOF) {
        if (!isdigit(c))
            continue;
        xs[4] = c-'0';

        int p = 1;
        for (int i = 0; i < 5; i++)
            p *= xs[i];
        ma = max(ma, p);

        for (int i = 0; i < 4; i++)
            xs[i] = xs[i+1];
    }
    printf("%d\n", ma);

    return 0;
}

EGGXを用いたライフゲーム処理系の作成

EGGXを使ってライフゲームの処理系を作る。

以下は、グローバル変数が多い、読みにくいコード。状態が遷移した回数だけgif画像を出力する(要ImageMagick)。

LIM回状態が遷移するか、状態が変わらなかったとき、終了する。ダブルバッファリングなどの洒落た機能は入れて無いので、画面がチラチラするかもしれない。

#include <stdio.h>
#include <string.h>
#include <eggx.h>
#define EGGX_BLACK 0
#define EGGX_WHITE 1

/* 最大100*100マスまで許容する */
#define MAX_SIZE 100

#define CELL_WIDTH 20
#define CELL_HEIGHT 20

#define DEAD 0
#define LIVE 1

/* 最大1000回まで状態を遷移させる */
#define LIM 1000

/* 状態遷移間隔(ミリ秒) */
#define DELAY 200

int win;
int w, h;
int width, height;
int board[MAX_SIZE][MAX_SIZE];
int prev[MAX_SIZE][MAX_SIZE];

void init(void);
int next_state(int y, int x);
void change_cells(void);
void draw_cell(int y, int x);
void draw_cells(void);

void init(void)
{
    int x, y;

    memset(prev, -1, sizeof(prev));
    scanf("%d %d", &w, &h);
    width = w*CELL_WIDTH;
    height = h*CELL_HEIGHT;
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++)
            scanf("%d", &board[y][x]);
}

int next_state(int y, int x)
{
    int i, live;
    int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
    int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

    live = 0;
    for (i = 0; i < 8; i++) {
        int ty = y+dy[i], tx = x+dx[i];
        if (!(0 <= ty && ty < h))   continue;
        if (!(0 <= tx && tx < w))   continue;
        if (board[ty][tx] == LIVE)  live++;
    }

    switch (live) {
        case 2:     return board[y][x];
        case 3:     return LIVE;
        default:    return DEAD;
    }
}

void change_cells(void)
{
    int y, x;
    int buf[MAX_SIZE][MAX_SIZE];

    memset(buf, 0, sizeof(buf));
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++)
            buf[y][x] = next_state(y, x);
    memcpy(board, buf, sizeof(buf));
}

void draw_cell(int y, int x)
{
    int kind;
    int px, py;

    kind = board[y][x];
    newpen(win, kind==DEAD?EGGX_WHITE:EGGX_BLACK);
    px = x*CELL_WIDTH;
    py = (h-1-y)*CELL_HEIGHT;
    fillrect(win, px, py, CELL_WIDTH, CELL_HEIGHT);
}

void draw_cells(void)
{
    int y, x;
    for (y = 0; y < h; y++)
        for (x = 0; x < w; x++)
            if (board[y][x] != prev[y][x])
                draw_cell(y, x);

    newpen(win, EGGX_BLACK);
    drawrect(win, 0, 0, width-1, height-1);
}

int main(void)
{
    int i;

    init();
    win = gopen(width, height);
    for (i = 0; i < LIM; i++) {
        if (memcmp(board, prev, sizeof(board))==0)
            break;

        winname(win, "turn %d", i);
        draw_cells();
        saveimg(win, 0, 0, 0, width-1, height-1, "convert", 16, "img%d.gif", 1000+i);

        memcpy(prev, board, sizeof(board));
        change_cells();
        msleep(DELAY);
    }
    gclose(win);

    return 0;
}

入力例と、それに対応する出力された画像をまとめたgif動画。入力のはじめ一行の二値は、それぞれ幅と高さを意味する。それに続くデータは、0なら死、1なら生を表す。

10 10
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Project Euler Problem 7

Problem 7

これらのプログラムでは、1から順番に素数の数を数えた。けれども、遅延評価を使ったエラトステネスの篩の方が良いかもしれない。

Scheme

(use srfi-1)

(define (prime? n)
  (if (= n 1) #f
      (let loop ((d 2))
        (cond ((> (* d d) n) #t)
              ((zero? (modulo n d)) #f)
              (else (loop (+ d 1)))))))

(define (p007)
  (let loop ((x 1) (c 0))
    (cond ((= c 10001) (print (- x 1)))
          ((prime? x) (loop (+ x 1) (+ c 1)))
          (else (loop (+ x 1) c)))))

(p007)

C++

#include <cstdio>

bool is_prime(int n)
{
    if (n == 1) return false;
    for (int i = 2; i*i <= n; i++)
        if (n%i == 0)
            return false;
    return true;
}

int main()
{
    int x, c;
    x = 1, c = 0;
    for (;;) {
        if (is_prime(x) && ++c == 10001)
            break;
        x++;
    }
    printf("%d\n", x);
    return 0;
}

Project Euler Problem 6

Problem 6

区間[1, n]の各整数の二乗の総和 = n(n+1)(2n+1)/6
区間[1, n]の各整数の総和 = n(n+1)/2

求める答えは|(n(n+1)/2)^2 - n(n+1)(2n+1)/6|となる。

Scheme

(use srfi-1)
(use numbers)

(define (square-of-sum n)
  (let ((sum (* n (+ n 1) 1/2)))
    (* sum sum)))

(define (sum-of-squares n)  
  (* n (+ n 1) (+ (* 2 n) 1) 1/6))

(define (p006)
  (print (- (square-of-sum 100) (sum-of-squares 100))))

(p006)

C++

#include <cstdio>

int square_of_sum(int n)
{
    int t = n*(n+1)/2;
    return t*t;
}

int sum_of_squares(int n)
{
    return n*(n+1)*(2*n+1)/6;
}

int main()
{
    printf("%d\n", square_of_sum(100)-sum_of_squares(100));
    return 0;
}

Project Euler Problem 5

Problem 5

この問題は、Schemeなら瞬殺。

Scheme

(use srfi-1)
(use numbers)

(define (p005)
  (print (apply lcm (iota 20 1))))

(p005)

C++

#include <cstdio>
typedef long long ll;

ll gcd(ll a, ll b)
{
    return b==0?a:gcd(b, a%b);
}

ll lcm(ll a, ll b)
{
    return a*b/gcd(a, b);
}

int main()
{
    ll l = 1;
    for (int i = 2; i <= 20; i++)
        l = lcm(l, i);
    printf("%lld\n", l);
    return 0;
}

Project Euler Problem 4

Problem 4

Scheme

(use srfi-1)
(use srfi-42)
(use numbers)

(define (number->list n)
  (define (body n)
    (if (zero? n) '()
        (cons (modulo n 10) (body (floor (/ n 10))))))
  (if (zero? n) '(0)
      (reverse (body n))))

(define (palindrome? n)
  (let ((ls (number->list n)))
    (equal? ls (reverse ls))))

(define (p004)
  (print (max-ec (: i 100 1000) (: j i 1000) (:let n (* i j))
                 (if (palindrome? n)) n)))

(p004)

C++

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

bool is_palindrome(int n)
{
    int rev = 0, buf = n;
    do {
        rev = 10*rev + buf%10;
        buf /= 10;
    } while(buf != 0);
    return rev == n;
}

int main()
{
    int ma = 0;
    for (int i = 100; i < 1000; i++) {
        for (int j = i; j < 1000; j++) {
            int t = i*j;
            if (is_palindrome(t))
                ma = max(ma, t);
        }
    }
    printf("%d\n", ma);
    return 0;
}

Project Euler Problem 3

Problem 3

Scheme

(use srfi-1)

(define (prime-factors n)
  (if (= n 1) '()
      (let loop ((d 2))
        (if (zero? (modulo n d)) (cons d (prime-factors (/ n d)))
            (loop (+ d 1))))))

(define (p003)
  (print (apply max (prime-factors 600851475143))))

(p003)

C++

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

ll lpf(ll n)
{
    if (n == 1)
        return 1;
    for (ll d = 2;; d++)
        if (n%d==0)
            return max(d, lpf(n/d));
}

int main()
{
    printf("%lld\n", lpf(600851475143));
    return 0;
}

Project Euler Problem 2

Problem 2

Scheme

(use srfi-1)

(define (fibs)
  (let loop ((a 0) (b 1) (ls '()))
    (if (>= a 4e6) ls
        (loop b (+ a b) (cons a ls)))))

(define (p002)
  (print (apply +
                (filter (lambda (x) (zero? (modulo x 2)))
                        (fibs)))))

(p002)

C++

#include <cstdio>

int main()
{
    int a, b;
    int sum = 0;
    a = 0, b = 1;
    while (a < 4000000) {
        if (a%2 == 0)
            sum += a;
        int tmp = a;
        a = b;
        b += tmp;
    }
    printf("%d\n", sum);
    return 0;
}

Project Euler Problem 1

Problem 1

Schemeの処理系はChicken Scheme。

現状適当に表示することにしたけれど、BloggerでSchemeのコードを色付けするシンタックスハイライターってないのかしら。

Scheme

(use srfi-1)

(define (p001)
  (print (apply +
                (filter (lambda (x) (or (zero? (modulo x 3)) (zero? (modulo x 5))))
                        (iota 1000)))))

(p001)

C++

#include <cstdio>

int sum(int x, int n)
{
    int t = n/x;
    return x*t*(t+1)/2;
}

int main()
{
    printf("%d\n", sum(3, 999)+sum(5, 999)-sum(15, 999));
    return 0;
}

Arch Linux上のxfce terminalで日本語を表示する

Arch Linuxをアップデートしようと思ったら、壊れてしまった。データを救出するのは面倒だったので、再インストール。

しかし、xfce terminalで日本語を表示できず、躓いてしまった。~/.bashrcに「export LC_CTYPE="en_US.UTF-8"」を入れて、一生懸命条件を変えたが、xfce terminalでは日本語が表示されなかった。gvimなどにおいては、表示されたのだけれども……。

そうして、解決方法を調べていたら~/.bashrcに書くのではなく、~/.xprofileというファイルを作って、その中で「export LC_CTYPE="en_US.UTF-8"」を書けば良いことがわかった。(情報源:http://fixunix.com/slackware/237547-xfce-utf-8-support.html)

それにしても、~/.bashrcに書いたとき、中途半端にgvimなどでは日本語が表示されていたから、~/.xprofileに辿り着くまでに時間がかかった。

SchemeとC++でProject Eulerに挑戦

Project Euler

今現在、61問だけ解いた。けれども、Schemeの勉強も兼ねてProject Eulerの問題を解き直す。また、所々HaskellゃPythonを使って楽をしていたので、とりあえずは全問SchemeとC++での解答を書いていくつもり。

Arch LinuxにMozc(Google IME)を入れる

頑張ってArch LinuxにMozcを入れるか、っと思っていたら、なんのことはない、パッケージを作ってくれている人が居た。ありがたい。

AUR (en) - mozc

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

はじめ

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