競プロ日記#25/04/20

AtCoder

ABC116_A-Right Triangle

• 最初はヘロンの公式でも使うのかと思ったがよくよく見たら直角三角形だった。

int main() {
    int AB,BC,CA;
    cin >> AB >> BC >> CA;
    int ans = 0;
    ans = AB * BC / 2;

    cout << ans << endl;
}

ABC116_B-Collatz Problem

• 問題設定がちょっとややこしかったが実装自体は簡単

int main() {
    int s;
    cin >> s;
    set<int> st;
    int counter = 0;
    while(true){
        int tmp = st.size();
        if (counter == 0) {
            st.insert(s);
        }
        if (s % 2 == 0) {
            s /= 2;
            st.insert(s);
        } else {
            s = 3 * s + 1;
            st.insert(s);
        }
        counter++;
        if (tmp == static_cast<int>(st.size())) {
            cout << counter + 1 << endl;
            break;
        }
        
    }
}

ABC149_A - Strings

• 特になし

int main() {
    string S,T;
    cin >> S >> T;
    cout << T << S << endl;
}

ABC149_B - Greedy Takahashi

• B問題だからと全探索でやろうとしたらアウトだった。ちゃんと考えましょう

int main() {
    long long A,B,K;
    cin >> A >> B >> K;
    if (K <= A){
        cout << A - K << " " << B << endl;
    } else if (K <= A + B) {
        cout << 0 << " " << B - (K - A) << endl;
    } else {
        cout << 0 << " " << 0 << endl;
    }
}

ABC149_C-Next Prime

• 以前実装した素数判定関数を使ってワンパン

bool isprime(int N) {
    if (N < 2) return false;
    for (int i = 2; i < N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

AGC027_A-Candy Distribution Again

• 昇順でソートした上で貪欲法で余裕だったがiがN-1、つまり最後のforループの際にちょうど配り切れるかどうかの判定が必要

int main() {
    int N,x;
    cin >> N >> x;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    int ans = 0;
    
    for  (int i = 0; i < N; i++) {
        if (i  ==  N  -  1){
            if (A[i] == x){
                ans++;
                break;
            }else{
                break;
            }
        }
        if (A[i] <= x) {
            x -= A[i];
            ans++;
        } else {
            break;
        }
    }
    cout << ans << endl;
}

アルゴ式-ひもの本数

• 十分に大きい要素数を持ったcount配列を用意してその中にひもの長さN種類分の有無をセットする
• なのでfor文はあくまでもN回でcinしたLに対してL番目のcount用をインクリメントするだけ（ちなみにインクリメントにしているので同じ長さのひもが複数ある場合にも対応できる）

const int MAX_LEN = 100001;
vector<int> count(MAX_LEN, 0);


for (int i = 0; i < N; ++i) {
    int x;
    cin >> x;
    count[x]++;
}

• その後はよくある累積和の問題に帰着

vector<int> R(MAX_LEN);
for (int i = 1;i < MAX_LEN;i++){
    R[i] = R[i - 1] + count[i];
}

int Q;
cin >> Q;
for (int i = 0;i < Q;i++){
    int A,B;
    cin >> A >> B;
    if (A > 0){
        cout << R[B] - R[A - 1] << endl;
    }else{
        cout << R[B] << endl;
    }
}

アルゴ式-最小の添字

• 二分探索を配列に応用。そんなに難しくないないのだがまだまだ二分探索の典型的な実装に不安がある。

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

    for (int i = 0;i < M;i++){
        int left = 0;
        int right = N - 1;
            while (left != right){
                int mid = (left + right) / 2;
                if (A[mid] < B[i]){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
        cout << left << endl;
    }
}