カード

パソコン甲子園 2006 カード

問題はこちら

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

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



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

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

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

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


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

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

#include<iostream>
using namespace std;
#define MAX 100
#define INFTY (1<<24)

struct Card{ int top, bottom; };

Card C[MAX+1];
int N;

int getCost(){
    int cost[MAX+1][MAX+1];
    for ( int i = 1; i <= N; i++ ){
        for ( int j = 1; j <= N; j++ ) cost[i][j] = INFTY;
    }
    for ( int i = 1; i <= N; i++ ) cost[i][i] = 0;

    for ( int j = 1; j <= N-1; j++ ){
        for ( int i = 1; i <= N-j; i++ ){
            for ( int k = i+1; k <= i+j; k++ ){
                int mul = C[i].top * C[k-1].bottom * C[k].top * C[i+j].bottom;
                cost[i][i+j] = min( cost[i][i+j], cost[i][k-1] + cost[k][i+j] + mul );
            }
        }
    }

    return cost[1][N];
}

main(){
    cin >> N;
    for ( int i = 1; i <= N; i++ ) cin >> C[i].top >> C[i].bottom;
    cout << getCost() << endl;
}

ぐるぐる模様

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

パタン（数列）が発見できればプログラムは比較的簡単になります。
まず、塗りつぶしていく方向は、↑→↓←の繰り返しであるとがわかります。
次に、塗りつぶす幅を考えます。
例えば、各数字を#の幅だとすると、 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 

ルパン四世

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

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

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

例：蔵の数 n が４の場合

state	bit	意味
0	0000	どの蔵も破られていない
1	0001	1 番目の蔵を破った状態
2	0010	2 番目の蔵を破った状態
3	0011	1, 2 番目の蔵を破った状態
4	0100	3 番目の蔵を破った状態
5	0101	1, 3 番目の蔵を破った状態
6	0110	2, 3 番目の蔵を破った状態
7	0111	1, 2, 3 番目の蔵を破った状態
8	1000	4 番目の蔵を破った状態
.	.	...
.	.	...
15	1111	全ての蔵を破った状態

この F[][] を、state が 0 から 2ⁿ - 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();
}

パソコン甲子園 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