fc2ブログ



Zigzag

2009.08.08 14:39  ACM/ICPC 2008

ACM-ICPC 2008 Aizu, Problem J: Zigzag

解説の通り Dijkstra で解いてみました。 与えられた点を通る2つの直線の組み合わせについて、交点を求め, その交点と入力された点の集合について TSP を解くような感じです。 状態は S[現在の点(入力された点のみ)][前にいた点][通った点の状態(入力された点のみ)] になります。

ただし、無駄な交点を作ってしまうとTLEになります。

コードは, Dijkstra の部分のみです。


スポンサーサイト



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

| コメント(0) | トラックバック(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) | ↑ページトップ |




ACM/ICPC 国内予選 2008

2008.07.10 23:05  ACM/ICPC 2008

番号問題難易度
A Equal Total Scores
B Monday-Saturday Prime Factors ★☆
C How can I satisfy thee? Let me count the ways... ★★☆
D Twirling Robot ★★★
E Roll-A-Big-Ball ★★★★
F ICPC: Intelligent Congruent Partition of Chocolate ★★★★

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

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




ICPC: Intelligent Congruent Partition of Chocolate

2008.07.10 22:57  ACM/ICPC 2008

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156




001 #include<iostream>
002 #include<algorithm>
003 #include<set>
004 #include<map>
005 using namespace std;
006 typedef set<int> Shape;
007 #define MAX 12
008 int W, H, C[MAX][MAX], ncell, sx, sy, tx, ty, sd, td, flip;
009 bool V[MAX][MAX];
010 map<Shape, bool> U;
011
012 void rotate( int &x, int &y ){
013 if ( td == 1 ){ swap( x, y ); x *= (-1);}
014 else if ( td == 2 ) { x *= (-1); y *= (-1);}
015 else if ( td == 3 ) { swap( x, y ); y *= (-1);}
016 x *= flip;
017 }
018
019 bool dfs( Shape shape ){
020 if ( shape.size() == ncell ) return true;
021
022 U[shape] = true;
023
024 static const int dx[4] = {0, -1, 0, 1};
025 static const int dy[4] = {1, 0, -1, 0};
026 int nx, ny, tnx, tny, diffx, diffy;
027 Shape nextS;
028
029 for ( Shape::iterator it = shape.begin(); it != shape.end(); it++ ){
030 for ( int d = 0; d < 4; d++ ){
031 nx = (*it)/W + dx[d];
032 ny = (*it)%W + dy[d];
033 if ( !C[nx][ny] || V[nx][ny] ) continue;
034 diffx = nx - sx;
035 diffy = ny - sy;
036 rotate( diffx, diffy );
037 tnx = tx + diffx;
038 tny = ty + diffy;
039 if ( nx == tnx && ny == tny ) continue;
040 if ( !C[tnx][tny] || V[tnx][tny] ) continue;
041 nextS = shape;
042 nextS.insert( nx*W + ny );
043 if ( U[nextS] ) continue;
044 V[nx][ny] = V[tnx][tny] = true;
045 if ( dfs( nextS ) ) return true;
046 V[nx][ny] = V[tnx][tny] = false;
047 }
048 }
049 return false;
050 }
051
052 bool parse(){
053 U = map<Shape, bool>();
054 for ( int x = 1; x <= H; x++ ){
055 for ( int y = 1; y <= W; y++ ) V[x][y] = 0;
056 }
057 Shape shape;
058 shape.insert( sx*W + sy );
059 U[shape] = true;
060 V[sx][sy] = V[tx][ty] = true;
061 return dfs( shape );
062 }
063
064 bool check(){
065 if ( ncell % 2 != 0 || ncell < 2 ) return false;
066 ncell /= 2;
067 for ( tx = 1; tx <= H; tx++ ){
068 for ( ty = 1; ty <= W; ty++ ){
069 if ( (tx == sx && ty == sy) || C[tx][ty] == 0) continue;
070 for ( td = 0; td < 4; td++ ){
071 flip = 1;
072 if ( parse() ) return true;
073 flip = -1;
074 if ( parse() ) return true;
075 }
076 }
077 }
078 return false;
079 }
080
081 main(){
082 while( cin >> W >> H && ( W && H ) ){
083 ncell = 0;
084 sx = sy = -1;
085 for ( int x = 0; x < H + 2; x++ ){
086 for ( int y = 0; y < W + 2; y++ ){
087 C[x][y] = 0;
088 if ( 1 <= x && 1 <= y && x <= H && y <= W ) cin >> C[x][y];
089 if ( C[x][y] ) ncell++;
090 if ( C[x][y] && sx == -1 ){ sx = x; sy = y; }
091 }
092 }
093 if ( check() ) cout << "YES" << endl;
094 else cout << "NO" << endl;
095 }
096 }


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

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




Twirling Robot

2008.07.10 22:56  ACM/ICPC 2008



001 #include<iostream>
002 #include<queue>
003 using namespace std;
004 #define MAX 30
005 static const int STR = 0;
006 static const int RIGHT = 1;
007 static const int BACK = 2;
008 static const int LEFT = 3;
009 static const int HALT = 4;
010 static const int di[4] = {0, -1, 0, 1};
011 static const int dj[4] = {1, 0, -1, 0};
012
013 class Robot{
014 public:
015 int i, j, k, cost;
016 Robot(){}
017 Robot( int i, int j, int k, int cost ): i(i), j(j), k(k), cost(cost){}
018
019 void move( int com, int c ){
020 if ( com == LEFT ) k = (k+1)%4;
021 if ( com == RIGHT ) k = (k+3)%4;
022 if ( com == BACK ) k = (k+2)%4;
023 i += di[k]; j += dj[k];
024 cost += c;
025 }
026
027 bool operator < ( const Robot &s ) const{
028 return cost > s.cost;
029 }
030 };
031
032 int W, H, G[MAX][MAX], C[4];
033
034 bool valid( Robot r ){
035 return ( 0 <= r.i && 0 <= r.j && r.i < H && r.j < W );
036 }
037
038 int dijkstra(){
039 bool V[MAX][MAX][4];
040 for ( int i = 0; i < H; i++ ){
041 for ( int j = 0; j < W; j++ ) {
042 for ( int k = 0; k < 4; k++ ) V[i][j][k] = false;
043 }
044 }
045 priority_queue<Robot> PQ;
046 PQ.push(Robot(0, 0, 0, 0)); // i, j, direction, cost
047 Robot u, v; // current node, next node
048
049 while(!PQ.empty()){
050 u = PQ.top(); PQ.pop();
051 if ( u.i == H-1 && u.j == W-1 ) return u.cost;
052 V[u.i][u.j][u.k] = true;
053 v = u;
054 v.move(G[u.i][u.j], 0);
055 if ( G[u.i][u.j] != HALT && valid(v) && !V[v.i][v.j][v.k] ) PQ.push( v );
056 for ( int com = 0; com < 4; com++ ){
057 v = u;
058 v.move(com, C[com]);
059 if ( valid(v) && !V[v.i][v.j][v.k] ) PQ.push( v );
060 }
061 }
062 }
063
064 main(){
065 while( cin >> W >> H && ( W && H) ){
066 for ( int i = 0; i < H; i++ ){
067 for ( int j = 0; j < W; j++ ) cin >> G[i][j];
068 }
069 for ( int i = 0; i < 4; i++ ) cin >> C[i];
070 cout << dijkstra() << endl;
071 }
072 }


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

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




How can I satisfy thee? Let me count the ways...

2008.07.10 22:55  ACM/ICPC 2008

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155




001 #include<iostream>
002 #include<string>
003 #include<map>
004 #include<cassert>
005 using namespace std;
006
007 map<char, int> V;
008 string exp;
009 int pos;
010
011 int formula(){
012 char ch = exp[pos];
013 if ( isdigit(ch) ){
014 pos++; return ch - '0';
015 } else if ( isalpha(ch) ){
016 pos++; return V[ch];
017 } else if ( ch == '-' ){
018 pos++; return (2 - formula()); // NOT
019 } else if ( ch == '(' ){
020 int v1, v2;
021 char op;
022 pos++;
023 v1 = formula();
024 op = exp[pos++];
025 v2 = formula();
026 assert( exp[pos++] == ')');
027 if ( op == '*' ) return min( v1, v2 ); // AND
028 else if ( op == '+' ) return max( v1, v2 ); // OR
029 }
030 }
031
032 main(){
033 int cnt;
034 while( cin >> exp && exp != "."){
035 cnt = 0;
036 for ( int p = 0; p <= 2; p++ ){
037 for ( int q = 0; q <= 2; q++ ){
038 for ( int r = 0; r <= 2; r++ ){
039 V['P'] = p;
040 V['Q'] = q;
041 V['R'] = r;
042 pos = 0;
043 if ( formula() == 2 ) cnt++;
044 }
045 }
046 }
047 cout << cnt << endl;
048 }
049 }


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

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




Monday-Saturday Prime Factors

2008.07.10 22:54  ACM/ICPC 2008

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1154




001 #include<iostream>
002 using namespace std;
003 #define MAX 300001
004
005 bool prime[MAX];
006
007 void generate(){
008 fill( prime, prime + MAX, false ) ;
009 for ( int i = 1, k = 0; i <= MAX; k++){
010 prime[i] = true;
011 i += ((k % 2 == 0) ? 5 : 2);
012 }
013 prime[1] = false;
014 for ( int i = 1, k = 0; i * i <= MAX; k++ ){
015 if ( prime[i] ) {
016 for ( int j = 2*i; j <= MAX; j += i ) prime[j] = false;
017 }
018 i += ((k % 2 == 0) ? 5 : 2);
019 }
020 }
021
022 main(){
023 generate();
024 int x;
025 while( cin >> x ){
026 if ( x == 1 ) break;
027 cout << x << ":";
028 for ( int i = 1; i <= MAX; i++ ){
029 if ( prime[i] && x % i == 0 ) cout << " " << i;
030 }
031 cout << endl;
032 }
033 }


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

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




Equal Total Scores

2008.07.10 22:52  ACM/ICPC 2008

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1153

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

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