Zenn
🔵

【ABC363】AtCoder Beginner Contest 363【C++】

2024/07/21に公開
C++
競技プログラミング
AtCoder
アルゴリズム
tech

コンテスト名

AtCoder Beginner Contest 363

コンテストURL

https://atcoder.jp/contests/abc363

開催日

2024/07/20 21:00-22:40

A: Piling Up

解法

  • 問題文通り条件分岐する
  • 計算して求める
    • (\lfloor \frac{R}{100} \rfloor + 1) \times 100 - R
ABC363_1A.cpp
#include <iostream>
using namespace std;

int main(){
    int r;
    cin >> r;

    if(r<=99){
        cout << 99 - r + 1 << endl;
    }else if(r<=199){
        cout << 199 - r + 1 << endl;
    }else if(r<=299){
        cout << 299 - r + 1 << endl;
    }

    return 0;
}
ABC363_2A.cpp
#include <iostream>
using namespace std;

int main(){
    int r;
    cin >> r;

    cout << (r / 100 + 1) * 100 - r << endl;
    return 0;
}

B: Japanese Cursed Doll

解法

  • 問題文通りシミュレーションする
    • 毎回条件を満たしているか判定し、全員の髪の長さを 1 増やす
  • P 番目に髪が長い人の髪の長さが T 以上になる日を求める
    • 髪の長さの降順にソートして P 番目の人の髪の長さを取得する
ABC363B_1.cpp
#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n, t, p;
    cin >> n >> t >> p;

    vector<int> L(n);
    for(int i=0; i<n; i++){
        cin >> L[i];
    }

    int ans = 0;
    while(true){
        int cnt = 0;
        for(int i=0; i<n; i++){
            if(L[i]>=t){
                cnt++;
            }
        }

        if(cnt>=p){
            break;
        }

        ans++;

        for(int i=0; i<n; i++){
            L[i]++;
        }
    }

    cout << ans << endl;
    return 0;
}
ABC363B_2.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, t, p;
    cin >> n >> t >> p;

    vector<int> L(n);
    for(int i=0; i<n; i++){
        cin >> L[i];
    }

    sort(L.rbegin(), L.rend());
    if(L[p-1]>=t){
        cout << 0 << endl;
    }else{
        cout << t - L[p-1] << endl;
    }

    return 0;
}

C: Avoid K Palindrome 2

解法

  • 順列全探索
  • 文字列 S を昇順にソートしてから next_permutation() にかける
  • 長さ K の回文を部分文字列として含むかを全探索して判定する
ABC363C.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    sort(s.begin(), s.end());

    int cnt = 0;
    do{
        bool flag = true;
        for(int i=0; i<=n-k; i++){
            string x = s.substr(i, k);
            string y = x;
            reverse(y.begin(), y.end());
            if(x==y){
                flag = false;
                break;
            }
        }

        if(flag){
            cnt++;
        }
    }while(next_permutation(s.begin(), s.end()));

    cout << cnt << endl;
    return 0;
}

D: Palindromic Number

解法

  • 回文数の法則を考える
    • d 桁の回文数を昇順に列挙すると、上位 \lceil \frac{d}{2} \rceil 桁の昇順に並んでいる
    • 上位 \lceil \frac{d}{2} \rceil 桁について考える
    • d 桁の回文数は 9 \times 10^{\lfloor \frac{d - 1}{2} \rfloor} 個ある
    • N 番目の回文数が何桁であるかを探して求める
  • 1 桁の回文数に注意する
ABC363D.cpp
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    long long int n;
    cin >> n;

    if(n<=10){
        cout << n - 1 << endl;
        return 0;
    }

    long long int cnt = 10;
    int keta;
    long long int x = 1, y, z;
    for(keta=2; ; keta++){
        if(n<=cnt){
            break;
        }

        if(keta%2==1){
            x *= 10;
        }

        z = x;
        
        y = x * 9;
        cnt += y;
    }
    
    n -= (cnt - y);
    string ans = to_string(z + n - 1);
    string rans;
    if(keta%2){
        rans = ans;
    }else{
        rans = ans.substr(0, ans.size()-1);
    }
    
    reverse(rans.begin(), rans.end());
    ans += rans;

    cout << ans << endl;
    return 0;
}

E: Sinking Land

解法

  • ダイクストラ法
  • 初めて海に接した年 x で場合分けする
    • A_{i, j} > x ならば、 A_{i, j} 年後に沈む
    • A_{i, j} \leqq x ならば、 x 年後に沈む
  • 沈む年を vector<vector<int>> に記録する
  • 沈む年と座標を priority_queue<tuple<int, int, int>> にプッシュする
  • 最初から海に接している外周の区画で初期化する
  • map<int, int> で各年に沈んだ区画数を記録する
ABC363E.cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <tuple>
using namespace std;

int main(){
    int h, w, y;
    cin >> h >> w >> y;

    vector<vector<int>> G(h, vector<int>(w));
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> G[i][j];
        }
    }

    vector<vector<int>> sink(h, vector<int>(w, -1));
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> Q;
    for(int i=0; i<h; i++){
        Q.emplace(G[i][0], i, 0);
        sink[i][0] = G[i][0];
        Q.emplace(G[i][w-1], i, w-1);
        sink[i][w-1] = G[i][w-1];
    }
    for(int i=0; i<w; i++){
        Q.emplace(G[0][i], 0, i);
        sink[0][i] = G[0][i];
        Q.emplace(G[h-1][i], h-1, i);
        sink[h-1][i] = G[h-1][i];
    }

    vector<int> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    while(!Q.empty()){
        auto [height, x, y] = Q.top();
        Q.pop();

        if(sink[x][y]!=height){
            continue;
        }

        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx<0 || nx>h-1 || ny<0 || ny>w-1){
                continue;
            }
            if(sink[nx][ny]>0){
                continue;
            }
            
            int maxv = max(height, G[nx][ny]);
            sink[nx][ny] = maxv;
            Q.emplace(maxv, nx, ny);
        }
    }

    map<int, int> ans;
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            ans[sink[i][j]]++;
        }
    }

    int cnt = h * w;
    for(int i=1; i<=y; i++){
        cout << cnt - ans[i] << endl;
        cnt -= ans[i];
    }

    return 0;
}

Discussion