問題E Robot Navigation
解法
BFS(幅優先探索)です。最短距離更新のときにキューに入れるのと経路数の更新をして、最短距離と等しいときは経路数の加算をしています。コード(C++)
#include <iostream> #include <queue> using namespace std; const int dx[4] = {0,1,0,-1}; const int dy[4] = {-1,0,1,0}; const int INF = 1e+8; int h, w, sx, sy, gx, gy, s_dir, ans1, ans2; string c[101]; // d[dir][y][x] := (sx, sy, s_dir) から (x, y, dir)までの最小コスト int d[4][101][101]; // dp[dir][y][x] := (x, y, dir)までの経路数 int dp[4][101][101]; struct State{ int x, y, dir; State(){} State(int x_, int y_, int dir_){ x = x_; y = y_; dir = dir_; } }; void solve(){ for(int i = 0 ; i < 4 ; i++ ){ for(int j = 0 ; j < 101 ; j++ ){ for(int k = 0 ; k < 101 ; k++ ){ d[i][j][k] = INF; dp[i][j][k] = 0; } } } d[s_dir][sy][sx] = 0; dp[s_dir][sy][sx] = 1; queue<State> q; q.push( State(sx, sy, s_dir) ); ans1 = INF, ans2 = 0; while( !q.empty() ){ int x = q.front().x, y = q.front().y, dir = q.front().dir; q.pop(); if( x == gx && y == gy ){ ans1 = d[dir][y][x]; break; } // 右に90度回転 int next_dir = (dir + 1) % 4; if( d[next_dir][y][x] == INF ){ d[next_dir][y][x] = d[dir][y][x] + 1; dp[next_dir][y][x] += dp[dir][y][x] % 1000000; q.push( State(x, y, next_dir) ); }else if( d[dir][y][x] + 1 == d[next_dir][y][x] ){ dp[next_dir][y][x] += dp[dir][y][x] % 1000000; } // 右に90度回転 next_dir = (dir + 3) % 4; if( d[next_dir][y][x] == INF ){ d[next_dir][y][x] = d[dir][y][x] + 1; dp[next_dir][y][x] += dp[dir][y][x] % 1000000; q.push( State(x, y, next_dir) ); }else if( d[dir][y][x] + 1 == d[next_dir][y][x] ){ dp[next_dir][y][x] += dp[dir][y][x] % 1000000; } // 直進する int mx = x, my = y; for( ; true ; ){ mx += dx[dir], my += dy[dir]; if( mx < 0 || my < 0 || w <= mx || h <= my || c[my][mx] == '*' ) break; if( d[dir][my][mx] == INF ){ d[dir][my][mx] = d[dir][y][x] + 1; dp[dir][my][mx] += dp[dir][y][x] % 1000000; q.push( State(mx, my, dir) ); }else if( d[dir][y][x] + 1 == d[dir][my][mx] ){ dp[dir][my][mx] += dp[dir][y][x] % 1000000; } } } for(int i = 0 ; i < 4 ; i++ ){ if( d[i][gy][gx] == ans1 ){ ans2 += dp[i][gy][gx] % 1000000; } } if( ans1 == INF ) ans1 = ans2 = 0; } int main(){ int f[256] = {0}; f['E'] = 1; f['S'] = 2; f['W'] = 3; while( cin >> h >> w , h || w ){ for(int y = 0 ; y < h ; y++ ) cin >> c[y]; for(int y = 0 ; y < h ; y++ ){ for(int x = 0 ; x < w ; x++ ){ if( c[y][x] == '.' || c[y][x] == '*' ) continue; if( c[y][x] == 'X' ){ gx = x, gy = y, c[y][x] = '.'; }else{ sx = x, sy = y, s_dir = f[c[y][x]]; c[y][x] = '.'; } } } solve(); cout << ans1 << " " << ans2 << endl; } }
問題D Hexagram
解法
DFS(深さ優先探索)です。12個の数字の合計が3の倍数にならないときや直線4つの数字が3の倍数にならないときに枝刈りできます。数字が全部異なるため回転・対称のものは全部で12通りあるので、重複して数え上げて最後に12で割るとよいです。コード(C++)
#include <iostream> using namespace std; int a[12], b[12], sum, line; bool memo[12]; int dfs(int pos = 0){ // 合計が 3 の倍数でないときは解は 0 if( sum % 3 != 0 ) return 0; if( pos == 12 ){ if( line != a[1] + a[8] + a[9] + a[11] ) return 0; if( line != a[5] + a[7] + a[10] + a[11] ) return 0; return 1; } if( pos == 4 ){ line = a[0] + a[1] + a[2] + a[3]; if( sum / 3 != line ) return 0; }else if( pos == 7 ){ if( line != a[3] + a[4] + a[5] + a[6] ) return 0; }else if( pos == 9 ){ if( line != a[0] + a[6] + a[7] + a[8] ) return 0; }else if( pos == 11 ){ if( line != a[2] + a[4] + a[9] + a[10] ) return 0; } int res = 0; for(int i = 0 ; i < 12 ; i++ ){ if( memo[i] ) continue; a[pos] = b[i]; memo[i] = true; res += dfs(pos + 1); memo[i] = false; } return res; } int main(){ while( cin >> b[0], b[0] ){ sum = b[0]; for(int i = 1 ; i < 12 ; i++ ){ cin >> b[i]; sum += b[i]; } fill(memo, memo + 12, false); cout << dfs() / 12 << endl; } }
問題C Sunday Drive
もとのこの問題は小数点以下2桁出力していますが、練習会では出力形式が小数点以下4桁の出力に変更されています。
解法
DP(動的計画法)です。dp[i][j] := i番目の区間のj番目のレーンにたどり着く最短距離 となるように計算します。曲がる区間のカーブの距離の計算式や直線区間の車線変更の部分が間違えやすいので気をつけましょう。コード(C++)
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; const double PI = acos(-1); const double INF = 1e+8; //dp[i][j] := 区間 i の左から j 番目レーンにたどり着く最短距離 double dp[1001][11]; int main(){ int N, M, K[1001]; char T[1001]; while( cin >> N >> M , N || M ){ for(int i = 0 ; i < N ; i++ ) cin >> T[i] >> K[i]; // 初期化 for(int i = 0 ; i < 1001 ; i++ ){ for(int j = 0 ; j < 11 ; j++ ){ dp[i][j] = INF; if( i == 0 ) dp[i][j] = 0; } } // i := 区間, j := レーン for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < M ; j++ ){ if( T[i] == 'S' ){ // 直線の区間 // 移動できるレーン数 int r = K[i] / 100; // レーンを j -> k と移動する for(int k = j - r ; k <= j + r ; k++ ){ if( j == k ){ // 直線で移動 dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + K[i]); }else if( 0 <= k && k < M ){ double a = K[i], b = abs(j - k) * 10; double d = sqrt(a * a + b * b); dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + d); } } }else if( T[i] == 'L' ){ // 左に曲がる区間 double r = K[i] + 10 * j + 5; double d = 0.5 * PI * r; dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d); }else if( T[i] == 'R' ){ // 左に曲がる区間 double r = K[i] + 10 * M - 10 * j - 5; double d = 0.5 * PI * r; dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + d);; } } } double ans = INF; for(int i = 0 ; i < M ; i++ ) ans = min(ans, dp[N][i]); printf("%.4f\n", ans); } }
問題B Shuffle'm up
練習会では入力形式が少し変更されているので上記のオンラインジャッジで正解するには入力部分のコードを少し書きなおす必要があります。(POJではテストケースの番号+解を出力する)
解法
問題文のとおりに実装しましょう。またいままで訪れた状態はメモしておきましょう。コード(C++)
#include <iostream> #include <string> #include <set> using namespace std; int main(){ int N; cin >> N; for(int n = 0 ; n < N ; n++ ){ int C; string s1, s2, s12, t; set<string> memo; cin >> C >> s1 >> s2 >> t; int ans = 0; while( true ){ ans++; s12.clear(); for(int i = 0 ; i < C ; i++ ){ s12.push_back( s2[i] ); s12.push_back( s1[i] ); } s1 = s12.substr(0, C); s2 = s12.substr(C, C); if( s12 == t ){ break; }else if( !memo.count(s12) ){ memo.insert(s12); }else{ ans = -1; break; } } cout << ans << endl; } }
問題A Event Planning
練習会では入力形式が複数テストケースに変更されているので上記のオンラインジャッジで正解するには入力部分のコードを少し書きなおす必要があります。
解法
全探索しましょう。C++ならmax_elementを使うと少しコードが短くなります。コード(C++)
#include <iostream> #include <algorithm> using namespace std; int main(){ int N, B, H, W, p, a[14]; while( cin >> N >> B >> H >> W , N || B || H || W ){ int ans = 1e+8; for(int i = 0 ; i < H ; i++ ){ cin >> p; for(int j = 0 ; j < W ; j++ ){ cin >> a[j]; } if( N <= *max_element(a, a + W) ){ ans = min(ans, p * N); } } if( ans <= B ){ cout << ans << endl; }else{ cout << "stay home" << endl; } } }
問題G Hot Dogs in Manhattan
解法
解説に書いてあるので省略。コード
#include <iostream> #include <vector> #include <map> #include <queue> #include <algorithm> using namespace std; typedef pair<int,int> P; const int INF = 1e+8; const int dx[4] = {0,0,-1,1}; const int dy[4] = {-1,1,0,0}; int w, h, n; // d[y][x] := (x,y)のプライバシー値 int d[1001][1001]; bool f(int mid){ vector<int> xleft(h), xright(h); for(int y = 0 ; y < h ; y++ ){ xleft[y] = xright[y] = -1; for(int x = 0 ; x < w ; x++ ){ if( d[y][x] >= mid ){ if( xleft[y] == -1 ){ xleft[y] = x; } xright[y] = x; } } } for(int y = 0 ; y < h ; y++ ){ if( xleft[y] == -1 ) continue; for(int x = y ; x < h ; x++){ if( xleft[x] == -1 ) continue; if( abs(xleft[y] - xright[x]) + (x - y) >= mid ){ return true; } if( abs(xright[y] - xleft[x]) + (x - y) >= mid ){ return true; } } } return false; } int main(){ int T; cin >> T; for(int t = 0 ; t < T ; t++ ){ cin >> n >> w >> h; // 初期化 for(int y = 0 ; y < h ; y++ ) fill(d[y], d[y] + w, INF); queue<P> q; for(int i = 0 ; i < n ; i++ ){ int x, y; cin >> x >> y; d[y][x] = 0; q.push( P(x, y) ); } // BFSで交差点ごとに既存のスタンドからの距離の最小値を求める while( !q.empty() ){ int x = q.front().first, y = q.front().second; q.pop(); for(int i = 0 ; i < 4 ; i++ ){ int mx = x + dx[i], my = y + dy[i]; if( mx < 0 || my < 0 || w <= mx || h <= my ) continue; if( d[y][x] + 1 < d[my][mx] ){ d[my][mx] = d[y][x] + 1; q.push( P(mx, my) ); } } } // 二分探索 int low = 0, high = w + h; while( low <= high ){ int mid = (low + high) / 2; if( f(mid) ){ low = mid + 1; }else{ high = mid - 1; } } cout << high << endl; } }
問題F Charlie the Cockchafer
解法
グラフを作成してdp[現在の頂点][直前の頂点] := 最小時間 となるようにダイクストラ法をします。二点間の距離と角度の計算(内積を使う)ができれば解けるかと思います。スタートとゴールが同じケースや直前に来た道に戻る時に誤差死しないように気をつけましょう。(直前に来た道には戻らないという処理をするのが楽かも)コード
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cstdio> #include <cmath> using namespace std; const int INF = 1e+8; const double EPS = 1e-8; const double PI = acos(-1.0); struct State{ int v, prev; double cost; State(){} State(int v_, int prev_, double cost_){ v = v_; prev = prev_; cost = cost_; } }; bool operator<(const State &a, const State &b){ return a.cost > b.cost; } struct P{ double x, y, z; P(){} P(double x_, double y_, double z_){ x = x_; y = y_; z = z_; } }; P operator-(P p1, P p2) { return P(p1.x - p2.x, p1.y - p2.y, p1.z - p2.z); } bool operator==(const P &a, const P &b){ return a.x == b.x && a.y == b.y && a.z == b.z; } bool operator<(const P &a, const P &b){ if( a.x == b.x ){ if( a.y == b.y ) return a.z < b.z; return a.y < b.y; } return a.x < b.x; } double dist(P a, P b){ return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y) + (a.z - b.z) * (a.z - b.z)); } double dot(P p1, P p2){ return p1.x * p2.x + p1.y * p2.y + p1.z * p2.z; } double norm(P p){ return dot(p, p); } double abs(P p){ return sqrt(norm(p)); } double get_angle(P p1, P p2) { double a = dot(p1, p2); double b = abs(p1); double c = abs(p2); double x = a / (b * c); if( 1.0 < x && x <= 1.0 + EPS ){ return acos(1); } if( -1.0 - EPS <= x && x < -1.0 ){ return acos(-1); } return acos(x); } double calc_angle(int to, int v, int prev, map<int,P> h) { P v1 = h[to] - h[v]; P v2 = h[v] - h[prev]; double rad = get_angle(v1, v2); double res = rad * 180.0 / PI; return res; } // dp[v][prev] := 前に来た頂点 prev で頂点 v までにたどりつく最小時間 double dp[2001][2001]; // G[v] := 頂点 v と隣接する頂点のリストを返す vector<int> G[2001]; double dijkstra(map<P,int> h, map<int,P> h_inv, int V, int S, int T){ for(int i = 0 ; i < V ; i++ ){ for(int j = 0 ; j < V ; j++ ){ dp[i][j] = INF; } } priority_queue<State> q; dp[0][0] = 0; for(int i = 0 ; i < G[0].size() ; i++ ){ int to = G[0][i]; double cost = dist(h_inv[0], h_inv[to]) / S; q.push( State(to, 0, cost)); dp[to][0] = cost; } double ans = -1; while( !q.empty() ){ int v = q.top().v, prev = q.top().prev; double cost = q.top().cost; q.pop(); // ゴールのとき if( v == 1 ){ ans = cost; break; } for(int i = 0 ; i < G[v].size() ; i++ ){ int to = G[v][i]; // さっき訪れた頂点には行かない if( to == prev ) continue; double next_cost = cost; next_cost += dist(h_inv[v], h_inv[to]) / S; next_cost += calc_angle(to, v, prev, h_inv) / T; if( next_cost < dp[to][v] ){ q.push( State(to, v, next_cost)); dp[to][v] = next_cost; } } } return ans; } int main(){ int N, S, T; while( cin >> N >> S >> T){ if( N == 0 ) break; for(int i = 0 ; i < 2001 ; i++ ) G[i].clear(); int V = 2, sx, sy, sz, gx, gy, gz; // h[p] := 座標 p = (x,y,z) に対応する頂点番号を返す map<P, int> h; // h_inv[v] := 頂点番号 v に対応する座標 (x,y,z) を返す map<int,P> h_inv; cin >> sx >> sy >> sz >> gx >> gy >> gz; P start(sx, sy, sz), goal(gx, gy, gz); h[start] = 0; h_inv[0] = start; h[goal] = 1; h_inv[1] = goal; for(int i = 0 ; i < N ; i++ ){ int x1, y1, z1, x2, y2, z2; cin >> x1 >> y1 >> z1 >> x2 >> y2 >> z2; P p1(x1, y1, z1), p2(x2, y2,z2); int u, v; if( h.count(p1) ){ u = h[p1]; }else{ u = h[p1] = V; h_inv[V] = p1; V++; } if( h.count(p2) ){ v = h[p2]; }else{ v = h[p2] = V; h_inv[V] = p2; V++; } G[u].push_back(v); G[v].push_back(u); } // スタートとゴールが同じ時の例外処理 if( start == goal ){ printf("%.4f\n", 0.0); continue; } double ans = dijkstra(h, h_inv, V, S, T); printf("%.4f\n",ans); } }
