接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 191（ABC191）

AtCoder Beginner Contest 191（ABC191）

AtCoderBeginnerContest AtCoderBeginnerContest191 ABC ABC191

atcoder.jp

A - Vanishing Pitch

$ VT \leq D \leq VS $を満たす場合No、そうでない場合Yes
提出コード

void solve(){
    int V, T, S, D;
    cin >> V >> T >> S >> D;
    if(V * T <= D and D <= V * S) cout << "No" << endl;
    else cout << "Yes" << endl;
}

B - Remove It

$ A_i = X $となる要素は出力しなければいい
提出コード

void solve(){
    int N;
    ll X;
    cin >> N >> X;
    vector<ll> A(N);
    REP(i,N) cin >> A[i];
    REP(i,N) if(A[i] != X) cout << A[i] << " ";
    cout << endl;
}

C - Digital Graffiti

問題がよくわからなくて本番中は飛ばした
$ (x, y) , (x+1, y), (x, y+1), (x+1, y+1) $の$ 2 \times 2 $長方形領域を考える
この時、この長方形領域に#が1個または3個含まれる時$ (x, y) $は頂点となる
よって上記を満たす個数を数えればいい
提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    REP(i,H) cin >> fi[i];
    int ans = 0;
    REP(i,H-1) REP(j,W-1){
        int cnt = (fi[i][j] == '#') + (fi[i][j+1] == '#') + (fi[i+1][j] == '#') + (fi[i+1][j+1] == '#');
        if(cnt == 1 or cnt == 3) ans++;
    }
    cout << ans << endl;
}

D - Circle Lattice Points

整数$ x $を固定したときに、$ y $の取りうる範囲は三平方の定理から求めることができる
よってyの上限が$ u $、下限が$ b $とすると$ u - b + 1 $個格子点が存在する
浮動小数点数のままでやると誤差があるので整数に直すのが無難そう
本番はXとYを平行移動させてlong doubleで通してしまった
提出コード

void solve(){
    long double X, Y, R;
    cin >> X >> Y >> R;
    X += 2e5;
    Y += 2e5;
    ll st = ceil(X - R);
    ll en = floor(X + R);
    ll num = 0;
    for(int i=st;i<=en;i++){
        long double p = sqrt(pow(R, 2) - pow((X - (long double)i), 2));
        ll b = ceil(Y - p);
        ll u = floor(Y + p);
        num += u - b + 1;
    }
    cout << num << endl;
}

E - Come Back Quickly

ある頂点$ i $を始点とした最短経路とある頂点$ j ( \neq i ) $からiへの最短経路がわかればいい
$ j $ から$ i $への経路は、与えられたグラフの辺をすべて逆辺にして考えるとこのグラフ上での$ i $から$ j $への最短経路となる
そのため、与えられたグラフと逆辺のグラフに対しダイクストラで全始点について求めればいい
提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    Dijkstra<ll> d1(N, LINF), d2(N, LINF);
    vector<ll> ans(N, LINF);
    REP(i,M){
        ll a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        if(a == b) chmin(ans[a], c);
        else{
            d1.make_edge(a, b, c);
            d2.make_edge(b, a, c);
        }
    }
    REP(i,N){
        d1.solve(i);
        d2.solve(i);
        REP(j,N) if(j != i){
            chmin(ans[i], d1.cost[j] + d2.cost[j]);
        }
        if(ans[i] == LINF) ans[i] = -1;
        cout << ans[i] << endl;
    }
}