Go to Qiita Advent Calendar Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@RubyLrving(ruby lrving)

AtCoder Beginner Contest 384

Last updated at Posted at 2024-12-17

A - aaaadaa

O(N)
シミュレートしましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    char c1, c2;
    cin >> N >> c1 >> c2;
    string S;
    cin >> S;

    rep(i, N){
        if(S[i] != c1) S[i] = c2;
    }
    cout << S << endl;

    return 0;
}

B - ARC Division

O(N)
シミュレートしましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, R;
    cin >> N >> R;
    
    rep(i, N){
        int d, a;
        cin >> d >> a;
        if(d == 1 && 1600 <= R && R <= 2799){
            R += a;
        }
        if(d == 2 && 1200 <= R && R <= 2399){
            R += a;
        }
    }
    cout << R << endl;

    return 0;
}

C - Perfect Standings

O(2^5+N)
bit全探索と複数条件ソートの問題です。
"ABCDE"の文字を使用して、31パターンの全ての組み合わせを作成します。
アルファベット毎に得点を加算して合計を求めます。
得点＞辞書順の優先順に並び替えて表示します。

自力ACしたコードでは、「bit全探索」を除いて31パターンの全ての組み合わせを用意しています。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

string use[31] = {
"ABCDE",
"BCDE",
"ACDE",
"ABDE",
"ABCE",
"ABCD",
"CDE",
"BDE",
"ADE",
"BCE",
"ACE",
"BCD",
"ABE",
"ACD",
"ABD",
"ABC",
"DE",
"CE",
"BE",
"CD",
"AE",
"BD",
"AD",
"BC",
"AC",
"AB",
"E",
"D",
"C",
"B",
"A"
};

int main() {
    int N = 5;
    vector<int> v(N);
    rep(i, N) cin >> v[i];

    vector<pair<int, string>> ans;
    rep(i, 31){
        int M = use[i].size();
        int sum = 0;
        rep(j, M){
            int index = use[i][j] - 'A';
            sum += v[index];
        }
        ans.push_back({sum, use[i]});
    }

    sort(ans.begin(), ans.end(), [](const pair<int, string> &x, const pair<int, string> &y){
        return x.first == y.first? x.second > y.second:x.first < y.first;
    });
    reverse(ans.begin(), ans.end());

    rep(i, 31){
        cout << ans[i].second << endl;
    }
   
   return 0;
}

コードを整理しましょう。
アルファベットの組み合わせは、bit全探索で実装します。
得点、文字列のペアをソートして答えを求めます。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N = 5;
    vector<int> v(N);
    rep(i, N) cin >> v[i];

    vector<pair<int, string>> ans;
    for(int bit=1; bit<(1 << 5); bit++){
        string s;
        int sum = 0;
        for(int i=0; i<5; i++){
            if(bit >> i & 1){
                sum += v[i];
                s += 'A' + i;
            }
        }
        ans.push_back({-sum, s});
    }

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

    for(auto [score, name]:ans){
        cout << name << endl;
    }
   
   return 0;
}

コンテスト中にこのようなコードが書けるようになりたいですね。

D - Repeated Sequence

O(N)
周期性、連続する区間の問題です。
周期性は余り、連続する区間は尺取り法を使用します。
尺取り法における円循環なので、aの配列をつなげたaaの配列を準備します。
S % Aの合計totalが0なら答えは"Yes"となります。

C++
    S = S % total;
    if(S == 0){
        cout << "Yes" << endl;
        return 0;
    }

尺取り法におけるループの条件は、

  • rightがaaのサイズ以下
  • 探索中の合計がS未満
C++
while(right < aa.size() && sum < S)

尺取り法の部分を実装しましょう。
sum == Sなら"Yes"を出力し処理を終了します。
sum -= aa[left]を忘れず減算しましょう。

C++
    rep(left, aa.size()){
        while(right < aa.size() && sum < S){
            sum += aa[right];
            right++;
        }

        if(sum == S){
            cout << "Yes" << endl;
            return 0;
        }
        sum -= aa[left];
    }

考察が終わったので実装しましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, S;
    cin >> N >> S;
    vector<ll> a(N), aa(N*2);
    rep(i, N) cin >> a[i];
    ll total = 0;
    rep(i, N) total += a[i];
    rep(i, N*2) aa[i] = a[i%N];
    S = S % total;
    if(S == 0){
        cout << "Yes" << endl;
        return 0;
    }

    ll right = 0;
    ll sum = 0;
    rep(left, aa.size()){
        while(right < aa.size() && sum < S){
            sum += aa[right];
            right++;
        }

        if(sum == S){
            cout << "Yes" << endl;
            return 0;
        }
        sum -= aa[left];
    }
    cout << "No" << endl;

    return 0;
}

E - Takahashi is Slime 2

O(HWlogN)
優先度付きキューのbfsの問題です。
スライムが隣接しているマスを毎回探索して、1/X未満か判定するとTLEになります。
隣接するスライムの強さを優先度付きキューに格納して、最も強さの小さいスライムを判定します。

1/X未満か判定する時は、X - 1を加算すると簡単に判定できます。

C++
if(size >= (total + X - 1) / X)

高橋くんの強さの初期値をS[P][Q]、最初に優先度付きキューへ追加するスライムの強さを0にすることでbfsを綺麗に実装することができます。

C++
    ll total = S[P][Q];
    priority_queue<slime, vector<slime>, Compare> pque;
    pque.emplace(slime(0, Q, P));
    used[P][Q] = true;

考察が終わったので実装しましょう。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

struct slime {
    ll size;
    int x;
    int y;
    slime(ll size_, int x_, int y_) : size(size_), x(x_), y(y_) {}
};

struct Compare {
    bool operator()(const slime& a, const slime& b) {
        return a.size > b.size; 
    }
};

int main() {
    int H, W;
    ll X;
    cin >> H >> W >> X;
    int P, Q;
    cin >> P >> Q;
    P--; Q--;
    vector<vector<ll>> S(H, vector<ll>(W));
    vector<vector<bool>> used(H, vector<bool>(W, false));
    rep(i, H) rep(j, W) cin >> S[i][j];

    ll total = S[P][Q];
    priority_queue<slime, vector<slime>, Compare> pque;
    pque.emplace(slime(0, Q, P));
    used[P][Q] = true;
    
    while(pque.size()){
        const auto [size, x, y] = pque.top();
        pque.pop();

        if(size >= (total + X - 1) / X){
            break;
        }

        total += size;

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

            if(xx<0 || W<=xx || yy<0 || H<=yy) continue;

            if(used[yy][xx] == false){
                used[yy][xx] = true;
                pque.emplace(slime(S[yy][xx], xx, yy));
            }
        }
    }
    cout << total << endl;

    return 0;
}

このコードを整理しましょう。
自作の構造体を用意しましたが、tupleで十分です。
Compareがいらなくなり、greater<int>()でソートが可能になります。

C++
struct slime {
    ll size;
    int x;
    int y;
    slime(ll size_, int x_, int y_) : size(size_), x(x_), y(y_) {}
};

struct Compare {
    bool operator()(const slime& a, const slime& b) {
        return a.size > b.size; 
    }
};

以下が修正したコードです。

C++
#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using P = pair<int,int>;
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};

int main() {
    int H, W;
    ll X;
    cin >> H >> W >> X;
    int P, Q;
    cin >> P >> Q;
    P--; Q--;
    vector<vector<ll>> S(H, vector<ll>(W));
    rep(i, H) rep(j, W) cin >> S[i][j];

    ll total = S[P][Q];
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<int>> pque;
    pque.emplace(0, Q, P);
    
    vector<vector<bool>> used(H, vector<bool>(W, false));
    used[P][Q] = true;
    
    while(pque.size()){
        const auto [size, x, y] = pque.top();
        pque.pop();

        if(size >= (total + X - 1) / X){
            break;
        }

        total += size;

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

            if(xx<0 || W<=xx || yy<0 || H<=yy) continue;

            if(used[yy][xx] == false){
                used[yy][xx] = true;
                pque.emplace(S[yy][xx], xx, yy);
            }
        }
    }
    cout << total << endl;

    return 0;
}
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?