AtCoder Regular Contest #003

問題A:GPA計算

N文字の文字列rが与えられ,r[i]が評価を表しています。評価'A', 'B', 'C, 'D', 'F'の5種類があり、それぞれ4,3,2,1,0点です。評価を点数に換算して平均を求めます。評価は'E'でなく'F'となっているので気をつけましょう。また誤差は1e-9まで許容されるので出力する桁数が足りないとWAになります。気をつけましょう。

#include <cstdio>
using namespace std;
 
int main(){
    int N, s = 0, f[256] = {0};
    char r[101];
    f['A'] = 4;
    f['B'] = 3;
    f['C'] = 2;
    f['D'] = 1;
    f['F'] = 0;
    
    scanf("%d", &N);
    scanf("%s", r);
    for(int i=0 ; i < N ; i++ ){
        s += f[ r[i] ];
    }
    double ans = (double) s / N;
    printf("%.10f\n", ans );
}

問題B:さかさま辞書

N個の文字列が入力されるので文字列を逆順に対して辞書順でソートします。出力するときに文字列を逆順のまま出力しないように気をつけましょう。

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<string> v;
    for(int i = 0 ; i < n ; i++ ){
        string s;
        cin >> s;
        reverse( s.begin() , s.end() );
        v.push_back( s );
    }
    sort( v.begin() , v.end() );
    for(int i=0 ; i < v.size() ; i++ ){
        string s = v[i];
        reverse( s.begin() , s.end() );
        cout << s << endl;
    }
}

問題C:暗闇帰り道

普通のダイクストラ法だとw,h <= 500 と大きいので計算量が間に合いません。この問題の解法は明るさについて二分探索して解くらしいです。二分探索で明るさを決め打ちしてその明るさより暗い区画に入らないようにBFSします。ゴールにたどり着けないケースがあるので注意しましょう。
SPFA(Shortest Path Faster Algorithm)だと通るという話があるようですが、私は未確認です。

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int INF = 1e+8;
const int MAX_W = 501;
typedef pair<int,int> P;

int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
char c[MAX_W][MAX_W];
int d[MAX_W][MAX_W];
int w, h, sx, sy;

// ch := 日当たりの良さ, t := 経過時間
// 区画の明るさ = ch * 0.99^t を返す.
double light(char ch, int t){
    return (double)(ch - '0') * pow( 0.99 , t );
}

// 明るさが mid 以上のところのみで BFS
bool bfs(double mid){
    // 初期化
    for(int y=0 ; y < MAX_W ; y++ ){
        for(int x=0 ; x < MAX_W ; x++ ){
            d[y][x] = INF;
        }
    }
    queue<P> q;
    q.push( P(sx,sy) );
    d[sy][sx] = 1;
    
    while( !q.empty() ){
        int x = q.front().first;
        int y = q.front().second;
        int t = d[y][x];
        q.pop();
        
        for(int i=0 ; i < 4 ; i++ ){
            int mx = x + dx[i];
            int my = y + dy[i];
            if( mx < 0 || my < 0 || mx >= w || my >= h || c[my][mx] == '#' ) continue;
            
            if( c[my][mx] == 'g' ){
                return true;
            }
            if( d[my][mx] == INF && isdigit(c[my][mx]) && mid < light( c[my][mx] , t ) ){
                d[my][mx] = t+1;
                q.push(P(mx,my));
            }
        }
    }
    return false;
}

int main(){
    
    scanf("%d %d", &h, &w );
    for(int y=0 ; y < h ; y++ ){
        scanf("%s", c[y]);
        for(int x=0 ; x < w ; x++ ){
            if( c[y][x] == 's' ){
                sx = x; sy = y;
            }
        }
    }
    
    if( !bfs(-1) ){ // たどり着けないとき
        printf("-1\n");
    }else{
        // 二分探索
        double low=0.0, high=10.0;
        for(int k=0 ; k < 100 ; k++ ){
            double mid = (low + high) / 2.0;
            if( bfs(mid) ){
                low = mid;
            }else{
                high = mid;
            }
        }
        printf("%.10f\n", low );
    }
}

問題D:シャッフル席替え

許容される誤差が2e-3とゆるいので実際にモンテカルロ法でシミュレーションして計算すると正解できる問題でした。モンテカルロ法では正しい答えが求まる保証はないですが、試行回数を増やすことによって許容誤差以内の解を求める確率が高くなるみたいです。

#include <iostream>
#include <cstdlib>
#include <map>
#include <ctime>
#include <vector>
using namespace std;

typedef pair<int,int> P;

// [a,b] のどれかの整数を返す。 (a,b は非負整数)
int random(int a, int b){
    int range = b - a + 1;
    return rand() % range + a;
}

// (v[i],v[i+1])のペア で 隣り合っていけないペアが存在するときは false を返す.
bool check(vector<int>& v, map<P,bool>& h){
    for(int i=0 ; i < v.size() ; i++ ){
        if( h[ P( v[i] , v[(i+1)%v.size()] ) ] ){
            return false;
        }
    }
    return true;
}

int main(){
    // 乱数の種の初期化
    srand((unsigned int)time(NULL));
    
    // 入力
    int N, M, K;
    cin >> N >> M >> K;
    
    // h[P(i,j)] := (i,j) が隣り合ってはいけないとき true を返す.
    map<P,bool> h;
    for(int i=0 ; i < N ; i++ ){
        for(int j=0 ; j < N ; j++ ){
            h[P(i,j)] = false;
        }
    }
    // 0..N-1 から 異なる 2つを選ぶ組合せ
    vector<P> c;
    for(int i=0 ; i < N ; i++ ){
        for(int j=i+1 ; j < N ; j++ ){
            c.push_back( P(i,j) );
        }
    }
    
    // 入力
    for(int i=0 ; i < M ; i++ ){
        int A, B;
        cin >> A >> B;
        h[P(B,A)] = h[P(A,B)] = true;
    }
    
    // x := シミュレーションする回数, cnt := 隣り合わせにならなかった回数
    const int x = 1000000;
    int cnt=0;
    for(int i=0 ; i < x ; i++ ){
        vector<int> v(N);
        for(int j=0 ; j < N ; j++ ) v[j] = j;
        
        // k 回席替え
        for(int j=0 ; j < K ; j++ ){
            int pos = random( 0 , c.size()-1 );
            int a = c[pos].first;
            int b = c[pos].second;
            swap( v[a] , v[b] );
        }
        
        // チェック
        if( check(v,h) ){
            cnt++;
        }
    }
    double ans = (double) cnt / x;
    cout << ans << endl;
}