fc2ブログ



カードの総和

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) | ↑ページトップ |