ABC423の記録

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

---

1.感想

A問題：
簡単(1分くらいで解けた)
150点と聞いていたが意外と簡単だった

B問題：
簡単だった、ミスせずに解けた

C問題：
簡単そうに見えて難しかった
なぜかテストケースは全部あっていたためどこが違うのか全然わからなかった

D問題：
C問題と並行して何とか解けた

2.結果

3.解説

A問題 Scary Fee

C++での実装

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

int main(){
    int X, C;
    cin >> X >> C;
    
    cout << X/(1000+C)*1000 << endl;
    
    return 0;
}

pythonでの実装

X, C = map(int, input().split())
print(X//(1000+C)*1000)

B問題 Locked Rooms

C++での実装

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

int main(){
    int N, first_locked = -1, last_locked = -1;
    cin >> N;
    vector<int> A(N);
    
    for (int i = 0; i < N; i++){
        cin >> A[i];
        if (A[i] == 1 && first_locked == -1) first_locked = i;
    }
    
    for (int i = N-1; i >= 0; i--){
        if (A[i] == 1 && last_locked == -1) last_locked = i;
    }
    
    cout << last_locked-first_locked << endl;
    return 0;
}

pythonでの解法

N = int(input())
A = list(map(int, input().split()))
first_locked = -1
last_locked = -1

for i in range(N):
    if A[i] == 1:
        if first_locked == -1:
            first_locked = i
        last_locked = i

print(last_locked-first_locked)

C問題 Lock All Doors

ACできなかったので考え方を書いていきます

1. 最初に左へ行く方法

int go_left(vector<int> &L, int left, int right, int R){
    int ans = 0;
    
    while (R > left){
        if (L[R] == 1) L[R] = 0, ans++;
        R--;
    }
    
    while (R <= right){
        if (L[R] == 1) ans += 2;
        else ans++;
        R++;
    }
    
    return ans;
}

1. 最初に右へ行く方法

int go_right(vector<int> &L, int left, int right, int R){
    int ans = 0;
    int N = (int)L.size();

    while (R > left){
        if (L[R] == 1) L[R] = 0, ans++;
        R--;
    }

    while (R <= right){
        if (L[R] == 1) ans += 2;
        else ans++;
        R++;
    }

    return ans;
}

これらの何処かがちがうと思いますがやることは

• 鍵の空いている右端に行ってから逆側に行く
• 鍵の空いている左端に行ってから逆側に行く

の最小値を取ることだと思います

D問題 Long Waiting

C++での解法

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

int main() {
    int N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N), B(N), C(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i] >> C[i];

    vector<ll> ans(N, -1);
    int idx = 0;
    ll curTime = 0;
    ll inside = 0;
    queue<int> q;
    priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> dep;

    while (idx < N || !q.empty() || !dep.empty()) {
        ll nextArrivalTime = (idx < N) ? A[idx] : (ll)4e18;
        ll nextDepartureTime = !dep.empty() ? dep.top().first : (ll)4e18;
        ll targetTime = min(nextArrivalTime, nextDepartureTime);
        if (q.empty() && curTime < targetTime) curTime = targetTime;
        else if (q.empty() && targetTime == (ll)4e18) break;

        while (!dep.empty() && dep.top().first <= curTime) {
            inside -= dep.top().second;
            dep.pop();
        }

        while (idx < N && A[idx] <= curTime) {
            q.push(idx);
            ++idx;
        }

        if (q.empty()) {
            if (idx < N && (dep.empty() || A[idx] < dep.top().first)) {
                curTime = A[idx];
                continue;
            }
            else if (!dep.empty()) {
                curTime = dep.top().first;
                continue;
            }
            else {
                break;
            }
        }

        bool admittedAny = false;
        while (!q.empty()) {
            int i = q.front();
            if (inside+C[i] <= K){
                q.pop();
                ans[i] = curTime;
                inside += C[i];
                dep.emplace(curTime+B[i], C[i]);
                admittedAny = true;
            } else break;
        }

        if (admittedAny) {
            continue;
        }

        if (!dep.empty()) {
            curTime = dep.top().first;
        }
        else if (idx < N) {
            curTime = A[idx];
        }
        else {
            break;
        }
    }

    for (int i = 0; i < N; ++i) cout << ans[i] << endl;
    return 0;
}