【ABC397】AtCoder Beginner Contest 397【C++】

コンテスト名

オムロンプログラミングコンテスト2025（AtCoder Beginner Contest 397）

コンテストURL

https://atcoder.jp/contests/abc397

開催日

2025/03/15 21:00-22:40

---

A: Thermometer

解法

• 問題文通りに判定する

ABC397A.cpp

#include <iostream>
using namespace std;

int main(){
    double x;
    cin >> x;

    if(x>=38.0){
        cout << 1 << endl;
    }else if(x>=37.5){
        cout << 2 << endl;
    }else{
        cout << 3 << endl;
    }

    return 0;
}

B: Ticket Gate Log

解法

• 前から順番に判定する
• 文字列 $SS$ の最後の文字が i であるときに注意する

ABC397B.cpp

#include <iostream>
#include <string>
using namespace std;

int main(){
    string s;
    cin >> s;

    int sum = 0, cnt = 0;
    if(s.back()=='i'){
        cnt++;
    }
    for(int i=0; i<s.size(); i++){
        if(sum%2==0 && s[i]!='i'){
            cnt++;
            sum++;
        }else if(sum%2==1 && s[i]!='o'){
            cnt++;
            sum++;
        }
        sum++;
    }

    cout << cnt << endl;

    return 0;
}

C: Variety Split Easy

解法

• 前から $ii$ 番目の種類数と後ろから $jj$ 番目の種類数をそれぞれ vector<int> に記録する

ABC397C.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(){
    int n;
    cin >> n;

    vector<int> A(n);
    for(int i=0; i<n; i++){
        cin >> A[i];
    }

    map<int, int> M1;
    vector<int> S1(n);
    for(int i=0; i<n; i++){
        if(M1.count(A[i])){
            M1[A[i]]++;
        }else{
            M1[A[i]]++;
            S1[i]++;
        }
    }
    for(int i=1; i<n; i++){
        S1[i] += S1[i-1];
    }

    map<int, int> M2;
    vector<int> S2(n);
    for(int i=0; i<n; i++){
        if(M2.count(A[n-i-1])){
            M2[A[n-i-1]]++;
        }else{
            M2[A[n-i-1]]++;
            S2[i]++;
        }
    }
    for(int i=1; i<n; i++){
        S2[i] += S2[i-1];
    }

    int maxv = 0;
    for(int i=0; i<n-1; i++){
        maxv = max(maxv, S1[i]+S2[n-i-2]);
    }

    cout << maxv << endl;

    return 0;
}

D: Cubes

解法

• $x3−y3=(x−y)(x2+xy+y2)x^3-y^3 = (x-y)(x^2+xy+y^2)$ と因数分解する
• $d=x−yd = x-y$ とおくと、 $d≦N3d \leqq \sqrt[3]{N}$ であり、 $d3+3d2y+3dy2=Nd^3 + 3d^2y + 3dy^2 = N$ を満たす
• $dd$ を全探索して、 $yy$ についての二次方程式 $d3+3d2y+3dy2−N=0d^3 + 3d^2y + 3dy^2 - N = 0$ を解く
  • 答えは $(x,y)=(d+y,y)(x, y) = (d + y, y)$

ABC397D.cpp

#include <iostream>
using namespace std;

long long int calc(long long int a, long long int b, long long int c){
    long long int low = 0, high = 1000000001;
    while(high-low>1){
        long long int mid = low + (high - low)/2;
        if (a*mid*mid + b*mid + c <= 0){
            low = mid;
        }else{
            high = mid;
        }
    }

    if(a*low*low + b*low + c == 0){
        return low;
    }
        
    return -1;
}

int main() {
    long long int n;
    cin >> n;

    for(long long int d=1; d*d*d<=n; d++){
        if(n%d!=0){
            continue;
        }

        long long int y = calc(3, 3*d, d*d-n/d);
        if(y>0){
            cout << y + d << " " << y << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}