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