競プロ日記#25/04/26

AtCoder

ABC153_A-Serval vs Monster

• 特になし

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

int main() {
    int H,A;
    cin >> H >> A;
    int ans = 0;
    while (H > 0){
        H -= A;
        ans++;
    }
    cout << ans << endl;
}

ABC153_B-Common Raccoon vs Monster

• 特になし

int main() {
    long long H,N;
    cin >> H >> N;
    long long total = 0;
    for (int i = 0; i < N; i++){
        long long a;
        cin >> a;
        total += a;
    }
    if (total >= H){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

ABC153_D-Caracal vs Monster

• Hが10^12の時点でH回のオーダーは無理→メモ化再帰でlogH回にすることはすぐに思いついた。
• しかしメモ化再帰をvectorで実装し、resizeの際にH分メモリを確保しに行ったことによってREになった。
• 以下は最初に実装したもの

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

vector<long long> memo;

long long func(long long H){
    if (memo[H] != -1) {
        return memo[H];
    }else{
        memo[H] = 2 * func(H / 2) + 1;
        return memo[H];
    }
    
}

int main() {
    long long H;
    cin >> H;
    memo.resize(H + 1, -1);
    memo[1] = 1;
    cout << func(H) << endl;  
}

• よってmapを使うことに

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

unordered_map<long long, long long> memo;

long long func(long long H){
    if (H == 1){
        return 1;
    }
    if (memo.count(H)) {
        return memo[H];
    }else{
        memo[H] = 2 * func(H / 2) + 1;
        return memo[H];
    } 
}

int main() {
    long long H;
    cin >> H;
    cout << func(H) << endl;
}

その際にH == 1の際の条件はfuncの中に詰め込んで、メモを参照する際の条件もmemo.count[H]に変更

アルゴ式-貯金 (2)

• 初項1公差1の等差数列の和であるということに着目すればそれを求める関数を実装してあとは単純な二分探索に帰着できる。このアイデアが足りていなかった。

// f(x) を求める関数
long long f(long long x) {
  return x*(x+1)/2;
}

アルゴ式-ひもを切る

• 問題の意図があまり適切に汲み取れていなかった
• 二分探索に帰着させる前の段階で詰まっている

// f(x) を求める関数
int f(double x, vector<double> L) {
  double ans = 0;
  for (double l: L) {
    ans += (int)(l/x);
  }
  return ans;
}

int main() {
  int N, K; cin >> N >> K;
  vector<double> L(N);
  for (int i=0; i<N; i++) cin >> L[i];

  // 二分探索
  double left = 0, right = 2e5;
  while (right-left>1e-8) { // 精度が十分良くなるまで
    // left と right の 中点 mid をとる
    double mid = (left+right)/2;
    if (f(mid,L)>=K) { // もし f(mid,L)>=K ならば答えは mid 以上 right 以下
      left = mid; // 範囲を狭める
    }
    else { // そうでなければ答えは left 以上 mid 未満
      right = mid; // 範囲を狭める
    }
  }

  // 答えは left 以上 right 以下であることがわかっている。
  // 精度は十分なので、ここでは left の値を出力する。
  double ans = left;
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}

アルゴ式-タスクリスト (Hard)

• むずすぎる。GPT先生案件。先生に解説してもらってもイマイチ理解しきれなかった。要復習

int main() {
    int X, Q;
    cin >> X >> Q;

    vector<int> finish_times;
    vector<pair<int, int>> queries;

    // 入力を一度全部読み込む
    for (int i = 0; i < Q; ++i) {
        int type, t;
        cin >> type >> t;
        if (type == 0) {
            finish_times.push_back(t + X);
        } else {
            queries.emplace_back(i, t);  // クエリ番号と時刻
        }
    }

    // 完了時刻をソート（upper_boundのため）
    sort(finish_times.begin(), finish_times.end());

    int idx = 0; // finish_times を順に探索するインデックス
    for (auto [_, t] : queries) {
        // t 以下の完了時刻の個数を数える
        int count = upper_bound(finish_times.begin(), finish_times.end(), t) - finish_times.begin();
        cout << count << endl;
    }

    return 0;
}

アルゴ式-半分にして行く

• heapを使わないと基本的には間に合わなそう。vectorを使ってソートすることを考えたが無理そう。

int main() {
    int N, K; cin >> N >> K;
    priority_queue<int> pq; // 現在の数列の状態を管理し、最大値を取り出すヒープ
    vector<int> A(N);
    for(int i = 0; i < N; ++i) {
        int a; cin >> a;
        A[i] = a;
        // ヒープに数列内の整数を挿入する
        pq.emplace(a);
    }

    // 最大値を取り出しその半分を挿入しなおす、という操作を K 回繰り返す
    for(int k = 0; k < K; ++k) {
        // 現在の数列における最大値を M とする
        int M = pq.top();
        pq.pop();
        // M を 2 で割った商をヒープに挿入する 
        pq.emplace(M / 2);
    }

    long long ans = 0;  // 答えとなる変数
    // ヒープ内の全ての要素を足し合わせる
    while(pq.size() > 0) {
        int a = pq.top();
        pq.pop();
        ans += a;
    }
    cout << ans << endl;

	return 0;
}

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

• Mこの箱で分ける→M-1のついたてで重複組合せ

// 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 - 1,N+M - 1) / (funcPermutation(N,N) * funcPermutation(M - 1,M - 1)) << endl;

}

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

• 各箱に最初から1個ずつ置いておくという話。→ForcusGoldマジでやりなおそうかな