🔵

【ABC389】AtCoder Beginner Contest 389【C++】

2025/01/20に公開

コンテスト名

トヨタ自動車プログラミングコンテスト2025(AtCoder Beginner Contest 389)

コンテストURL

https://atcoder.jp/contests/abc389

開催日

2025/01/20 21:00-22:40


A: 9x9

解法

  • 文字型の数字から 0 を引いて整数型に変換する
ABC389A.cpp
#include <iostream>
#include <string>
using namespace std;

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

    cout << (s[0]-'0')*(s[2]-'0') << endl;

    return 0;
}

B: tcaF

解法

  • 全探索
  • 小さいほうから順に乗算して判定する
ABC389B.cpp
#include <iostream>
using namespace std;

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

    long long int mul = 1;
    for(int i=2; ; i++){
        mul *= i;
        if(mul==x){
            cout << i << endl;
            return 0;
        }
    }
}

C: Snake Queue

解法

  • 累積和
  • 列から抜けたヘビの数を記録し、先頭にいるヘビを特定する
  • 累積和によって先頭にいるヘビからの距離を求める
ABC389C.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    int num, l, k;
    vector<long long int> V;
    int top = 0;
    V.push_back(0);
    for(int i=0; i<q; i++){
        cin >> num;
        if(num==1){
            cin >> l;
            long long int tmp = V.back();
            V.push_back(tmp+l);
        }else if(num==2){
            top++;
        }else{
            cin >> k;
            k--;
            cout << V[top+k] - V[top] << '\n';
        }
    }

    return 0;
}

D: Squares in Circle

解法

  • しゃくとり法
  • 円の対称性により、右上の \frac{1}{4} 円について、点 (i+0.5, j+0.5) と原点の距離を考える
  • i が大きくなるにつれて、 j は小さくなるため、しゃくとり法で求める
ABC389D.cpp
#include <iostream>
#include <vector>
using namespace std;

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

    vector<double> dx = {0.5, 0.5, -0.5, -0.5}, dy = {0.5, -0.5, 0.5, -0.5};
    long long int cnt = 0;
    int y = r;
    for(int i=0; i<=r; i++){
        while(((i+dx[0])*(i+dx[0])+(y+dy[0])*(y+dy[0]))>r*r && y>-1){
            y--;
        }

        if(y==-1){
            break;
        }

        cnt += y + 1;
    }

    cout << cnt*4 - (r-1)*4 - 3 << endl;
    
    return 0;
}

Discussion