ABC203 解説 - Motsu_xe 競プロのhogeやfuga

AtCoder Beginner Contest 203（Sponsored by Panasonic）の解説記事です。私は2100点(75:49)74位でした。

A - Chinchirorin

思考

最初同じものが2つ必ずあると思って、a,b,cのxorを出力しそうになりましたが、必ずしもそうでないので、チェックする必要があります。変に楽をしようとして、長さ3の配列に入れてソートしていますが、正直言われたままやる方が良い気がします。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[3];
    for(int i{};i<(3);++i){
        cin >> a[i];
    }
    sort(a, a+3);
    if(a[0] == a[1]) cout << a[2] << endl;
    else if(a[1] == a[2] ) cout << a[0] << endl;
    else cout << 0 << endl;
}

コンテスト中のACコード

B - AtCoder Condominium

思考

N, Kは十分小さいので、全ての部屋番号を求めて、実際に足せば良いです。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    int ans{};
    for(int i{1};i<=(n);++i){
        for(int j{1};j<=(k);++j){
            ans += 100*i + j;
        }
    }
    cout << ans << endl;
}

コンテスト中のACコード

C - Friends and Travel costs

思考

真面目にシミュレーションすることもできますが、まず持ってるお金で限界まで進み、友達の下をすでに通り過ぎていたら、その時点でその友達からお金をもらうと考えてもよく、こう考えると実装が楽になります。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    int n, k;
    cin >> n >> k;
    vector<ll> a(n), b(n), p(n);
    for(int i{};i<(n);++i){
        cin >> a[i] >> b[i];
    }
    iota(begin(p),end(p),0);
    sort(begin(p),end(p),[&](int i,int j){
        return a[i] < a[j];
    });
    ll nw = k;
    for(auto&i:p){
        if(nw < a[i]){
            break;
        }
        else{
            nw += b[i];
        }
    }
    cout << nw << endl;
}

コンテスト中のACコード

D - Pond

思考

最初、全てのK*Kの区画について、中央値を求める問題と誤読して $O(N^2K\log K)$ とか*1しか思いつかず、もう一度問題文を読むと、中央値の最小値を求める問題でした。

「中央値がX以下となる区画が存在する」という問題を解くことができれば、二分探索で解くことができます。中央値がX以下となるためには、その区画の半分以上*2がX以下であることが必要十分です。よって各マスについて、X以下かどうかだけの情報でよく、これは二次元累積和などを用いれば、 $O(N^2)$ の前計算で、各区画について $O(1)$ でX以下のマスの個数を答えることができるため、解くことができました。

中央値の定義を癖で昇順で考えて、サンプル合わずに首をひねり、そのデバッグ中に二分探索の上限を引き下げたのを忘れて、1e9を19にしたまま提出し1WA出て悲しい気持ちになります。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    auto a = vector(n, vector(n, 0));
    for(auto&v:a) for(auto&i:v) cin >> i;
    int l = -1, r = 1e9, m;
    auto s = vector(n+1, vector(n+1, 0));
    int lim = (k*k+1)/2;
    while(r - l > 1){
        m = (l+r)/2;
        s.assign(n+1, vector(n+1, 0));
        for(int i{};i<(n);++i){
            for(int j{};j<(n);++j){
                s[i+1][j+1] = (a[i][j] <= m);
            }
        }
        for(int i{1};i<=(n);++i){
            for(int j{1};j<=(n);++j){
                s[i][j] += s[i][j-1];
            }
        }
        for(int j{1};j<=(n);++j){
            for(int i{1};i<=(n);++i){
                s[i][j] += s[i-1][j];
            }
        }
        bool f = false;
        for(int i{};i<=(n-k);++i){
            for(int j{};j<=(n-k);++j){
                if(s[i][j] - s[i+k][j] - s[i][j+k] + s[i+k][j+k] >= lim){
                    f = true;
                    break;
                }
            }
            if(f) break;
        }
        if(f) r = m;
        else l = m;
    }
    cout << r << endl;
}

コンテスト中のACコード

E - White Pawn

思考

ある行について、白の置ける列が減る条件と、増える条件を考えていきます。

まず白の置ける列が減る条件は、もともとポーンが置けた列に、黒が置かれていることです。

次に白の置ける列が増える条件は、その列の隣にポーンが置けたときに、その列に黒が置かれていることです。ただし、増える条件は減る条件よりも優先されることに注意が必要です。

よって白の置ける列の集合を管理して、上の方の行から黒が置かれている点について、白の置ける列の変動をチェックすれば良いです。これはstd::setなどを用いれば、 $O(M\log M)$ などで実行可能です。

実装例

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    int n, m;
    cin >> n >> m;
    map<int, vector<int>> mp;
    for(int i{}, x, y;i<(m);++i){
        cin >> x >> y;
        mp[x].push_back(y);
    }
    set<int> st;
    st.insert(n);
    for(auto[x, v]:mp){
        vector<int> pu, er;
        for(auto y:v){
            if(y and st.count(y-1)) pu.push_back(y);
            else if(y < 2*n and st.count(y+1)) pu.push_back(y);
            if(st.count(y)) er.push_back(y);
        }
        for(auto y:er) st.erase(y);
        for(auto y:pu) st.insert(y);
    }
    cout << st.size() << endl;
}

コンテスト中のACコード

F - Weed

思考

高橋君と青木君の操作回数を共に考える必要があります。こういう問題は、いわゆる頂点倍化などの方法を取ることで、グラフの最短距離の問題に帰着できます。一見青木君の操作回数も、高橋君の操作回数も多く、頂点倍化すると頂点が増え過ぎて破滅するように見えますが、実は高橋君の操作回数は、高々30回程度であることがわかります(操作後の高さの最大値が半々になっていくことからわかります)。

Aはソート済として、 $D_{x, y}=$ (x以下番目の草を高橋君の操作回数y回で全て抜くための青木君の最小の操作回数)とします。これは適当に辺を生やすと、 $O(N\log A)$ 個くらいで、かつ各辺の長さは1以下となるので、0-1BFSでよしなに解くことができます。

実装例

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto&i:a) cin >> i;
    sort(begin(a),end(a));
    using P = pair<int, int>;
    vector<int> p(n);
    auto e = vector(n+1, vector<int>());
    for(int i{};i<(n);++i){
        p[i] = upper_bound(begin(a),end(a),a[i]/2) - begin(a);
        e[p[i]].push_back(i+1);
    }
    auto d = vector(n + 1, vector(32, INT_MAX));
    deque<P> dq;
    dq.emplace_back(0, 0);
    d[0][0] = 0;
    while(!dq.empty()){
        auto[x,y] = dq.front();dq.pop_front();
        if(x < n and d[x+1][y] > d[x][y] + 1){
            dq.emplace_back(x+1, y);
            d[x+1][y] = d[x][y] + 1;
        }
        if(x and d[x-1][y] > d[x][y]){
            dq.emplace_front(x-1, y);
            d[x-1][y] = d[x][y];
        }
        if(y < 31){
            for(auto i:e[x]) if(d[i][y+1] > d[x][y]){
                dq.emplace_front(i, y+1);
                d[i][y+1] = d[x][y];
            }
        }
    }
    for(int i{};i<(32);++i){
        if(d[n][i]<=k){
            cout << i << " " << d[n][i] << endl;
            break;
        }
    }
}