パソコン甲子園 2003 問題 019

[問題]
昨年他界した曽祖父の遺品を整理していたところ、次のような紙がでてきました。

紙の裏には「最初の数だけ前に進んで、次の数の角度だけ右にまわる（負の数は左にまわる）、それ以降はその繰り返し」とメモがしてあります。祖母によれば「三本松」は、町のちょうど中心にあったそうです。しかし、今はビルや家が立ち並んでいて、ここに書いてあるとおりに歩くことはできません。地図の上で宝のある場所を探してください。

1 歩は 1m だとします。入力データは、進む歩数と回転する角度を書いた行が並んでいて、最後に「0,0」という行があります。最後まで指示どおりに歩いたときに着いた場所を「街の中心から東へ x m, 北へ y m 」のように測り、その x と y を表示して終了するプログラムを作成して下さい。西および南の場合は x, y は負の値となります。x, y ともに整数部を表示して下さい。

[入力]
歩数（100以下の正の整数）　回転角度(-180 以上 180 以下の整数)が半角カンマ区切りで与えられます。

[出力]
x, y をそれぞれ１行に出力して下さい。

[入力例]

56,65
97,54
64,-4
55,76
42,-27
43,80
87,-86
55,-6
89,34
95,5
0,0

[出力例]

171
-302

[解説]
与えられる入力は、現在地から進む距離 length と、"次のステップでの角度"を計算するための angle であることに注意しましょう。また、与えられる角度の単位は度(degree)なので、三角関数を使う場合はラジアンに変換する必要があります。

[プログラム例]

// @author yutaka C++
#include<stdio.h>
#include<cmath>

#define PI 3.14159265358979323846

using namespace std;

int length, angle, currentAngle;
double px, py;

void walk(){
    px += length * cos(currentAngle * PI / 180.0);
    py += length * sin(currentAngle * PI / 180.0);
    currentAngle -= angle;
}

main(){
    px = py = 0;
    currentAngle = 90;
    
    while (1){
        scanf("%d,%d", &length, &angle);
        if ( length == 0 && angle == 0 ) break;
        walk();
    }
    
    printf("%d\n%d\n", (int)px, (int)py);
}

パソコン甲子園 2003 問題 030

[問題]
図のようなマス目の「紙」があり、(1, 2)のように x, y の値の対でその上の位置を示すことにします。値は 0 から始まる整数とします。

この「紙」にインキを滴下します。インキ滴には「大」「中」「小」の３サイズがあり、インキ滴の落ちた地点を中心に図のように周囲も色がつきます。図で☆が中心、○が色の滲む範囲です。

「紙」は、最初は「まっしろ」つまり、どのマスも色の濃さを示す値が 0 とします。インキ滴が落ちるごとに値が 1 ずつ増えていきます。「小の滴」が (1, 2)、「中の滴」が (3, 2) に落ちた場合、各マスの値は次図の左部のようになります。なお空白は値 0 を示します。滲む範囲が紙の外にもなる場合は、紙の外部を無視して下さい。

例えば、白紙に、「小の滴」を (8, 0) に落とした場合は、次図の右部のように y = -1 に相当する部分を無視することになります。同じ場所に複数のインキ滴が落ちることもありえます。

落とすインキ滴」の x, y, サイズ（小 = 1, 中 = 2, 大 = 3）を入力として読み込んで、色のついてない部分（まだ滲んでこない部分）のマス目の個数と、一番濃いマス目の濃さを出力するプログラムを作成して下さい。なお、「紙」の大きさを 10 × 10 とします。滴下される点の位置を (x, y) とすると、( 0 ≦ x ＜ 10 ), ( 0 ≦ y ＜ 10 ) です。

[入力]

x1,y1,size
x2,y2,size
   .
   .
   .

[出力]
色のついていない部分のマス目の個数を第１行目に。１番濃いマス目の濃さを第２行目に出力して下さい。

[入力例]

2,5,3
3,6,1
3,4,2
4,5,2
3,6,3
2,4,1

[出力例]

77
5

[解説]
この類の問題を解くためのプログラムでは、原点（インキを落とす座標）からの相対座標を求めるために、if 文をごちゃごちゃに駆使し、プログラムが汚くなってしまうケースがよく見うけられます。ポイントは以下の２点です。

• 紙からインキがはみ出るか否かを調べることを避けるために、いわゆる"番兵"として、紙を表す２次元配列のサイズを x 軸, y 軸それぞれについて 4 づつ増やします（下図参照）。ここで、インキを落とす範囲は、2 ≦ x ≦ 11、 2 ≦ y ≦ 11　となります。番兵の領域に滲んだインキがはみ出ても、配列のサイズを超えることはありません。



• インキが落とされた原点 (x, y) からの相対座標を求めるために、(x, y) からの差分を記録した配列 dx[], dy[] を用意します（下図参照）。左図は x, y 座標の差分を表します。配列のインデックスの順番を、右図のようにしておくと便利です（プログラム例参照）。

[プログラム例]

// @author yutaka C++
#include<stdio.h>
#define MAX 10

using namespace std;

int paper[MAX + 4][MAX + 4]; // +4 = 番兵

void initialize(){
    for ( int y = 0; y < MAX + 4; y++ ){
        for ( int x = 0; x < MAX + 4; x++ ) paper[y][x] = 0;
    }
}

void drop( int x, int y, int size ){
    x += 2; y += 2; // 番兵の分を足す
    
    static const int dx[13] = {0, 1, 0, -1, 0, 1, -1, -1, 1, 2, 0, -2, 0};
    static const int dy[13] = {0, 0, -1, 0, 1, -1, -1, 1, 1, 0, -2, 0, 2};
    
    int limit = size * 4 + 1;
    for ( int r = 0; r < limit; r++ ) paper[y + dy[r]][x + dx[r]]++;
}

main(){
    int x, y, size;
    int numberOfEmpty = 0;
    int maxValue = 0;
    
    initialize();
    
    while ( scanf("%d,%d,%d", &x, &y, &size) != EOF ){
        drop( x, y, size );
    }
    
    for ( int y = 2; y <= 11; y++ ){
        for ( int x = 2; x <= 11; x++ ){
            if ( paper[y][x] == 0 ) numberOfEmpty++;
            if ( paper[y][x] > maxValue ) maxValue = paper[y][x];
        }
    }
    
    printf("%d\n%d\n", numberOfEmpty, maxValue);
}