接着剤の精進日記

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

トップ > AtCoderBeginnerContest > AtCoder Beginner Contest 224（ABC224）

AtCoder Beginner Contest 224（ABC224）

AtCoderBeginnerContest AtCoderBeginnerContest224 ABC ABC224

atcoder.jp

A - Tires

末尾がerかどうか判定する

提出コード

void solve(){
    string S;
    cin >> S;
    int N = S.size();
    if(N == 2){
        cout << "er" << endl;
    }
    else{
        if(S[N-2] == 'e' and S[N-1] == 'r') cout << "er" << endl;
        else cout << "ist" << endl;
    }
}

B - Mongeness

$ O(N^4) $ が間に合うので愚直に計算する

提出コード

void solve(){
    int H, W;
    cin >> H >> W;
    vector<vector<ll>> A(H, vector<ll>(W));
    REP(i,H) REP(j,W) cin >> A[i][j];
    bool ok = true;
    REP(i1,H) REP(i2,i1+1,H){
        REP(j1,W) REP(j2,j1+1,W){
            if(!(A[i1][j1] + A[i2][j2] <= A[i2][j1] + A[i1][j2])) ok = false;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;
}

C - Triangle?

選んだ3点の三角形が正の面積を持つには3点が一直線上になければいい
3点から2つの直線の傾きを求め、その傾きが一致していなければ正の面積を持つ

提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    ll ans = 0;
    REP(i,N) for(int j=i+1;j<N;j++) for(int k=j+1;k<N;k++){
        int x1 = x[j] - x[i], y1 = y[j] - y[i];
        int x2 = x[k] - x[i], y2 = y[k] - y[i];
        int g1 = gcd(abs(x1), abs(y1));
        int g2 = gcd(abs(x2), abs(y2));
        x1 /= g1, y1 /= g1, x2 /= g2, y2 /= g2;
        if(x1 == 0) y1 = 1;
        if(y1 == 0) x1 = 1;
        if(x1 < 0) x1 *= -1, y1 *= -1;
        if(x2 == 0) y2 = 1;
        if(y2 == 0) x2 = 1;
        if(x2 < 0) x2 *= -1, y2 *= -1;
        if(x1 == x2 and y1 == y2) continue;
        ans++;
    }
    cout << ans << endl;
}

D - 8 Puzzle on Graph

あり得る状態の数は全部で $ 9! $ なので全探索ができる
map<vector<int>, int で各状態までに必要な最小操作回数を管理し、その遷移をBFSで求める

提出コード

void solve(){
    int M;
    cin >> M;
    vector<vector<int>> g(9);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    vector<int> p(8);
    vector<int> koma(9);
    REP(i,8){
        cin >> p[i];
        --p[i];
        koma[p[i]] = i+1;
    }
    map<vector<int>, int> mp;
    queue<vector<int>> q;
    q.emplace(koma);
    mp[koma] = 0;
    while(!q.empty()){
        auto ko = q.front(); q.pop();
        int d = mp[ko];
        int v = -1;
        REP(i,9) if(ko[i] == 0) v = i;
        for(auto nv : g[v]){
            swap(ko[nv], ko[v]);
            if(!mp.count(ko)){
                q.emplace(ko);
                mp[ko] = d + 1;
            }
            swap(ko[nv], ko[v]);
        }
    }
    vector<int> idx(9);
    iota(idx.begin(), idx.end(), 1);
    idx.back() = 0;
    if(mp.count(idx)) cout << mp[idx] << endl;
    else cout << -1 << endl;
}

E - Integers on Grid

$ a_i $ の降順に見ていき、 $ a_i $ と同じ行、または同じ列の$ a_i $ より真に小さいものに移動できるとして求める
各列、行の移動回数の最大を $ rmax, \; cmax $ で管理すると $ a_i $ の答えは $ dp_i = \max(rmax_{r_i}, cmax_{c_i} ) $ となる
その後、$ rmax_{r_i} = \max(rmax_{r_i}, dp_i + 1), \; cmax_{c_i} = \max(cmax_{c_i}, dp_i + 1)$ として各列、行を更新していく

提出コード

void solve(){
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> r(N), c(N), a(N);
    map<int, vector<int>> mp;
    REP(i,N){
        cin >> r[i] >> c[i] >> a[i];
        mp[a[i]].emplace_back(i);
    }
    vector<int> rmax(H+10), cmax(W+10);
    vector<int> dp(N);
    for(auto itr=mp.rbegin();itr!=mp.rend();itr++){
        for(auto i : itr->second) dp[i] = max(rmax[r[i]], cmax[c[i]]);
        for(auto i : itr->second){
            chmax(rmax[r[i]], dp[i] + 1);
            chmax(cmax[c[i]], dp[i] + 1);
        }
    }
    REP(i,N) cout << dp[i] << endl;
}