競プロ日記#25/04/16

AtCoder

ABC156_B-Digits

• 記数法の問題。カウンタを持たせたwhileでpow(N,カウンタ)をしたのだが微妙に答えが合わなかった。
• 解説によるとNが0になるまでNをKで割った時の商で置き換える

int main() {
    int N,K;
    cin >> N >> K;

    int ans = 0;
    int total = 0;
    
    while(N > 0){
        N /= K;
        ans++;
    }
    cout << ans << endl;
}

ABC156_C-Rally

• X1~XNの間から探すために昇順でソートしてその間からPを探す。
• 今回はあくまで最小値を探すのでmin変数に対して0で初期化すると0が常に答えになってしまうことに気を付ける（INT_MAXを使った）
• あとはN == 1やN > 1だけどXが全て同じ値の時は上手くfor文を回せなくて詰むので例外パターンとして列挙するのを忘れない。

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

    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    
    int min = INT_MAX;
    sort(A.begin(), A.end());
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }
    if (A[0] == A[N - 1]) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = A[0]; i < A[N - 1]; i++) {
        int sum = 0;
        for (int j = 0; j < N; j++) {
            
            sum += (i - A[j]) * (i - A[j]); 
            
        }
        if (min > sum){
            min = sum;
        }
    
    }

    cout << min << endl;
        
}

アルゴ式-ボールと箱 (2)

• 階乗を実装すればいい。
• 階乗も含めた順列の関数を実装。

// nPmの順列(階乗や0!にも対応)
long long funcPermutation(int N,int M){
    if (N == 0 & M == 0){
        return 1;
    }
    long long ans = 1;
    for (int i = 0;i < M;i++){
        
        ans = ans * (N - i);
        
    }
    return ans;
}

アルゴ式-駅と駅の距離

• 累積和の応用

int N;
cin >> N;
vector<int> d(N-1)
for (int = 0;i < N - 1;i++){
    cin >> d[i];
}

int Q;
cin >> Q;

vector<int> acc(N);
for (int i=0; i<N-1; ++i) {
    acc[i+1] = acc[i] + d[i];
}
for (int i=0; i<Q; ++i) {
    int l, r;
    cin >> l >> r;
    int result = acc[r] - acc[l];
    cout << result << endl;
}