スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




Cliff Climbing

2007.07.16 01:31  ACM/ICPC 2007

[問題] 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 }
スポンサーサイト

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

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




Cut the Cakes

2007.07.16 01:27  ACM/ICPC 2007

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

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

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 }

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

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




Analyzing Login/Logout Records

2007.07.16 01:22  ACM/ICPC 2007

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

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

001 #include
002 #include
003 #include
004 using namespace std;
005 #define PMAX 1000 // number of PC
006 #define SMAX 10000 // number of Student
007 #define TMAX 1260
008 
009 int npc, nstudent;
010 bool record[SMAX+1][TMAX+1];
011 
012 void init(){
013     for ( int i = 0; i <= nstudent; i++ ){
014         for ( int t = 0; t <= TMAX; t++ ){
015             record[i][t] = false;
016         }
017     }
018 }
019 
020 void compute(){
021     int q; cin >> q;
022     int total, s, e, m;
023     for ( int i = 0; i < q; i++ ){
024         cin >> s >> e >> m;
025         total = 0;
026         for ( int t = s; t < e; t++ ){
027             if ( record[m][t] ) total++;
028         }
029         cout << total << endl;
030     }
031 }
032 
033 void fill( int student, int start, int end ){
034     for ( int t = start; t < end; t++ )	record[student][t] = true;
035 }
036 
037 bool input(){
038     cin >> npc >> nstudent;
039     if ( npc == 0 && nstudent == 0 ) return false;
040     init();
041     mapint, int>, int> login;
042     int r, t, pc, student, state;
043     cin >> r;
044     for ( int i = 0; i < r; i++ ){
045         cin >> t >> pc >> student >> state;
046         if ( state == 1 ){
047             login[make_pair(pc, student)] = t;
048         } else {
049             fill( student, login[make_pair(pc, student)], t );
050         }
051     }
052     return true;
053 }
054 
055 main(){
056     while( input()) compute();
057 }

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

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




ICPC Score Totalizer Software

2007.07.16 01:16  ACM/ICPC 2007

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

読み込みと同時に最大値、最小値、合計を計算し、
(合計 - (最小値 + 最大値))/(人数 - 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 }

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

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

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。