AtCoder Beginner Contest 254

A - Last Two Digits

O(1)
１文字目と２文字目を表示します。

C++

#include <bits/stdc++.h>

int main() {
    string N;
    cin >> N;
    cout << N.substr(1,2) << endl;
    return 0;
} 

B - Practical Computing

O(N*N/2)
問題文の制約通りにコーディングできるかを問われています。

C++

#include <bits/stdc++.h>

int main() {
    int N;
    cin >> N;
    vector<vector<int>> A(N);

    for(int i=0; i<N; i++){
        for(int j=0; j<i+1; j++){
            if(j==0 || j==i) A[i].push_back(1);
            else A[i].push_back(A[i-1][j-1]+A[i-1][j]);
        }
    }

    for(int i=0; i<N; i++){
        for(int j=0; j<i+1; j++){
            cout << A[i][j];
            if(j<i) cout << ' ';
        }
        cout << endl;
    }

    return 0;
} 

C - K Swap

O(N)
i番目と、i+K番目を入れ替えることができます。
入れ替え可能な回数は0回以上です。
まずテストデータを作成します。

10 3
6 1 1 3 1 1 2 1 1 1

のテストデータの時、i=0からi=N-1まで、各要素を１回だけ昇順に入れ替えをします。

10 3
3 1 1 2 1 1 1 1 1 6

この結果から、i番目と、i+K番目を入れ替えを行う際、
昇順になるまで無制限にソートを行う必要があると分かります。
また、i番目からi+K*j番目の要素のみ入れ替えています。

つまり、i番目からi+K*j番目の要素のみの集合を作成し、
昇順にソートを行なったものを、
Aの要素に順番通りに代入すると解答になります。

C++

#include <bits/stdc++.h>

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    vector<int> f(N, 0);
    for(auto &a:A) cin >> a;

    for(int i=0; i<N-K; i++){
        if(f[i] == 1) continue;

        multiset<int> st;
        for(int j=i; j<N; j+=K){
            st.insert(A[j]);
            f[j] = 1;
        }

        auto itr = st.begin();
        for(int j=i; j<N; j+=K){
            A[j] = *itr;
            itr++;
        }
    }

    int ok=1;
    for(int i=0; i<N-1; i++){
        if(A[i]>A[i+1]) ok = 0;
    }
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
} 

D - Together Square

O(N√N)
AtCoder math Contestです。
N以下のi,jを使用して、i*jの平方数がいくつあるか組み合わせの数を求める問題です。

O(N＾２)では、TLEになります。
O(NlogN)、O(N√N)、O(N)にする方法を考えます。

iを固定した時、jがとる値を計算しましょう。
iから、約数の組み合わせて２乗になっている物を取り除きます。

2*2*2*2*3*5

3*5=15として、15に平方数をかけてN以下の数字が、
jのとる値になります。

C++

#include <bits/stdc++.h>

int main() {
    ll N;
    cin >> N;
    vector<int> A;
    //  N以下の平方数を全て計算する
    for(int i=1; i*i<=N; i++){
        A.push_back(i*i);
    }

    ll ans = 0;
    // iを固定した時、jがとる値を計算する
    for(int i=1; i<=N; i++){
        ll t = i;
        // N以下の平方数でiを割る。
        // 大きい平方数から割らないと余りが出る。
        for(auto itr = A.rbegin(); (*itr) != 1; itr++){
            while(t%(*itr)==0) t /= *itr;
        }
        // 残った約数と、N以下の平方数をかけて、
        // N以下なら組み合わせの一つであると判定できる。
        for(auto itr = A.begin(); t * (*itr)<=N && itr != A.end(); itr++){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}