fc2ブログ



カード

2009.07.14 19:26  パソコン甲子園 2006

パソコン甲子園 2006 カード


連鎖行列積問題の解法と同様に動的計画法で解きます。

例えば、下図のように5枚のカードの山があるとします。

パソコン甲子園 2006 カード


まず最初に、隣り合う2組の山を重ねるときの最小のコストを計算します(j = 1)。
i を 重ねる山の左端の山とすると、i = 1, 2, 3, 4 について計算します。

つぎに、隣り合う3組の山を重ねるときの最小のコストを計算します(j = 2)。
i = 1, 2, 3 について計算します。

つぎに、隣り合う4組の山を重ねるときの最小のコストを計算します(j = 3)。
i = 1, 2 について計算します。

同様に、隣り合うN組の山を重ねるときの最小のコストを計算します(j = N-1)。
i = 1 について計算します。


各 j の値での最小コストの計算方法を考えます。
例えば、j = 3, i = 1 の場合の最小コストは以下の中で最小のものとなります:

  • カードの山[1]とカードの山[2,3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+1)
  • カードの山[1,2]とカードの山[3,4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+2)
  • カードの山[1,2,3]とカードの山[4]をそれぞれ重ねるのに要した最小コスト + それら2つの山を重ねるコスト (k = i+3 = i+j)

スポンサーサイト



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

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




ぐるぐる模様

2007.07.27 22:17  パソコン甲子園 2006


[問題] パソコン甲子園 2006 ぐるぐる模様



整数 n が与えられ、n × n のグリッド上にぐるぐる模様を描きなさい、という問題です。
例えば n が 1 ~ 9 までの出力はそれぞれ以下のようになります。('.' は空白を表すことにします)

n = 1

#

n = 2

##
#. 

n = 3

###
#.#
#.#

n = 4

####
#..#
#..#
#.##

n = 5

#####
#...#
#.#.#
#.#.#
#.###

n = 6

######
#....#
#.##.#
#.#..#
#.#..#
#.####

n = 7

#######
#.....#
#.###.#
#.#.#.#
#.#.#.#
#.#...#
#.#####

n = 8

########
#......#
#.####.#
#.#..#.#
#.#..#.#
#.#.##.#
#.#....#
#.######

n = 9

#########
#.......#
#.#####.#
#.#...#.#
#.#.#.#.#
#.#.#.#.#
#.#.###.#
#.#.....#
#.#######

問題の定義が曖昧な気もしますが、左下角から時計回りに'#'で埋めて下さいということです。

なにやら面倒な問題ですが、いかに楽をして解くかを考えなければなりません。
この問題の考えられる解法は、
①グリッド上を探索っぽく塗りつぶす
②パタンを発見して塗りつぶす
など
がありますが、これを探索っぽく、壁にぶつかったらどうのこうのと実装すると、
ハマりやすいと思います。実際多くの学生がハマってしまいました。

パタン(数列)が発見できればプログラムは比較的簡単になります。
まず、塗りつぶしていく方向は、↑→↓←の繰り返しであるとがわかります。
次に、塗りつぶす幅を考えます。
例えば、各数字を#の幅だとすると、 n = 8 の場合は、
88866442
と表されます。これは、
↑に8、→に8、↓に8、←に6、↑に6、→に4、...塗りつぶす、という意味です。
n = 9 の場合は、
999775533
と表されます。

他のnに対しても試してみると、以下のような数列になることが分かります。

n n n (n-2) (n-2) (n-4) (n-4) . . .

そして、数列の長さが n となります。

「座標(i, j)から、d 方向 に向かって幅 w だけ塗りつぶす」
といった関数またはルーチンを、繰り返すだけです。

※ n = 2 のときの出力に注意する必要があります。
本戦で wrong answer をもらった人は、n = 2 の出力が間違っていた可能性が高いです。

以下解答例です。

001 #include<stdio.h>
002 
003 int n;
004 char G[100][100]; // grid
005 static int di[4] = {-1, 0, 1, 0};
006 static int dj[4] = {0, 1, 0, -1};
007 
008 int main(){
009     int dir, width, i, j, a, w;
010     scanf("%d", &n);
011     
012     for ( i = 0; i < n; i++ )
013         for ( j = 0; j < n; j++ ) G[i][j] = ' ';
014     
015     width = n - 1;
016     i = width; j = dir = 0;
017     
018     for ( a = 1; a <= (n + n % 2); a++, dir = (dir + 1) % 4 ){
019         for ( w = 0; w <= width; w++ ) G[i+di[dir]*w][j+dj[dir]*w] = '#';
020         i += di[dir] * width;
021         j += dj[dir] * width;
022         if ( a % 2 == 1 && a >= 3 ) width -= 2;
023     }
024     
025     for ( i = 0; i < n; i++ ){
026         for ( j = 0; j < n; j++ ) printf("%c", G[i][j]);
027         printf("\n");
028     }
029 }
030 
031 

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

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




ルパン四世

2006.12.05 23:32  パソコン甲子園 2006

パソコン甲子園2006、唯一どのチームにも解かれなかった問題です。参考記事

この問題は「巡回セールスマン問題」に帰着できるので、ちょっと勉強すれば簡単に解けます。もちろん、問題のサイズである蔵の数が最高でも 15 個なので、力任せのアルゴリズムでは解くことができません。巡回セールスマン問題は、分岐限定法や遺伝的アルゴリズムなど、様々な方法で解くことができますが、問題のサイズが高々 20 くらいまでなら動的計画法で厳密解を求めることが可能です。

以下の解答プログラムでは、F[][] という配列を用いてます。
ここで、F[state][i] には、
状態 state で i 番目の蔵に至るまでにかかった時間を記録します。
ここで、state は「どの蔵がすでに破られたか」を表す数で、以下の表のように 0 ~ 2n - 1 の数をわりあてます。

例:蔵の数 n が4の場合
statebit意味
00000どの蔵も破られていない
100011 番目の蔵を破った状態
200102 番目の蔵を破った状態
300111, 2 番目の蔵を破った状態
401003 番目の蔵を破った状態
501011, 3 番目の蔵を破った状態
601102, 3 番目の蔵を破った状態
701111, 2, 3 番目の蔵を破った状態
810004 番目の蔵を破った状態
.....
.....
151111全ての蔵を破った状態


この F[][] を、state が 0 から 2n - 1 に向かって、動的計画法により計算していきます。

#include<iostream>
#define INFTY 1e+1000
#define MAX 15
#define SMAX 1 << MAX

using namespace std;

struct StoreHouse{
    int id, dist, nbox;
};

int nstore; // the number of storehouse
StoreHouse stores[MAX];
double F[SMAX][MAX]; // cost table
int W[SMAX]; // total wight in states
pair<int, int> P[SMAX][MAX]; // for path generation

double getCost( int source, int target, int state ){
    return abs(stores[source].dist - stores[target].dist )/(2000.0/(70 + W[state]));
}

void compute(){
    int smax = 1 << nstore;
    
    for ( int state = 1; state < smax; state++ ){
        for ( int j = 0; j < nstore; j++ ){
            F[state][j] = INFTY;
            P[state][j] = make_pair(-1, -1);
        }
    }
    
    for ( int j = 0; j < nstore; j++ ) F[1 << j][j] = 0;
    
    for ( int state = 1; state < smax; state++ ){
        for ( int i = 0; i < nstore; i++ ){
            if ( ! (( 1 << i ) & state ) ) continue;
            for ( int j = 0; j < nstore; j++ ){
                if ( ( 1 << j ) & state ) continue;
                double cost = F[state][i] + getCost(i, j, state);
                if ( cost < F[state|(1 << j)][j] ){
                    F[state|(1 << j)][j] = cost;
                    P[state|(1 << j)][j] = make_pair(state, i);
                }
            }
        }
    }
    
    int endpoint = 0;
    for ( int i = 1; i < nstore; i++ ){
        if ( F[smax-1][i] < F[smax-1][endpoint] ) endpoint = i;
    }
    
    pair<int, int> pre = make_pair(smax-1, endpoint);
    int path[MAX];
    for ( int i = 0; pre.first != -1; pre = P[pre.first][pre.second], i++ ){
        path[i] = stores[pre.second].id;
    }
    
    for ( int i = 0; i < nstore; i++ ){
        if ( i ) cout << " ";
        cout << path[nstore - i - 1];
    }
    cout << endl;
}

void input(){
    cin >> nstore;
    for ( int i = 0; i < nstore; i++ ){
        cin >> stores[i].id >> stores[i].dist >> stores[i].nbox;
    }
}

void init(){
    int limit = 1 << nstore;
    for ( int state = 1; state < limit; state++ ){
        int sum = 0;
        for ( int i = 0; i < nstore; i++ ){
            if ( state & (1 << i) ) sum += (stores[i].nbox * 20);
        }
        W[state] = sum;
    }
}

main(){
    input();
    init();
    compute();
}

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




パソコン甲子園 2006 本戦

2006.11.12 14:01  パソコン甲子園 2006

今年もパソコン甲子園が会津大学で開催されました。年々出場者も増え、問題の質やレベルも上がってきました。今年の問題セットは今まででも一番おもしろく難易度が高かったように思います(相変わらずつっこみ所は満載でしたが)。それと、いい加減、「パソコン甲子園」という名前を変えてほしいですね。せめて、「プログラミング甲子園」ですよ

問題はここから解答できます。

ID 問題 難易度 考察
01 パターンの回転 Pending
02 出口調査 Pending
03 短針と長針の出会うころ… Pending
04 身長の度数分布 Pending
05 平方採中法 Pending
06 陸上競技大会 Pending
07 ヘビ ★☆ Pending
08 バス路線 ★☆ Pending
09 ぐるぐる模様 ★★ Pending
10 素数の性質 ★☆ Pending
11 織女と牽牛 ★★ Pending
12 パケット転送 ★★☆ Pending
13 カード ★★★
14 ルパン四世 ★★★★☆
15 福縞軒 ★★★☆ Pending

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

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