hotaruの蛍雪日記

競プロとゲームをしています

キャディコン2021(ABC193)に参加した

キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193) - AtCoder https://atcoder.jp/contests/abc193?lang=ja

53分でABCDの4完。 Cは典型問題・Dはやるだけ実装面倒。

machikaneさんのキャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)での成績:1256位 パフォーマンス:1380相当 レーティング:1200→1219 (+19) :) #AtCoder #キャディプログラミングコンテスト2021(ABC193) https://atcoder.jp/users/machikane/history/share/abc193?lang=ja

まあ通すべきD問題を通せたから及第点だろう。 ABCD問題を35分で解いて青パフォ取りたかった。

A - Discount

やるだけ。 整数同士を浮動小数点数として演算したいならば、キャストする。 これを忘れないようにしよう。

const long double ans = (1 - (long double)b / a) * 100;

B - Play Snuke

やるだけですね。

  1. 各店について処理する
  2. スヌケマシンが売りきれずに買えるか調べる
    1. $A_i > X_i$なら買える
  3. スヌケマシンが買えるなら最小金額を更新する
  4. 最小金額を出力する

code

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
constexpr int INF = 1000000000 + 8;
#define int long long

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;
    vector<int> a(n), p(n), x(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> p[i] >> x[i];

    int ans = INF;

    // それぞれの店で買ったときの値段を調べる
    for (int i = 0; i < n; i++) {
        // 店に着くまでに売り切れるなら値段は調べない
        if (!(a[i] < x[i])) continue;

        // 最小の値段を更新
        ans = min(p[i], ans);
    }

    cout << (ans != INF ? ans : -1) << "\n";
}

C - Unexpressed

「2以上の整数$a,b$を用いて$ab$と表せる数」はあんまりたくさんないと思う。 表せるものをすべて数えたらよさそう。

  1. $a$を2から大きくしていく
  2. $ab$を数える ここで$a2$を既に数えていたら飛ばす
  3. $a2 \leq N$ならばもう数える数は無いので打ち切る

打ち切らないと$O(N)$になりTLEする。

code

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// AとBの乗算がオーバーフローするか返す
template <typename T>
constexpr bool isProdOverflow(T a, T b) {
    if (b == 0) return false;
    return a > numeric_limits<T>::max() / b;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n;
    cin >> n;

    // $a^b$で表せる値の数
    int expressed = 0;

    // もう出た値
    set<int> pop;

    // aをそれぞれ調べる
    for (int a = 2; a <= n; a++) {
        // もう数える値が無いので計算を打ち切るかどうか
        bool cancel = false;

        long long x = a;
        for (int b = 2; b <= n; b++) {
            // オーバーフローするなら打ち切る
            // a^bがnを超えるなら打ち切る
            if (isProdOverflow(x, a) || x * a > n) {
                // a^2がnより大きいなら、aを増やしても表せるようにはならない 計算を打ち切る
                cancel = b == 2;
                break;
            }
            x *= a;
            // もう出た値なら打ち切る
            if (pop.count(x)) break;

            // xを数える
            expressed++;
            pop.insert(x);
        }
        if (cancel) break;
    }

    // $a^b$で表せない値の数
    const int ans = n - expressed;
    cout << ans << "\n";
}

D - Poker

引くカードを全探索したら計算量$O(K2)$でTLEする。 引くカードの数字を全探索したら計算量が小さくなる。

  1. 高橋が引く数と青木が引く数を全探索する
  2. 引くカードの組に対してその勝敗を計算する
  3. 引くカードの組に対してその事象数を計算する
  4. 高橋が勝つ事象数を計算する
  5. 確率を計算する

code

#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long

// $a^r$ 整数演算する
constexpr long long powi(long long a, long long r) {
    int ans = 1;
    for (int i = 0; i < r; i++) {
        ans *= a;
    }
    return ans;
}

// 文字列sに登場する数字を数えて配列に入れる
array<int, 10> countNumber(string s) {
    array<int, 10> hand{};
    for (auto &&i : s) {
        if ('0' <= i && i <= '9') {
            hand[i - '0']++;
        }
    }

    return hand;
}

// 得点を計算する
int getScore(array<int, 10> hand) {
    int score = 0;
    for (int i = 0; i < 10; i++) {
        score += i * powi(10, hand[i]);
    }
    return score;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(16);

    int k;
    cin >> k;
    string s, t;
    cin >> s >> t;

    // 4枚目までの手札の数字を配列にいれる
    const auto taka4 = countNumber(s), aoki4 = countNumber(t);

    // 高橋が引く数と青木が引く数を全探索する
    // 引くカードの組に対してその勝敗を計算する
    // 引くカードの組に対してその事象数を計算する
    // 高橋が勝つ事象数を計算する
    // 確率を計算する

    // 高橋が勝つ引くカードの組を調べておく
    // win_condition[i][j]: 高橋,青木のカードがi,jのとき高橋が勝てるか
    array<array<bool, 10>, 10> win_condition{};
    // 高橋がi、青木がjを引く
    for (int i = 1; i < 10; i++) {
        // 高橋の手札
        auto taka = taka4;
        taka[i]++;
        for (int j = 1; j < 10; j++) {
            // 青木の手札
            auto aoki = aoki4;
            aoki[j]++;

            // 得点
            const int taka_score = getScore(taka), aoki_score = getScore(aoki);

            win_condition[i][j] = taka_score > aoki_score;
        }
    }

    // iのカードが山札と5枚目のカードに何枚あるか調べておく
    // deck[i]: iのカードが山札と5枚目のカードに何枚あるか
    array<int, 10> deck{};
    for (int i = 0; i < 10; i++) {
        deck[i] = k - taka4[i] - aoki4[i];
    }

    // 全事象・高橋が勝つ事象
    int all_events = 0, win_events = 0;

    // 高橋がi、青木がjを引く
    for (int i = 1; i < 10; i++) {
        for (int j = 1; j < 10; j++) {
            // 引いたカードの組がありえない組み合わせなら処理を飛ばす
            if (deck[i] == 0 && deck[j] == 0) continue;
            if (i == j && deck[i] <= 1) continue;

            // 引いたカードの組がこうなる事象
            int events = deck[i] * deck[j];
            if (i == j) events = deck[i] * (deck[i] - 1);

            all_events += events;
            if (win_condition[i][j]) win_events += events;
        }
    }

    // 事象数から確率を計算する
    const long double ans = (long double)win_events / all_events;
    cout << ans << "\n";
}

コーディング環境改善

整数べき乗

整数のべき乗を整数型として計算するスニペットを登録した。

// 整数のべき乗を整数型として計算する
// b: 底
// e: べき指数
constexpr long long powi(long long b, int e) {
    long long ans = 1;
    for (int i = 0; i < e; i++) ans *= b;
    return ans;
}

スニペットの登録はsnippet generator使うと楽です。

入力受け取りスニペットを修正

次が今まで使っていた変数入力スニペット。 変数型→変数名を入力する。

    "inputval": {
        "body": [
            "${1:int} ${2:n};",
            "cin >> $2;",
            "$0"
        ],
        "description": "inputval",
        "prefix": "inputval"
    },
    "inputvals2": {
        "body": [
            "${1:int} ${2:n}, ${3:m};",
            "cin >> $2 >> $3;",
            "$0"
        ],
        "description": "inputvals2",
        "prefix": "inputvals2"
    },

変数型は九分九厘int型だから型を指定しないように修正した。

    "inputint": {
        "body": [
            "int ${1:n};",
            "cin >> $1;",
            "$0"
        ],
        "description": "inputint",
        "prefix": "inputint"
    },
    "inputints2": {
        "body": [
            "int ${2:n}, ${3:m};",
            "cin >> $2 >> $3;",
            "$0"
        ],
        "description": "inputints2",
        "prefix": "inputints2"
    },