競プロ日記#25/04/24

AtCoder

日立製作所 社会システム事業部 プログラミングコンテスト2020

B-Nice Shopping

• 割引券を使わない→最安のレンジと冷蔵庫を買うパターンを忘れない

int main() {
    int A,B,M;
    cin >> A >> B >> M;
    vector<int> a(A), b(B);
    
    for (int i = 0; i < A; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < B; i++) {
        cin >> b[i];
    }

    
    int ans = *min_element(a.begin(), a.end()) + *min_element(b.begin(), b.end());
    for (int i = 0; i < M;i++){
        int x, y, c;
        cin >> x >> y >> c;
        ans = min(ans, a[x - 1] + b[y - 1] - c);
    }

    cout << ans << endl;
}

ABC150_C-Count Order

• 解説を読んで実装しました...。
• 前提としてnext_permutation(mini.begin(), mini.end())という順列を辞書順に一つ進める関数があるというのを知らなかった
• その上で辞書順で最小の順列を表す配列を用意して、その配列とそれぞれの配列を比較していくというアイデアもなかった。

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    vector<int> b(N);
    vector<int> mini(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> b[i];
    }
    for (int i = 0; i < N; i++) {
        mini[i] = i + 1;
    }
    int x;
    int y;
    int counter = 0;

    do {
        if (mini == a) {
            x = counter;
        }
        if (mini == b) {
            y = counter;
        }
        counter++;
    }while(next_permutation(mini.begin(), mini.end()));

    cout << abs(x - y) << endl;
}

ABC150_A-500 Yen Coins

• 特になし

ABC_B-Count ABC

• 特になし

int main() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    for (int i = 0;i < N - 2;i++){
        if ((S[i] == 'A') && (S[i + 1] == 'B') && (S[i + 2] == 'C')){
            ans++;
        }
    }
    cout << ans << endl;
}

アルゴ式-フィボナッチ数列

• 書かれている通りに実装するという意味では簡単だがメモ化という概念をきちんと理解できているかというと半々くらい。そもそも再帰関数自体があまり好きではない

int func(int n){
    if (n == 0) return 0;
    if (n == 1) return 1;
    return func(n-1) + func(n-2);
}

int main() {
    int N;
    cin >> N;
    
    cout << func(N) << endl;
}

↑

アルゴ式-フィボナッチ数列のメモ化

• 配列変数.resize()で再定義できるのでそれを使うべし（グローバルで頑張って上手いことやろうとしたけど無理だった）

vector<long long> fib;

long long func(int n){
    
    if (fib[n] != -1){
        return fib[n];
    }else{
        fib[n] = func(n-1) + func(n-2);
        return fib[n];
    }
    
}

int main() {
    long long N;
    cin >> N;
    fib.resize(N+1, -1);
    
    fib[0] = 0;
    fib[1] = 1;
    cout << func(N) << endl;
}

アルゴ式-逆ポーランド記法の計算

• 実装をそのまますることはできると思ったが、「そもそも逆ポーランド記法で標準入力されないと活用できなくね？」という疑問が頭から離れずとりあえず解説を読みた過ぎて解説見てしまった。

int main() {
    string X; cin >> X;
    int N; cin >> N;
    vector<string> S(N);
    for(int i = 0; i < N; ++i) {
        cin >> S[i];
    }

    stack<int> numbers; // 数字を記録するスタック
    for(int i = 0; i < N; ++i) {
        string tmp = S[i];
        if(tmp == "+" || tmp == "-" || tmp == "*") {
            // 今見ている文字列が演算子ならば、スタックから数字を 2 つ取り出して計算結果をスタックに入れる
            int n2 = numbers.top(); numbers.pop();
            int n1 = numbers.top(); numbers.pop();
            int n;

            if(tmp == "+") {n = n1 + n2;}
            else if(tmp == "-") {n = n1 - n2;}
            else if(tmp == "*") {n = n1 * n2;}
            numbers.push(n);
        }
        else {
            // 今見ている文字列が数字ならば、数値に変換してスタックに保存する
            int n = stoi(tmp);
            numbers.push(n);
        }
    }

    int ans = numbers.top();
    cout << X << "=" << ans << endl;

	return 0;
}