ABC428の記録

AtCoder428の感想と自分が解いたところまでの解説を書いていきます
(今回はAを, python, javaで書きます)
AtCoder Beginner Contest 428

1.感想

A問題：
150は意外と簡単?
B問題：
解くのに時間がかかってしまった
C問題：
ミスが多かったが一応解けた
E問題：
とりあえずBFSっぽかった

2.結果

少し上がった

3.解説

A問題 Grandma's Footsteps

C++での解法

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

int main(){
    int S, A, B, X, count, last;
    cin >> S >> A >> B >> X;
    count = X/(A+B);
    last = min(A, X%(A+B));
    cout << count*A*S+last*S << endl;
    return 0;
}

pythonでの解法

S, A, B, X = map(int, input().split())
count, last = X//(A-B), min(A, X%(A+B))
print(count*A*S+last*S)

javaでの解法

import java.util.*;

public class Main{
    static Scanner javain = new Scanner(System.in);
    
    public static void main (String[] args){
        int S = javain.nextInt();
        int A = javain.nextInt();
        int B = javain.nextInt();
        int X = javain.nextInt();
        int count = X/(A+B);
        int last = min(A, X%(A+B));
        System.out.println(count*A*S+last*S);
    }
    
    public static int min(int a, int b){
        if (a < b) return a;
        return b;
    }
}

B問題Most Frequent Substrings

C++での解法

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

int main() {
    int N, K, maxCount = 0;;
    string S;
    map<string, int> count;
    vector<string> ans;
    cin >> N >> K >> S;

    for (int i = 0; i <= N - K; i++) {
        string sub = S.substr(i, K);
        count[sub]++;
    }

    for (auto entry : count) {
        maxCount = max(maxCount, entry.second);
    }

    for (auto entry : count) {
        if (entry.second == maxCount) {
            ans.push_back(entry.first);
        }
    }

    cout << maxCount << endl;
    sort(ans.begin(), ans.end());
    for (string s : ans) {
        cout << s << ' ';
    }
    cout << endl;

    return 0;
}

C問題 Brackets Stack Query

C++での解法

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

int main() {
    int Q;
    cin >> Q;
    vector<pair<char, int>> stk;
    int balance = 0, min_balance = 0;

    for (int i = 0; i < Q; i++) {
        char query;
        cin >> query;

        if (query == '1'){
            char c;
            cin >> c;
            balance += (c == '(' ? 1 : -1);
            min_balance = min(min_balance, balance);
            stk.emplace_back(c, min_balance);
        }
        else{
            char last = stk.back().first;
            stk.pop_back();
            balance += (last == '(' ? -1 : 1);
            min_balance = stk.empty() ? 0 : stk.back().second;
        }

        puts((balance == 0 && min_balance >= 0)? "Yes": "No");
    }
}