fc2ブログ



マトリョーシカ

2007.10.04 15:13  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題 マトリョーシカ

概要

高さが h 半径が r の筒状の人形が n + m 個与えられる。高さ h 半径 r の人形は x < h かつ y < r を満たす高さ x 半径 y の人形を含むことができる。これらの人形の中から複数選んで k 個の人形の入れ子(マトリョーシカ)を作るとき、k の最大値を求めよ。

解法

高さ(または半径)で全ての人形をソートします。ソートした人形に対して半径(または高さ)についての最長増加部分列の長さを動的計画法により求めます。


サインプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 200
005 
006 class Doll{
007     public:
008     int h, r;
009     Doll(){}
010     Doll( int h, int r ): h(h), r(r){}
011     
012     bool operator < ( const Doll &d ) const {
013         if ( r == d.r ) return h < d.h;
014         else return r < d.r;
015     }
016 };
017 
018 Doll dolls[MAX+1];
019 int size;
020 
021 int lis(){
022     int T[MAX+1];
023     T[0] = 0;
024     dolls[0] = Doll( 0, 0 );
025     for ( int i = 1; i <= size; i++ ){
026         int maxi = 0;
027         for ( int j = 0; j <= i - 1; j++ ){
028             if ( T[j] > T[maxi] &&
029             dolls[j].h < dolls[i].h && dolls[j].r < dolls[i].r ){
030                 maxi = j;
031             }
032         }
033         T[i] = T[maxi] + 1;
034     }
035     
036     int maxv = 0;
037     for ( int i = 1; i <= size; i++ ) maxv = max( maxv, T[i] );
038     
039     return maxv;
040 }
041 
042 bool input(){
043     int n, m, h, r;
044     cin >> n;
045     if ( n == 0 ) return false;
046     
047     dolls[0] = Doll(0, 0);
048     
049     for ( int i = 1; i <= n; i++ ){
050         cin >> h >> r;
051         dolls[i] = Doll( h, r );
052     }
053     cin >> m; size = n + m;
054     for ( int i = n + 1; i <= size; i++ ){
055         cin >> h >> r;
056         dolls[i] = Doll( h, r );
057     }
058     return true;
059 }
060 
061 int main(){
062     while(input()){
063         sort( dolls, dolls + size + 1);
064         cout << lis() << endl;
065     }
066     return 0;
067 }
スポンサーサイト



テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




お城の堀

2007.09.29 18:23  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題09 お城の堀

概要

2次元配列上に地面'.', 堀'#', 天守閣'&' で表されたお城の見取図が与えられ、忍者が見取図の外側から天守閣(見取図上に1つしかない)に至るまでに、堀から這い上がらなくてはならない最小回数を求めよ。忍者は堀の中および地面を東西南北4方向に動くことができる。例えば

.###.
#...#
#.&.#
#...#
.###.

の見取図では、答えは 1

#######
#.....#
#.###.#
#.#&#.#
#.###.#
#.....#
#######

の見取図では、答えは 2

######
######
##..##
##&.##
##..##
######
######

の見取図では、答えは 1
(※忍者は堀を泳ぐことができるので、2 ではない)

########################################
#......................................#
#..#########...######################..#
#..#.......#...#....................#..#
#..#.......#...#.##################.#..#
#..#.####..#...#.#..........#.#...#.#..#
#..#.#..#..#...#.#....#######.#...#.#..#
#..#.####..#...#.#....#.......#...#.#..#
#..#.......#...#.#....#.#####.#...#.#..#
#..#.......#...#.#....#.#.&.#.#...#.#..#
#..#########...#.######.#####.#####.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#.#................#.#..#
#..............#.##################.#..#
#..............#....................#..#
#..............######################..#
#......................................#
#......................................#
########################################

の見取図では、答えは 4


見取図のサイズは最大 100 × 100 である。

解法

天守閣'&'の位置(ci, cj)から深さ優先探索を反復することによって解くことができます。
(ci, cj) と隣接する地面、それらに隣接する地面...を色0で塗りつぶします。
色0に隣接する堀、それらに隣接する堀...を色1で塗りつぶします。
色1に隣接する地面、それらに隣接する地面...を色2で塗りつぶします。
色2に隣接する堀、それらに隣接する堀...を色3で塗りつぶします。
.
.
.
この処理の過程で、見取図からはみ出た時点の色nの半分が解となります。

サンプルプログラム

001 #include<iostream>
002 #include<string>
003 #define MAX 100
004 using namespace std;
005 #define GROUND '.'
006 #define CASTLE '&'
007 #define MOAT '#'
008 #define INFTY (1<<21)
009 
010 int H, W;
011 char G[MAX+2][MAX+2];
012 int T[MAX+2][MAX+2];
013 pair<int, int> castle;
014 
015 bool fill( int i, int j, int color, char target ){
016     T[i][j] = color;
017     if ( i == 0 || j == 0 || i == H + 1 || j == W + 1 ) return true;
018     static const int di[4] = {0, -1, 0, 1};
019     static const int dj[4] = {1, 0, -1, 0};
020     int ni, nj;
021     for ( int r = 0; r < 4; r++ ){
022         ni = i + di[r]; nj = j + dj[r];
023         if ( (G[ni][nj] == target && T[ni][nj] == INFTY) || T[ni][nj] < color ){
024             if ( fill( ni, nj, color, target ) ) return true;
025         }
026     }
027     return false;
028 }
029 
030 int compute(){
031     int color = 0;
032     
033     for ( int i = 0; i < H + 2; i++ ){
034         for ( int j = 0; j < W + 2; j++ ) T[i][j] = INFTY;
035     }
036     
037     while(1){
038         if ( fill( castle.first, castle.second, color, GROUND ) ) return color;
039         color++;
040         if ( fill( castle.first, castle.second, color, MOAT ) ) return color;
041         color++;
042     }
043 }
044 
045 bool initialize(){
046     cin >> W >> H;
047     if ( W == 0 && H == 0 ) return false;
048     for ( int i = 0; i < H + 2; i++ ) G[i][0] = G[i][W+1] = GROUND;
049     for ( int j = 0; j < W + 2; j++ ) G[0][j] = G[H+1][j] = GROUND;
050     
051     for ( int i = 1; i <= H; i++ ){
052         for ( int j = 1; j <= W; j++ ) {
053             cin >> G[i][j];
054             if ( G[i][j] == CASTLE ) {
055                 castle = make_pair(i, j);
056                 G[i][j] = GROUND;
057             }
058         }
059     }
060     return true;
061 }
062 
063 main(){
064     while(initialize()){
065         cout << compute()/2 << endl;
066     }
067 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




カードの総和

2007.09.28 10:27  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題07 カードの総和

概要

m (m < 8)種類(各種類のカードは複数(<11)存在する)のカードの集合から数枚カードを選んで、カードに書かれた数字の合計が n になるような組み合わせ数を出力せよ。

解法

再帰関数によって、全てのカードの組み合わせについての数字の合計を試します。
再帰関数内では、k 種類目のカードを 0 枚から amout[k] (k 種類目のカードの枚数)枚選んで、
k + 1 種類目のカードを選ぶ処理に移ります。
この過程で、選んだカードにかかれた数字の合計 v を計算していき、v が n と等しくなったとき、
カウンターを増やします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 7
004 
005 int m, n, counter;
006 int value[MAX], amount[MAX];
007 
008 void recursive( int k, int v ){
009     if ( v == n ) {
010         counter++; return;
011     } else if ( v > n || k >= m ) return;
012     
013     for ( int a = 0; a <= amount[k]; a++ ){
014         recursive( k + 1, v + value[k]*a );
015     }
016 }
017 
018 int main(){
019     while( cin >> m, m ){
020         for ( int i = 0; i < m; i++ ){
021             cin >> value[i] >> amount[i];
022         }
023         int g; cin >> g;
024         for ( int i = 0; i < g; i++ ){
025             cin >> n;
026             counter = 0;
027             recursive(0, 0);
028             cout << counter << endl;
029         }
030     }
031     return 0;
032 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




マス目

2007.09.28 09:55  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題04 マス目

概要

各要素が 0 または 1 である n × n (n < 256)の2次元配列が与えられ、上下、左右、または対角線方向に並んだ 1 の列のうち、長さが最大のものの長さを出力せよ。

例えば、以下のような入力に対しては、4 を出力する。

00011
00101
01000
10101

解法

動的計画法で解きます。
T[i][j][k] を G[i][j] から k 方向(k は右上、上、左上、左の4種類)に 1 が連続する数とします。
これを各列(j)を左から右、各行(i)を上から下という順番で計算していきます。
G[i][j] が 0 であれば、T[i][j][k] (k = 0, 1, 2, 3) は 0 となり、
G[i][j] が 1 であれば、
T[i][j][0] = T[i-1][j+1][0] + 1 (右上),
T[i][j][1] = T[i-1][j][1] + 1, (上)
T[i][j][2] = T[i-1][j-1][2] + 1 (左上),
T[i][j][3] = T[i][j-1][3] + 1 (左)
となります。
T の要素の最大値が答えとなります。

サンプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 255
005 
006 int n;
007 char G[MAX+2][MAX+2];
008 int T[MAX+2][MAX+2][4];
009 
010 void compute(){
011     for ( int i = 0; i < n + 2; i++ ){
012         for ( int j = 0; j < n + 2; j++ ){
013             for ( int k = 0; k < 4; k++ ) T[i][j][k] = 0;
014         }
015     }
016     
017     static const int di[4] = {-1, -1, -1, 0};
018     static const int dj[4] = {1, 0, -1, -1};
019     
020     int maxv = 0;
021     
022     for ( int i = 0; i <= n; i++ ){
023         for ( int j = 0; j <= n; j++ ){
024             if ( G[i][j] == '1' ){
025                 for ( int k = 0; k < 4; k++ ){
026                     T[i][j][k] = T[i+di[k]][j+dj[k]][k] + 1;
027                     maxv = max( maxv, T[i][j][k] );
028                 }
029             }
030         }
031     }
032     
033     cout << maxv << endl;
034 }
035 
036 main(){
037     while(cin >> n, n){
038         for ( int i = 1; i <= n; i++ ){
039             for ( int j = 1; j <= n; j++ ) cin >> G[i][j];
040         }
041         compute();
042     }
043 }

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |




パソコン甲子園2007予選 

2007.09.28 01:15  パソコン甲子園 2007

パソコン甲子園2007予選問題

番号問題難易度点数
01 キャンディーとクラス期 3
02 視力検査 3
03 双子素数 8
04 マス目 ★☆ 8
05 ボウリングのスコア計算 ★★ 8
06 三角形と円 ★★★ 8
07 カードの総和 ★★☆ 8
08 スパイダー人 ★★★ 18
09 お城の堀 ★★★ 18
10 マトリョーシカ ★★★ 18


パソコン甲子園2007の予選が開催されました。問題は計10問。問題の質は良くなってきたと思います。問題01,02,06以外は、ACM/ICPCの国内予選に出てもおかしくない内容だと思います。ということで、簡単な問題も含めて解説したいと思います(※紹介するサンプルプログラムは審判データに対して正しい答えを出力することを保障するものではありません)。

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(2) | トラックバック(1) | ↑ページトップ |




パソコン甲子園2007予選 3点問題(基礎)

2007.09.28 01:07  パソコン甲子園 2007

パソコン甲子園2007予選問題

問題01 キャンディーとクラス旗

概要

n個のキャンディがあり、これらを39人の生徒が順番に1個ずつ取っていく。生徒は3C01から3C39までの生徒番号をそれぞれもち、最後のキャンディを取った生徒番号を出力せよ。

解法

キャンディの数を生徒の数で割った余りを計算し対応する生徒番号を出力します。
ただし、キャンディの数が生徒数で割り切れる場合は、最後の生徒番号を出力することに注意が必要です。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 main(){
005     static const int nstudent = 39;
006     int ncandy, target;
007     cin >> ncandy;
008     target = ncandy % nstudent;
009     if ( target == 0 ) target = nstudent;
010     cout << "3C";
011     if ( target < 10 ) cout << "0";
012     cout << target << endl;
013 }



問題02 視力検査

概要

複数の人の視力検査の結果を入力として、視力判定表に基づいて各判定にあてはまる人数を左右の視力別に出力せよ。

解法

各判定A, B, C, Dにおける左右の該当人数を保持する4×2の整数型配列を用意し、
分岐処理によって人数をカウントしていきます。

サンプルプルグラム

001 #include<iostream>
002 using namespace std;
003 #define A 0
004 #define B 1
005 #define C 2
006 #define D 3
007 #define LEFT 0
008 #define RIGHT 1
009 
010 main(){
011     int T[4][2];
012     for ( int i = 0; i < 4; i++ ) T[i][0] = T[i][1] = 0;
013     double left, right;
014     while( cin >> left >> right ){
015         if ( 1.1 <= left) T[A][LEFT]++;
016         if ( 1.1 <= right) T[A][RIGHT]++;
017         if ( 0.6 <= left && left < 1.1 ) T[B][LEFT]++;
018         if ( 0.6 <= right && right < 1.1 ) T[B][RIGHT]++;
019         if ( 0.2 <= left && left < 0.6 ) T[C][LEFT]++;
020         if ( 0.2 <= right && right < 0.6 ) T[C][RIGHT]++;
021         if ( left < 0.2 ) T[D][LEFT]++;
022         if ( right < 0.2 ) T[D][RIGHT]++;
023     }
024     
025     for ( int i = 0; i < 4; i++ ) {
026         cout << T[i][0] << " " << T[i][1] << endl;
027     }
028 }



問題03 双子素数

概要

n以下の双子素数(差が2となる素数の組)で最大のものを出力せよ。

解法

エラトステネスの篩などで素数表Tをつくり、入力nから5に向かってT[i] と T[i-2] が共に素数かどうかを調べます。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 
004 #define LIMIT 10000
005 
006 void eratos ( int n, bool prime[]){
007     for ( int i = 0; i <= n; i++ ) prime[i] = false;
008     for ( int i = 3; i <= n; i += 2 ) prime[i] = true;
009     prime[2] = true;
010     int limit = (int)sqrt((double)n) + 1;
011     for ( int i = 3; i <= limit; i += 2 ){
012         if ( !prime[i] ) continue;
013         for ( int j = i + i; j <= n; j += i ) prime[j] = false;
014     }
015 }
016 
017 bool prime[LIMIT+1];
018 
019 void compute( int n ){
020     int i;
021     for ( i = n; i >= 5; i-- ){
022         if ( prime[i] && prime[i-2] ) break;
023     }
024     cout << i - 2 << " " << i << endl;
025 }
026 
027 main(){
028     eratos(LIMIT, prime);
029     int n;
030     while ( cin >> n, n) compute(n);
031 }


テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |