fc2ブログ



ビーカー

2008.09.16 21:55  パソコン甲子園 2008


問題 パソコン甲子園2008 10



いろいろな容量のビーカーがあります。はじめに、その中の一番容量が大きなビーカーに水を満タンに注ぎます。次に、以下のルールに従いビーカーの水を他のビーカーに写し変えていきます:

  • ビーカーに入っている水は、残さずに全て他のビーカーに移さなければならない。ただし、一個のビーカーに水を全部移せない場合は、複数のビーカーに分けて移すことができる


  • ビーカーに水を入れるとき、満タンになるまで水を注がなければならない。また、水をこぼしてはならない。


  • 複数のビーカーから同じビーカーに一度に水を注いではならない。

  • 同じビーカーには一度しか水を注いではならない。



このルールに従ったとき、すべてのビーカーに水を注ぐことができるかどうかを判定して下さい。ビーカーの数 n は 1 以上 50 以下です。



解説

問題が分かりづらいですが、「すべてのビーカーに水を注ぐことができるか」というのは「水を移し変える一連の操作の過程で、すべてのビーカーが使われたか」を意味します。

うまく枝を刈りながらバックトラックを行います。

再帰関数の構造

pour() は注ぐビーカー(source)を選び searchTarget() で注がれるビーカー(target)を決定します。searchTarget() が成功したら、さらに pour() を呼び出します。

サンプルプログラム

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 #define MAX 50
005 #define NOT_USED 0
006 #define USED 1
007 #define ISFULL 2
008
009 bool searchTarget(int, int, int, int );
010 bool pour(int, int);
011
012 int size, C[MAX], state[MAX];
013
014 bool searchTarget( int volume, int source, int startt, int nfilled, int remain ){
015 if ( volume == 0 ){
016 state[source] = USED;
017 if( pour(nfilled, remain) ) return true;
018 state[source] = ISFULL;
019 return false;
020 } else if ( volume < 0 || startt < 0 || remain < volume ) return false;
021
022 for ( int i = source - 1; i >= 0; i-- ){
023 if ( state[i] == ISFULL ) break;
024 if ( state[i] == NOT_USED && C[i] > volume ) return false;
025 }
026
027 int pre = -1;
028 for ( int target = startt; target >= 0; target-- ){
029 if ( state[target] >= 1 || C[target] > volume ) continue;
030 if ( pre == C[target] ) continue; // pre 彫髏オッ椎タ彫ネ彫キ彫ソ彫竰、ホ彫マ彫ケ彫ヌ彫ヒ懲・・勅ヌ綴、長、槌、彫、k
031 state[target] = ISFULL;
032 if ( searchTarget( volume - C[target], source, target-1, nfilled+1, remain-C[target] ) ) return true;
033 state[target] = NOT_USED;
034 pre = C[target];
035 }
036 return false;
037 }
038
039 bool pour( int nfilled, int remain ){
040 if ( nfilled == size ) return true;
041
042 for ( int source = size-1; source >= 1; source-- ){
043 if ( state[source] == ISFULL ) {
044 if ( searchTarget( C[source], source, source-1, nfilled, remain )) return true;
045 }
046 }
047
048 return false;
049 }
050
051 bool judge(){
052 sort( C, C + size );
053 int remain = 0;
054 for ( int i = 0; i < size; i++ ) {
055 state[i] = NOT_USED;
056 remain += C[i];
057 }
058 state[size-1] = ISFULL;
059 remain -= C[size-1];
060 return pour( 1 , remain );
061 }
062
063 int main(){
064 while ( cin >> size && size ) {
065 for ( int i = 0; i < size; i++ ) cin >> C[i];
066 if ( judge() ) cout << "YES" << endl;
067 else cout << "NO" << endl;
068 }
069 return 0;
070 }



スポンサーサイト



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

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




こだわり

2008.09.15 13:58  パソコン甲子園 2008

問題 パソコン甲子園2008 09

厚さが異なる n 冊の本を、 k 段の本棚に入れるとき、本棚の最小の幅を求めて下さい。

pck200809.gif
出典:パソコン甲子園2008

入力例
3 9
500
300
800
200
100
600
900
700
400
4 3
1000
1000
1000
0 0

出力例
1800
1000

解説

Partition Problem といいます。

[この問題では、本の厚さの制限が緩いので、力任せ(本棚の幅を少しづづ厚くしていき貪欲に解く)で解けたのかもしれませんが、点数から察して、悲しいことに設定ミスか、または意図的に難易度を下げたか、または実行時間の制限を厳しくしているのでしょうか。力任せで解けないのであれば難易度はさらに高くなります。]

出題者が求めた解法は、動的計画法または二分法だと思います。
ここでは、動的計画法でこの Partition Problem を解きます。


Partition Problem とは、n 個の数からなる数列

S = {s1, ..... sn}

を k 個の部分に分割するときに、各部分の数字の和をできるだけ均等にする、という問題です。厳密に言えば、各部分の数字の和の最大値を最小にするような分割を行います。

例えば、k が 3 の場合、数列

5 3 8 2 1 6 9 7 4



5 3 8 | 2 1 6 | 9 7 4

と 3 つに分割することができます(これは最適な解ではありません)。
この場合は各部分の合計は、16, 9, 20 となり、その最大は 20 となります。
ところが、同じ数列を

5 3 8 | 2 1 6 9 | 7 4

と分割すれば、各部分の合計は 16, 18, 11 となり、その最大が 18 となります。そしてこれが最適解となります(最大値が 18 を下回る分割方法はない)。

仮にこの問題を nCk の組み合わせで総当たりに計算しても、本棚の厚みを少しづつ増やしていく方法で反復的に計算しても、その計算量は膨大になります。

では、動的計画法で解いてみましょう。
まず、以下のデータを用意します。

S : 入力の数列である1次元配列 (最初の要素をS[1]とします)
P : P[i] = P[i-1] + S[i] であるような、1次元配列
P[i] には、最初の要素S[1] から S[i] までの合計が記録されています。
M : M[i][j] が 1 から i 番目までの要素を使い S を j 以下の部分に分割したときの最適解(部分の最大値の最小値)を示す2次元配列

(1) j = 1 の場合、1 ~ i までの要素を 1 個に分割するので、
M[i][1] = P[i] (i = 1,,,n)
となります。

(2) i = 1 の場合、1 つの要素を j 個に分割するので、
M[1][j] = S[1] (j = 1,,,k)
となります。

(3) 2 <= i, 2 <= j の場合 M[i][j] は
x が 1 から i-1 について、S[1] ~ S[i] を S[1] ~ S[x] と S[x+1] ~ S[i] の2つの部分に分けたとき、M[x][j-1] と P[i] - P[x] の大きい方が最小になるような x での最小値になります。ここで、M[x][j-1] は、1 から x 番目までの要素を使い S を j-1 個の部分に分割したときの最適解、
P[i] - P[x] は、x+1 から i 番目までの要素を1つの部分とした場合の合計値

を示します。上記のデータを例にとると、M[i][j]は以下のようになります。
123
1555
2855
31688
418108
519118
625169
7341815
8412216
9452518

例えば i = 6, j = 3 の場合は以下の組み合わせが考えられますが、この中で最適なものを選びます。


絵を準備。。。

サンプルプログラム

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

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




デブンキー一家の大活躍

2008.09.15 13:46  パソコン甲子園 2008

問題 パソコン甲子園2008 08

n 個の都市がり、それらが m 本の橋で繋がっています。各橋の維持費(コスト)が決められています。どの都市にでも行くことができるように橋を残しつつ、橋の維持費の合計が最小になるように、いくつかの橋を壊したときの、維持費の合計を求めて下さい。


解説

重み付きグラフの最小全域木を求める問題です。サンプルは Prim のアルゴリズムで解きました。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define REP(i, e) for ( int i = 0; i < e; i++ )
004 #define MAX 100
005 static const int INFTY = (1<<21);
006 int G[MAX][MAX], n;
007
008 int prim(){
009 int P[MAX], D[MAX];
010 bool V[MAX];
011 REP(i, n) { D[i] = INFTY; V[i] = false;}
012 D[0] = 0;
013 P[0] = -1;
014 int cost = 0;
015 while(1){
016 int u;
017 int minv = INFTY;
018 REP(i, n) if ( !V[i] && D[i] < minv ){
019 minv = D[i]; u = i;
020 }
021 if ( minv == INFTY ) break;
022 V[u] = true;
023 if ( P[u] != -1 ) cost += G[u][P[u]];
024
025 REP(v, n){
026 if ( G[u][v] != INFTY && !V[v] ){
027 if ( D[v] > G[u][v] ){
028 P[v] = u;
029 D[v] = G[u][v];
030 }
031 }
032 }
033 }
034 return cost;
035 }
036
037 int main(){
038 int m, s, t, c;
039 while( cin >> n >> m && n){
040 REP(i, n) REP(j, n) G[i][j] = INFTY;
041 for ( int i = 0; i < m; i++ ){
042 cin >> s >> t >> c;
043 G[s][t] = G[t][s] = c;
044 }
045 cout << prim() << endl;
046 }
047 }

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

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




ふしぎな虫

2008.09.15 13:10  パソコン甲子園 2008

問題 パソコン甲子園2008 07

いくつかの玉のような形をした体節でつながっている不思議な虫がいます。体節は赤(r)、緑(g)、青(b)のいづれかの色をもっています。この虫が、以下の条件のもとで1秒ごとに体節の色を変えます:


  • 色が変わるのは、隣合っている色違いの2つの体節のペア 1 組のみ。

  • そのようなペアは、2 つの体節の色のどちらでもない色に同時に変わる。


この虫の色の変化を、2 秒後まですべて表したものが以下の図です。

pck200807_2.gif
出典:パソコン甲子園2008


与えられたある虫の体節の並びから、すべての体節の色が同じになるまでに要する最小の時間を求めて下さい(不可能な場合は NA と出力して下さい)。

入力例
rbgrg
rbbgbbr
bgr
bgrbrgbr
bggrgbgrr
gbrggrbggr
rrrrr
bgbr
0

出力例
5
7
1
6
NA
8
0
4


解説

状態空間における幅優先探索で解きます。
ここでは、状態を r, g, b からなる文字列(そのまま)で表します。
状態を保存するためにハッシュ法を用いるのが良いでしょうが、
STL の map を使うと実装が楽になります(速度は落ちるでしょう)。

サンプルプログラム

001 #include<iostream>
002 #include<queue>
003 #include<map>
004 using namespace std;
005 #define INFTY (1<<21)
006
007 bool isSameColor( string state ){
008 for ( int i = 1; i < state.size(); i++ ){
009 if ( state[i-1] != state[i] ) return false;
010 }
011 return true;
012 }
013
014 char getColor( char c1, char c2 ){
015 if ( c1 == 'g' ) return (c2=='r' ? 'b' : 'r');
016 else if ( c1 == 'b' ) return (c2=='r' ? 'g' : 'r');
017 else if ( c1 == 'r' ) return (c2=='b' ? 'g' : 'b');
018 }
019
020 int bfs(string s){
021 queue<string> Q;
022 map<string, bool> V;
023 map<string, int> D;
024
025 Q.push(s);
026 V[s] = true;
027 D[s] = 0;
028 string u, v;
029
030 while(!Q.empty()){
031 u = Q.front(); Q.pop();
032 if ( isSameColor(u) ) return D[u];
033 for ( int i = 1; i < u.size(); i++ ){
034 if ( u[i-1] != u[i] ){
035 v = u;
036 v[i-1] = v[i] = getColor(u[i-1], u[i]);
037 if ( !V[v] ){
038 V[v] = true;
039 D[v] = D[u] + 1;
040 Q.push(v);
041 }
042 }
043 }
044 }
045
046 return INFTY;
047 }
048
049 int main(){
050 string initial;
051 while( cin >> initial ){
052 if ( initial == "0" ) break;
053 int cost = bfs( initial );
054 if ( cost == INFTY ) cout << "NA" << endl;
055 else cout << cost << endl;
056 }
057 return 0;
058 }


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

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




テトリス

2008.09.15 11:48  パソコン甲子園 2008

問題 パソコン甲子園2008 06

テトリスをシミュレーションして下さい。盤面の大きさは横 5 コマで、落ちてくるブロックはすべて直線状で、横向き、縦向きの2種類があり、長さは 1 から 5 までの 5 種類です(全部で10種類)。

いくつかのブロックを落としていき、全てブロックで埋まった横一列は削除され、その列の上にあったブロックたちはそのままの形で下へ落ちます。最後に残るブロックのコマ数を求めて下さい。

pck200806_1.gif

pck200806_2.gif
出典(パソコン甲子園2008)


入力例
4
1 4 1
1 3 1
2 2 4
2 3 5
0

出力例
2


解説

2次元配列で盤面を表現することもできますが、ここでは整数型の1次元配列(stack)で盤面を表します。
stack[i] には盤面の下から i 行目のブロック片の状態を記録します。各行のブロック片の状態を整数で表すために、ブロック片の並びをビットとみなします。ブロック片がある状態を 1 ない状態を 0 とします。例えば、ある行のブロック片

■□■■□



10110(2進数)

と表されるので、22(10進数)となります。

例えば、盤面が

5□□□■□
4□□□■□
3■□■■■
2■■■□□
1■□■■□

の状態ならば、スタックの中身は

stack = {22, 28, 23, 2, 2}

となります。

このstackに、同様に整数で表されたブロックを落としていきます。
例えば、上記の盤面にブロック

■■■□□

を落とすと

5□□□■□
4■■■■□
3■□■■■
2■■■□□
1■□■■□

となります。
ここで、ブロックが置かれる位置は、ブロックを上から落としたときに、すでにあるブロック片にひっかかる直前の位置です。
この位置は、stack の頂点から下に向かってブロックの値とスタックの値の論理積をとり、論理積が0とならない直前の位置となります。

例えば、今落したブロック
■■■□□
と、stack[5] のブロック片
□□□■□
との論理積(28 & 2)は 0 となるので、すり抜けます。

例えば、ブロック
■■■□□
と、stack[3] のブロック片
■□■■■
との論理積(23 & 2)は 0 とはならないので、このブロック片の上にブロックが置かれます。

ブロックを置いた後に、ブロック片が5つ並んでいる場所、つまり stack の要素が 31 の場所を消していきます。

便宜上、stack[0] を 31 とします。

サンプルプログラム

001 #include<iostream>
002 using namespace std;
003 #define MAX 5000
004
005 class Tetoris{
006 public:
007 int stack[MAX+1], top;
008 Tetoris(){ stack[0] = 31; top = 0; }
009
010 void insert( int o, int p, int q ){
011 int value = (o == 1 ? (((2 << p-1)-1) << (q-1)) : (1 << (q-1)));
012 int target = getTarget( value );
013 for ( int i = target; i < target + ((o == 2) ? p : 1); i++ ){
014 if ( i > top ){
015 stack[i] = value;
016 top = i;
017 } else {
018 stack[i] += value;
019 }
020 }
021
022 while( erase());
023 }
024
025 bool erase(){
026 for ( int i = 1; i <= top; i++ ){
027 if ( stack[i] == 31 ){
028 for ( int j = i+1; j <= top; j++ ) stack[j-1] = stack[j];
029 top--; return true;
030 }
031 }
032 return false;
033 }
034
035 int getResult(){
036 int sum = 0;
037 for ( int i = top; i >= 1; i-- ){
038 int val = stack[i];
039 while( val ){
040 if ( val%2 ) sum++;
041 val /= 2;
042 }
043 }
044 return sum;
045 }
046
047 int getTarget( int value ){
048 int target = top;
049 while( (stack[target] & value) == 0 ) target--;
050 return target + 1;
051 }
052 };
053
054 int main(){
055 int n, o, p, q;
056 while( cin >> n && n ){
057 Tetoris tetoris;
058 for ( int i = 0; i < n; i++ ) {
059 cin >> o >> p >> q;
060 tetoris.insert(o, p, q);
061 }
062 cout << tetoris.getResult() << endl;
063 }
064 return 0;
065 }




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

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




都市間の距離

2008.09.13 23:01  ACM/ICPC 2008

問題 パソコン甲子園2008 05

地球上の2つの都市の北緯と東経を入力し、地表距離を計算して出力して下さい。


解説

これは数学の問題です。
入力された2つの角度から球面座標へ変換し、各都市の(x, y, z)座標を求めます。

以下の図で、z 軸から方向ベクトルへの角度を theta、x 軸から半時計回りのxy平面上の角度をphiとすると、

pck200805_1.gif


x = r*sin(theta)*cos(phi);
y = r*sin(theta)*sin(phi);
z = r*cos(theta);

となります。2つの都市の座標より、距離 d を求めます。

さらに以下の図で、

pck200805_2.gif


s = r*th となります。

th = acos(1 - d*d/(2*r*r))

より、地表距離 s は

s = r*acos(1 - d*d/(2*r*r))

となります。

サンプルプログラム
※ d*d を dist としています(sqrtの計算を避けるため)
001 #include<stdio.h>
002 #include<iostream>
003 #include<cmath>
004 using namespace std;
005 static const double r = 6378.1;
006 static const double PI = acos(-1);
007
008 class Point{
009 public:
010 double x, y, z;
011 Point(){}
012 Point ( double theta, double phi ){
013 theta = 90 - theta;
014 theta *= (PI/180); // to degree
015 phi *= (PI/180);
016 x = r*sin(theta)*cos(phi);
017 y = r*sin(theta)*sin(phi);
018 z = r*cos(theta);
019 }
020 };
021
022 double getDistance( Point p1, Point p2 ){
023 return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z);
024 }
025
026 int main(){
027 double lat1, lat2, lon1, lon2;
028 Point p1, p2;
029 double theta, phi;
030 while( cin >> lat1 >> lon1 >> lat2 >> lon2 ){
031 if ( lat1 == 0 && lon1 == 0 && lat2 == 0 && lon2 == 0 ) break;
032
033 p1 = Point( lat1, lon1 );
034 p2 = Point( lat2, lon2 );
035
036 double dist = getDistance( p1, p2 );
037
038 printf("%.0lf\n", r*acos( 1 - dist/(2*r*r)));
039 }
040
041 return 0;
042 }



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

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




ハワイ好きの王様

2008.09.13 22:10  パソコン甲子園 2008

問題 パソコン甲子園2008 03

与えられた10進数の数 n を、4進数へ変換して出力して下さい。

入力例
7
4
0
12
10
10000
-1 (入力の終り)

出力例
13
10
0
30
22
2130100


解説

基数変換の問題です。
10進数 n を B 進数に変換するには、
n を B で割った余りを並べていきます。

サンプルプログラム


001 #include<iostream>
002 using namespace std;
003 #define BASE 4
004
005 void parse( int x ){
006 if ( x / BASE ) parse( x / BASE );
007 cout << x % BASE;
008 }
009
010 int main(){
011 int n;
012 while( cin >> n && n >= 0){
013 parse(n);
014 cout << endl;
015 }
016 return 0;
017 }



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

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




バドミントン

2008.09.13 21:59  パソコン甲子園 2008

問題 パソコン甲子園2008予選 02

A君とBさんが以下のルールでバドミントンをしました。
(1データセットにつき)3ゲームを行います。
各ゲームは11点先取した人が勝者となります。
第1ゲームの最初のサーブはA君から始まりますが、次のサーブは直前のポイントを取った人が行います。
第2ゲーム、第3ゲームは前のゲームを取った人が最初のサーブを行います。
10-10になって以降は2点差をつけた人が勝者となります。

誰がサーブを打ったかの情報のみから2人の得点を求めて下さい。

入力例
ABAABBBAABABAAABBAA
AABBBABBABBAAABABABAAB
BABAABAABABABBAAAB
AABABAAABBAABBBABAA
AAAAAAAAAAA
ABBBBBBBBBB
0(入力の終り)

出力例
11 8
10 12
11 7
11 8
11 0
0 11

解説

ロジックを組むのがなかなか面倒そうな問題、、と思ったらすごく簡単です。
ポイントは、1ゲームの情報(各行)からそのゲームの得点が決まるということです。
(問題文にある、前のゲームを取った人が最初のサーブを行うというルールは
問題を解くうえでは必要ない情報)

各ゲーム(行)について、まず、1文字目を除いたAとBの数を求めます。
これで、各ゲームの最後のポイントを除いたA君とBさんの得点が求まります。
次に、この2つの得点から以下のアルゴリズムで誰が最後のポイントを獲得
したかを推測し、最終得点を決めます。

A > B ならば A に 1 を足し、
A < B ならば B に 1 を足します。

(入力は正しく行われたゲームの情報なのでこのアルゴリズムが適用できます)

サンプルプログラム



001 #include<iostream>
002 #include<cassert>
003 using namespace std;
004
005 void play(string game){
006 int A, B;
007 A = B = 0;
008 for ( int i = 1; i < game.size(); i++ ) {
009 if ( game[i] == 'A' ) A++;
010 else B++;
011 }
012 if ( A > B ) A++;
013 else if ( A < B ) B++;
014 else assert( false );
015
016 cout << A << " " << B << endl;
017 }
018
019 int main(){
020 string game;
021 while( cin >> game && game != "0") play(game);
022 return 0;
023 }


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

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




パソコン甲子園2008

2008.09.12 22:55  パソコン甲子園 2008

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

番号問題難易度点数
01 お化け屋敷 6
02 バドミントン 6
03 ハワイ好きの王様 6
04 どんな色 6
05 都市間の距離 ★☆ 8
06 テトリス ★★☆ 8
07 ふしぎな虫 ★★★ 20
08 デンブンキー一家の大活躍 ★★★ 20
09 こだわり ★★★ 20
10 ビーカー ★★★☆ 20


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

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