競プロ日記#25/04/25

アルゴ式-パスワードの可能性 (Ex)

• 未提出（提出しましょう）
• すべての位の数字が異なるという条件が漏れていた

// 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 main() {
    int N;
    cin >> N;
    cout << N * funcPermutation(9, N - 1) << endl;
}

アルゴ式-Grouping1

• 未提出（提出しましょう）
• 高校数学の重複組合せを頑張って思い出してた

// 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;
}

// nCmの組合せ(funcPermutationを使う)
long long funcCombination(int N,int M){
    return funcPermutation(N,M) / funcPermutation(M,M);
}

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

    cout << funcPermutation(N+M,N+M) / (funcPermutation(N,N) * funcPermutation(M,M)) << endl;
}

アルゴ式-巡回セールスマン問題の近似解

• 貪欲法の実装。解説を見ました。

int main() {
    // 入力
    int N;
    cin >> N;
    vector<double> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // 二頂点間の距離を求める関数
    auto calc = [&](int i, int j) -> double {
        return sqrt((X[j]-X[i]) * (X[j] - X[i]) + (Y[j] - Y[i]) * (Y[j] - Y[i]));
    };

    // 答え
    double res = 0.0;

    // used[v] ← 頂点 v をすでに訪れたか
    vector<bool> used(N, false);
    used[0] = true;

    // 前回の頂点
    int prev = 0;

    // 毎回貪欲に頂点を選んでいく
    for (int i = 0; i < N - 1; ++i) {
        // 残っている頂点で最も近いところを探す
        int nex = -1;
        double min_dis = 1000000;
        for (int j = 0; j < N; ++j) {
            // すでに訪れた頂点はスキップ
            if (used[j]) continue;
            double dis = calc(prev, j);
            if (min_dis > dis) {
                min_dis = dis;
                nex = j;
            }
        }
        
        // 新たに頂点 nex を訪れる
        used[nex] = true;
        res += min_dis;

        // 前回頂点を更新
        prev = nex;
    }

    // 最後に頂点 0 へ戻る
    res += calc(prev, 0);

    // 小数点出力
    cout << fixed << setprecision(10) << res << endl;
}

アルゴ式-グループ分け (1)

• 貪欲法あんまり得意じゃない

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

    for ( int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());

    int ans = 0;
    while(A.size()){
        ans++;
        auto it = A.begin();
        int m = *it;

        while(it != A.end()){
            if((*it) % m == 0){
                it = A.erase(it);
            }else{
                ++it;
            }
        }
    }

    cout << ans << endl;
}

アルゴ式-グループ分け (2)

• 問題の意味を正しく読み取れていなかった。
• 解説だけ読んでも実装の意図が良くわからなかったのでChatGPT先生に聞いてやっと理解した