Volume 5 / 0540->0541
情報オリンピック 2009本選 解答
公式のページはJOI 2008-2009 本選 問題・データ
前回Q1~Q3を解いたときの記事は『Volume 5 / 0538->0540（2009年11月28日）』
Problem 0540 : Amidakuji / 4: あみだくじ
むずかしかった。解説見ても解くのに手間取った。
解き方は解説の通り。
#include <iostream> #include <vector> #include <algorithm> using namespace std; // 横棒の構造体 typedef struct CROSS_TAG { int right_num, left_num; int right_point, left_point; int r, l, h; } CROSS; vector<CROSS> crosses; int points[1001]; int n; // 縦棒の本数 int m; // 横棒の本数 int h; // 棒の長さ int k; // 選ぶ棒の本数 // ソート用 bool cross_cmp( const CROSS &left, const CROSS &right ) { return left.h < right.h; } int calc() { int i, j; int work[1001], tmp; //// 線の番号 // 初期化 for( i=1; i<=n; i++ ) work[i] = i; // 上の横棒から順に走査して入れ替え for( i=0; i<m; i++ ){ crosses[i].left_num = work[crosses[i].l]; crosses[i].right_num = work[crosses[i].r]; tmp = work[crosses[i].l]; work[crosses[i].l] = work[crosses[i].r]; work[crosses[i].r] = tmp; } //// 線のスコア // 初期化 for( i=1; i<=n; i++ ){ work[i] = points[i-1]; } // 下の横棒から順に走査して入れ替え for( i=m-1; i>=0; i-- ){ crosses[i].left_point = work[crosses[i].l]; crosses[i].right_point = work[crosses[i].r]; tmp = work[crosses[i].l]; work[crosses[i].l] = work[crosses[i].r]; work[crosses[i].r] = tmp; } // 横棒を消去しないときのスコア int score0 = 0; for( i=1; i<=k; i++ ){ score0 += work[i]; } // 横棒を消去したときの減少値の最大を求める int max = 0; for( i=0; i<m; i++ ){ // 両方ともk番目（以内｜の範囲外）の場合は処理をする必要がない if( ( crosses[i].left_num <= k && crosses[i].right_num <= k ) || ( crosses[i].left_num > k && crosses[i].right_num > k ) ) continue; // 左側がk番目以内 if( crosses[i].left_num <= k ){ // 曲がったほうがいいとき if( crosses[i].left_point >= crosses[i].right_point ) continue; // 棒を消去したときの減少値 int d = crosses[i].right_point - crosses[i].left_point; if( max < d ) max = d; } // 右側がk番目以内 if( crosses[i].right_num <= k ){ // 曲がったほうがいいとき if( crosses[i].left_point <= crosses[i].right_point ) continue; // 棒を消去したときの減少値 int d = crosses[i].left_point - crosses[i].right_point; if( max < d ) max = d; } } // 横棒を消去したスコアを返す return score0 - max; } int main(void) { int i; while( cin >> n >> m >> h >> k, n != 0 && m != 0 && h != 0 && k != 0 ){ crosses.resize(m); // 入力 for( i=0; i<n; i++ ){ cin >> points[i]; } for( i=0; i<m; i++ ){ cin >> crosses[i].l >> crosses[i].h; crosses[i].r = crosses[i].l+1; } // 横棒を高さでソート sort( crosses.begin(), crosses.end(), cross_cmp ); // 結果の出力 cout << calc() << endl; } return 0; }
Problem 0541 : Walk / 4: 散歩
DPっぽい気はしたけど、自力では形にできなかった。
解説さまさま。
#include <iostream> using namespace std; #define MAX_WH 1000 int map[MAX_WH+2][MAX_WH+2]; int cnt[MAX_WH+2][MAX_WH+2][2]; int w, h; int n; // n回目の散歩のときの道の状態を生成 void reflesh() { int sum; int x, y; if( n == 1 ) return; cnt[1][1][(map[1][1]+1)%2] = (n-1)/2; cnt[1][1][map[1][1]] = (n-1) - cnt[1][1][(map[1][1]+1)%2]; map[1][1] = (map[1][1]+(n-1)%2)%2; for( y=1; y<=h; y++ ){ for( x=1; x<=w; x++ ){ if( y == 1 && x == 1 ) continue; sum = cnt[y-1][x][0] + cnt[y][x-1][1]; cnt[y][x][(map[y][x]+1)%2] = sum/2; cnt[y][x][map[y][x]] = sum - cnt[y][x][(map[y][x]+1)%2]; map[y][x] = (map[y][x]+sum%2)%2; } } return; } // n回目の散歩のシミュレーション・結果の出力 void check() { int x, y; x = 1; y = 1; while( x != w+1 && y != h+1 ){ if( map[y][x] ) x++; else y++; } // 結果の出力 cout << y << " " << x << endl; return; } int main(void) { int x, y; int i, j; while( cin >> h >> w >> n, h != 0 && w != 0 && n != 0 ){ // 入力と初期化 for( y=0; y<=h+1; y++ ){ for( x=0; x<=w+1; x++ ){ cnt[y][x][0] = cnt[y][x][1] = 0; if( y != 0 && y != h+1 && x != 0 && x != w+1 ){ cin >> map[y][x]; } } } reflesh(); check(); } return 0; }
Problem 0542 : Authentication Level / 5: 認証レベル
解法はわかったんだけど、priority_queueを使わなかったらTLE。
priority_queueはじめて使った。なかなか早い。
#include <iostream> #include <queue> #include <algorithm> using namespace std; #define W_MAX 500 #define H_MAX 500 #define R_MAX 250000 #define L_MAX 100000000 int map[2][H_MAX+2][W_MAX+2]; // 部屋の配置 bool v[2][H_MAX+2][W_MAX+2]; // 訪れた部屋の数（探索用） int rl[2][R_MAX+1]; // r部屋訪れるために必要な認証レベル int w[2], h[2]; // 部屋の数（横、縦） int ex[2], ey[2]; // エレベーターの座標 priority_queue< pair< int, pair< int, int > > > rooms; // 訪問する予定の部屋（レベル,x座標,y座標） // r部屋訪れるために必要な認証のレベルを調べる（配列rl[][]の更新） void check( int k ) { int i, j; int dx[4] = { 0, 1, 0, -1 }; int dy[4] = { 1, 0, -1, 0 }; int count_room = 0; // 訪れた部屋の数をカウント int current_level = 0; // 現在の認証レベルを保持 int x, y, level; // キューを空にしておく while( !rooms.empty() ) rooms.pop(); // 初期化（四辺は"訪問済み"で囲っておく） for( i=0; i<=h[k]+1; i++ ) for( j=0; j<=w[k]+1; j++ ) v[k][i][j] = ( i==0 || i==h[k]+1 || j==0 || j==w[k]+1 ) ? true : false; // エレベーターの位置からスタート rooms.push( make_pair( -1, make_pair( ex[k], ey[k] ) ) ); while( rooms.size() > 0 && count_room <= w[k]*h[k] ){ // levelが一番低いものを取り出す x = rooms.top().second.first; y = rooms.top().second.second; level = -rooms.top().first; rooms.pop(); // その座標が既に訪問済み if( v[k][y][x] ) continue; // 訪問済みにする v[k][y][x] = true; // 最小の認証レベルが現在の認証レベルより大きいときは更新 if( current_level < level ) current_level = level; // 訪問済みの部屋数を増やし、その数に達するのに必要だった認証レベルを配列に格納 count_room++; rl[k][count_room] = current_level; // 未訪問の部屋をキューに追加 for( i=0; i<4; i++ ){ if( !v[k][y+dy[i]][x+dx[i]] ){ rooms.push( make_pair( -map[k][y+dy[i]][x+dx[i]], make_pair( x+dx[i], y+dy[i] ) ) ); } } } return; } int main(void) { int k, i, x, y; int r; while( cin >> r, r!=0 ){ for( k=0; k<2; k++ ){ // 入力 cin >> w[k] >> h[k] >> ex[k] >> ey[k]; for( y=1; y<=h[k]; y++ ){ for( x=1; x<=w[k]; x++ ){ cin >> map[k][y][x]; } } // 初期化 for( i=0; i<=w[k]*h[k]; i++ ) rl[k][i] = 0; // rl[][]の更新 check( k ); } int min = L_MAX; int new_val; // 認証レベルの和が最小となるものを探す for( i=0; i<=r; i++ ){ if( i > w[0]*h[0] || r-i > w[1]*h[1] ) continue; new_val = 0; new_val += rl[0][i]; new_val += rl[1][r-i]; if( min > new_val ) min = new_val; } // 結果の出力 cout << min << endl; } return 0; }
