競プロ日記#25/04/29

アルゴ式-トリボナッチ数列

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

vector<long long> fib;

long long func(long long n){
    
    if (fib[n] != -1){
        return fib[n];
    }else{
        fib[n] = (func(n-1) + func(n-2) + func(n-3))  % 1000000;
        return fib[n];
    }
    
}

int main() {
    long long N;
    cin >> N;
    fib.resize(N+1, -1);
    
    if (N >= 0) fib[0] = 1;
    if (N >= 1) fib[1] = 1;
    if (N >= 2) fib[2] = 1;
    cout << func(N) << endl;
}

アルゴ式-できるだけ離したい

• まあ解説読まないとわからない系

// 貪欲法により、電波塔の建てられる本数を返す関数
int build_towers(int min_dist, vector<int> &x){
    int ret = 0;
    int left_pos = -1e9;
    for (const auto pos: x) {
        if (pos - left_pos >= min_dist) {
            ret++;
            left_pos = pos;
        }
    }
    return ret;
}

int main() {
    // 入力
    int N, K;
    cin >> N >> K;
    vector<int> x(N);
    for (int i=0; i<N; ++i){
        cin >> x[i];
    }

    // 二分探索
    int left = 1;
    int right = x[N-1];
    while (right - left > 1){
        int mid = left + (right - left) / 2;

        // 距離 mid だけ離して K 本以上電波塔を建てることが、
        int num_of_towers = build_towers(mid, x);
        // 可能ならば可能である側の変数 left を更新、
        // 不可能ならば不可能である側の変数 right を更新
        (num_of_towers >= K ? left : right) = mid;
    }
    // 最終的に right - left == 1 となるため、可能なうち最大の距離が left に格納されている
    cout << left << endl;
}

アルゴ式-互除法

• シンプルに再帰で実装

int func(long long x,long long y){
    if (y == 0){
        return x;
    }
    return func(y, x % y);
}

int main() {
    long long N, M;
    cin >> N >> M;
    cout << func(N, M) << endl;
}

アルゴ式-数を選ぶ (2)

• LとRの間でいくつのN個の組み合わせを取るというだけの問題なのだがティルトしているのか全く気付かなかった。

アルゴ式-等比数列の和 (1)

• 等比数列で大きな累乗を扱ったりする際にはpow()だとオーバーフローする場合がある→powl()の方が良かったりする。

int main() {
    int N;
    cin >> N;
    long long ans = powl(2,N) - 1;
    cout << ans << endl;
}

アルゴ式-等比数列の和 (2)

• 公式にぶち込もうとしたけどオーバフローがオーバフローし過ぎててぶっ壊れた。
• 公式をそのまま分解してn乗するタイミングで都度1000000000で割った余りを求めている。

int main() {
  // 入力
  long long N, X, r;
  cin >> N >> X >> r;

  // 答えを計算する
  long long pow_r_n = 1; // r の n 乗を 1e9 で割ったあまりを求める
  for (int i=0; i<N; i++) pow_r_n = (pow_r_n * r) % MOD;
  long long ans = X * (pow_r_n - 1 + MOD) % MOD;

  // 出力
  cout << ans << endl;
}

AtCoder

ABC348_B-Farthest Point

• 馬鹿正直にユークリッド距離を求めたせいでWAした。
• 当然sqrtを使うので少数の場合などを考慮しなかったこちらが悪いのだが、そもそも距離の最大の点を求めさえすればよいことを考えると距離そのものを求める必要がなかった。
• なんかせこ臭くて萎えた。

int func(int x1, int y1,int x2, int y2) {
    return pow(x1 - x2, 2) + pow(y1 - y2, 2);
}

int main() {
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < N; i++){
        int max = -1;
        int ans = -1;
        for (int j = 0; j < N; j++){
            if (i == j){
                continue;
            }
            int temp = func(x[i], y[i], x[j], y[j]);
            if (temp > max){
                max = temp;
                ans = j;
            }
        }
        
        cout << ans + 1 << endl;
    }
}