Zigzag

ACM-ICPC 2008 Aizu, Problem J: Zigzag

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

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

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

void dijkstra(){
    priority_queue<QState> PQ[5];
    bool C[10][MAX][SMAX];
    rep(i, nnode) rep(j, n) rep(k, (1<<nnode)) C[i][j][k]= false;

    rep(s, nnode) rep(i, P[s].size) {
        int v = P[s].adj[i].t;
        if ( v < nnode ){
            PQ[0].push(QState(S[s]|S[v], v, s, 0, P[s].adj[i].d));
        } else {
            rep(j, P[v].size){
                int vv = P[v].adj[j].t;
                if ( vv == s ) continue;
                int nt = CCW2[s][v][vv]; 
                PQ[nt].push(QState(S[s]|S[vv], vv, v, nt, P[s].adj[i].d + P[v].adj[j].d));
            }
        }
    }

    QState u;
    while(1){
        u = getState(PQ);
        if ( u.state == S[nnode]-1 ) {
            printf("%d %.5lf\n", u.nturn, u.dist);
            return;
        }
        if ( C[u.cur][u.pre][u.state] ) continue;
        C[u.cur][u.pre][u.state] = true;

        int p0 = u.pre;
        int p1 = u.cur;
        int p2, p3;

        rep(i, P[p1].size){
            int p2 = P[p1].adj[i].t;
            double ndist = P[p1].adj[i].d;
            if ( p2 < nnode ){
                ushort state = (u.state|S[p2]);
                ushort nt = u.nturn + CCW1[p0][p1][p2];
                if ( nt >= 5 ) continue;
                double nd = u.dist + ndist;
                if ( !C[p2][p1][state] ) PQ[nt].push(QState(state, p2, p1, nt, nd));
            } else {
                rep(j, P[p2].size ){
                    p3 = P[p2].adj[j].t;
                    if ( p3 == p1 ) continue;
                    ushort state = (u.state|S[p3]);
                    ushort nt = u.nturn + CCW1[p0][p1][p2] + 1;
                    if ( nt >= 5 ) continue;
                    double nd = u.dist + ndist + P[p2].adj[j].d;
                    if ( !C[p3][p2][state] ) PQ[nt].push(QState(state, p3, p2, nt, nd));
                }
            }
        }
    }
}

都市間の距離

問題 パソコン甲子園2008 05

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

解説

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

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



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

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

さらに以下の図で、



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 }

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	★★★★

ICPC: Intelligent Congruent Partition of Chocolate

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 }

Twirling Robot

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 }

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

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 }

Monday-Saturday Prime Factors

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 }

Equal Total Scores

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

#include<iostream>
using namespace std;
#define MAX 100

main(){
    int n, m, T[MAX], H[MAX], sumT, sumH, exT, exH;
    while( cin >> n >> m  ){
	if ( n == 0 && m == 0 ) break;
	sumT = sumH = 0;
	for ( int i = 0; i < n; i++ ) { cin >> T[i]; sumT += T[i]; }
	for ( int j = 0; j < m; j++ ) { cin >> H[j]; sumH += H[j]; }
	exT = exH = MAX;
	for ( int i = 0; i < n; i++ ){
	    for ( int j = 0; j < m; j++ ){
		if ( sumT - T[i] + H[j] != sumH - H[j] + T[i] ) continue;
		if ( exT + exH > T[i] + H[j] ){
		    exT = T[i];
		    exH = H[j];
		}
	    }
	}
	if ( exT == MAX && exH == MAX ) cout << -1 << endl;
	else cout << exT << " " << exH << endl;
    }
}