ABC465の記録

AtCoderBeginnerContest465の感想と自分が解いたところまでの解説を書いていきます
A,B,C,DをC++,をA,B,C,Dをpythonで解きます
Atcoder Beginner Contest 465

1.感想

A問題
数学
B問題
半開区間だったことで時間かかった
C問題
dequeだろって思ったら反転可能な木でいけた
D問題
数学やんけ
E問題
桁DP
F問題
6次元累積和の実装ができてなかった
G問題
知らんて

2.結果

もうすこし上がってほしかった

3.解説

A問題 Supermajority

$A > \frac{2}{3}B \Leftrightarrow 3A > 2B$
これ判定するだけ

A, B = map(int, input().split())  
print("Yes" if 3*A > 2*B else "No")  

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

int main(){  
    int A, B;  
    cin >> A >> B;  
    puts(3*A > 2*B? "Yes": "No");  
}  

B問題 Parking 2

実装するだけ

X, Y, L, R, A, B = map(int, input().split())  
ans = 0  

for i in range(A, B):  
    if L <= i and i < R:  
        ans += X  
    else:  
        ans += Y  

print(ans)  

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

int main(){  
    int X, Y, L, R, A, B;  
    cin >> X >> Y >> L >> R >> A >> B;  

    int ans = 0;  
    for (int i = A; i < B; i++){  
        if (L <= i && i < R) ans += X;  
        else ans += Y;  
    }  

    cout << ans << endl;  
}  

C問題 Reverse Permutation

dequeか(反転木でいけるの?)
S[i]がoならpush_frontとpush_backの入れ替え

from collections import deque  

N = int(input())  
S = list(input())  
A = deque()  
R = False  

for i in range(N):  
    if not R:  
        A.append(i+1)  
    else:  
        A.appendleft(i+1)  
    if S[i] == 'o':  
        R = not R  

if R:  
    A = reversed(list(A))  
print(*A)  

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

int main(){  
    int N;  
    string S;  
    cin >> N >> S;  

    bool R = false;  
    deque<int> A;  
    for (int i = 0; i < N; i++){  
        if (!R) A.push_back(i+1);  
        else A.push_front(i+1);  
        if (S[i] == 'o') R = !R;  
    }  

    if (R) ranges::reverse(A);  
    for (int x : A) cout << x << ' ';  
    cout << endl;  
}  

D問題 X to Y

D(X)をXの深さを求める関数として深さをそろえていく

for _ in range(int(input())):  
    X, Y, K = map(int, input().split())  
    def D(v):  
        res = 0  
        while v > 0:  
            v //= K  
            res += 1  
        return res  

    dx, dy, ans = D(X), D(Y), 0  
    while dx > dy:  
        X //= K  
        dx -= 1  
        ans += 1  
    while dx < dy:  
        Y //= K  
        dy -= 1  
        ans += 1  
    while X != Y:  
        X //= K  
        Y //= K  
        ans += 2  
    print(ans)  

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

int main(){  
    int T;  
    cin >> T;  
    while (T--){  
        long X, Y, K;  
        cin >> X >> Y >> K;  
        auto D = [&](long v){  
            int res = 0;  
            while (v > 0) v /= K, res++;  
            return res;  
        };  

        int dx = D(X), dy = D(Y), ans = 0;  
        while (dx > dy) X /= K, dx--, ans++;  
        while (dx < dy) Y /= K, dy--, ans++;  
        while (X != Y) X /= K, Y /= K, ans += 2;  
        cout << ans << endl;  
    }  
}  

E問題 Digt Circus

実装がめんどいので口頭で
桁DPをして
最後に
3の倍数か3が含まれるか3種類の数字が使われるのどれかを満たすかを計算
3種類使われているかはpopcountが3であればいい