Cliff Climbing

[問題] ACM/ICPC 国内予選2007: Problem D
[解説]
知識問題。知ってる人はラッキー☆な問題です。
ダイクストラのアルゴリズム（順位優先探索）で解きます。
この問題では、探索の空間が

足 f で崖 (i, j) にいる状態

となります。この空間においてダイクストラのアルゴリズムによって最短距離を求めます。

ダイクストラのアルゴリズムの原理を良く理解し、かつ何も見ないで実装できる力が必要ですね。

001 #include<iostream>
002 #include<queue>
003 using namespace std;
004 #define HMAX 60
005 #define WMAX 30
006 #define LEFT 0
007 #define RIGHT 1
008 #define INFTY (1<<21)
009 
010 class State{
011     public:
012     int i, j, f, c; // i, j, foot, cost
013     State(){}
014     State( int i, int j, int f, int c ): i(i), j(j), f(f), c(c){}
015     
016     bool operator < ( const State &s ) const{
017         return c > s.c;
018     }
019 };
020 
021 int H, W;
022 char C[HMAX][WMAX]; //cliff
023 priority_queue<State> PQ;
024 int D[HMAX][WMAX][2];
025 bool visited[HMAX][WMAX][2];
026 
027 bool isOutside( int i, int j ){
028     return ( i < 0 || j < 0 || H <= i || W <= j);
029 }
030 
031 int dijkstra(){
032     static const int di[2][9] = {{-2, -1, -1, 0, 0, 0, 1, 1, 2},
033                                  {-2, -1, -1, 0, 0, 0, 1, 1, 2}};
034     static const int dj[2][9] = {{-1, -2, -1, -3, -2, -1, -2, -1, -1},
035                                  {1, 1, 2, 1, 2, 3, 1, 2, 1}};
036     State u, v;
037     int ni, nj, nf;
038     
039     while ( !PQ.empty() ){
040         u = PQ.top(); PQ.pop();
041         if ( C[u.i][u.j] == 'T' ) return D[u.i][u.j][u.f];
042         visited[u.i][u.j][u.f] = true;
043         
044         for ( int r = 0; r < 9; r++ ){
045             nf = (u.f + 1)%2;
046             ni = u.i + di[nf][r]; nj = u.j + dj[nf][r];
047             if ( isOutside( ni, nj ) ||
048             C[ni][nj] == 'X' || visited[ni][nj][nf] ) continue;
049             int cost = D[u.i][u.j][u.f] + ((C[ni][nj]=='T')?0:(C[ni][nj]-'0'));
050             if ( cost < D[ni][nj][nf] ){
051                 D[ni][nj][nf] = cost;
052                 PQ.push( State(ni, nj, nf, cost) );
053             }
054         }
055     }
056     
057     return -1;
058 }
059 
060 bool initialize(){
061     cin >> W >> H;
062     if ( W == 0 && H == 0 ) return false;
063     PQ = priority_queue<State>();
064     for ( int i = 0; i < H; i++ ){
065         for ( int j = 0; j < W; j++ ){
066             cin >> C[i][j];
067             if ( C[i][j] == 'S' ){
068                 PQ.push( State( i, j, LEFT, 0) );
069                 PQ.push( State( i, j, RIGHT, 0) );
070                 D[i][j][LEFT] = D[i][j][RIGHT] = 0;
071             } else {
072                 D[i][j][LEFT] = D[i][j][RIGHT] = INFTY;
073             }
074             visited[i][j][0] = visited[i][j][1] = false;
075         }
076     }
077     return true;
078 }
079 
080 main(){
081     while ( initialize() ) cout << dijkstra() << endl;
082 }

Cut the Cakes

[問題] ACM/ICPC 国内予選2007: Problem C
[解説]
データ構造はvectorが妥当かと思います。
最初vectorの要素に１つのケーキがあります。
次に、これを取り出して、２つの新しいピースを作り、面積が小さい順にvectorに挿入します。
問題の定義から、vectorのインデックスがそのままピースの番号になります。
逐次
指定されたピースを取り出して、それから２つの新しいピースを作り、小さい順に挿入して、、、
を繰り返していきます。
最後に、面積でソートするのを忘れずに出力です。

カットする処理が多少ごちゃごちゃしてますが、数学のセンスがある人はもっとかっこ良く書けるでしょう

001 #include<iostream>
002 #include<vector>
003 #include<algorithm>
004 using namespace std;
005 
006 class Piece{
007     public:
008     int d, w, area;
009     Piece(){}
010     Piece( int d, int w ): d(d), w(w){ area = d*w; }
011     
012     bool operator < ( const Piece &p ) const{
013         return area < p.area;
014     }
015 };
016 
017 int n;
018 vector<Piece> P;
019 
020 void cut( int p, int s ){
021     Piece target = P[p]; P.erase( P.begin() + p );
022     Piece new1, new2;
023     int d = target.d;
024     int w = target.w;
025     int c1 = w;
026     int c2 = w + d;
027     int c3 = 2*w + d;
028     int c4 = 2*w + 2*d;
029     s = s % c4;
030     if ( 0 < s && s < c1 ){
031         new1 = Piece( d, s ); new2 = Piece( d, c1 - s );
032     } else if ( c2 < s && s < c3 ){
033         new1 = Piece( d, c3 - s ); new2 = Piece( d, s - c2 );
034     } else if ( c1 < s && s < c2 ){
035         new1 = Piece( s - c1, w ); new2 = Piece( c2 - s, w );
036     } else if ( c3 < s && s < c4 ){
037         new1 = Piece( s - c3, w ); new2 = Piece( c4 - s, w );
038     }
039     
040     if ( new1 < new2 ){ P.push_back( new1 ); P.push_back( new2 ); }
041     else { P.push_back( new2 ); P.push_back( new1 ); }
042 }
043 
044 void simulate(){
045     int p, s;
046     for ( int i = 0; i < n; i++ ){
047         cin >> p >> s;
048         cut( p - 1, s );
049     }
050     sort( P.begin(), P.end() );
051     for ( int i = 0; i < P.size(); i++ ){
052         if ( i ) cout << " ";
053         cout << P[i].area;
054     }
055     cout << endl;
056 }
057 
058 bool input(){
059     int w, d;
060     cin >> n >> w >> d;
061     if ( n == 0 && w == 0 && d == 0 ) return false;
062     P.clear();
063     P.push_back(Piece(d, w));
064     return true;
065 }
066 
067 main(){
068     while ( input() ) simulate();
069 }

Analyzing Login/Logout Records

[問題] ACM/ICPC 国内予選2007: Problem B
[解説]
生徒と時間に関するbool値の２次元配列を埋めていく方法が安全で簡単です。
入力から各生徒のマシンごとのログイン・ログアウトの状況を記録していくのが多少面倒ですが、map を使うと便利だと思います。

コンテストではこの力任せ方法が妥当ですが、 実際のシステムではこのようには実装しないでしょうね。

001 #include
002 #include
003 #include

ICPC Score Totalizer Software

[問題] ACM/ICPC 国内予選2007: Problem A
[解説]
ＩＣＰＣ国内予選、史上最も簡単な問題ではないでしょうか。
解説するのもなんですが、やっとの思いで解いたチームの参考になれば幸いです。

読み込みと同時に最大値、最小値、合計を計算し、
(合計 - (最小値 + 最大値))/(人数 - 2)　を出力します。

001 #include<iostream>
002 #include<algorithm>
003 using namespace std;
004 
005 main(){
006     int N, maxv, minv, total, score;
007     while(1){
008         cin >> N;
009         if ( N == 0 ) break;
010         total = 0;
011         maxv = 0, minv = INT_MAX;
012         for ( int i = 0; i < N; i++ ){
013             cin >> score;
014             maxv = max( maxv, score);
015             minv = min( minv, score);
016             total += score;
017         }
018         cout << (total - minv - maxv)/(N-2) << endl;
019     }
020 }

ACM/ICPC 国内予選 2007

ID	問題	難易度	考察
A	ICPC Score Totalizer Software	☆	-
B	Analyzing Login/Logout Records	★☆	-
C	Cut the Cakes	★★☆	-
D	Cliff Climbing	★★★	-
E	Twirl Around	★★★★★	grave
F	Dr. Podboq or: How We Became Asymmetric	★★★★☆	-

データがまだ公開されてませんが、解いてみました。解く順番はＡ→Ｂ→Ｃ→Ｄ→Ｆ→Ｅが妥当でしょう。しかし、３問目をトップで通過したチームはＡ→Ｂ→Ｄの順で解いています。なぜなら、Ｄは知識問題だからです。

最初の４問を解けないチームは、このままではアジア地区予選で撃沈してしまうでしょう。選手の皆さん練習頑張って下さい。

今年は、最初の４問をいかに速く解くかがポイントになりましたね。５問解いたチームはさすがです。