初手の発想

ABC193_D

各数字について、すでに確定しているカードの枚数を記録して、確定していないカードについて、勝敗を全探索すればよさそう。
確定していないカードの組み合わせは高々 9 × 9 の 81 通りしかないので余裕で探索できるはず。

提出コード

提出コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool win(vector<int> S, vector<int> T){
    vector<int> count(9, 0);
    for (auto s: S) {
        count[s - 1]++;
    }
    int score_s = 0;
    for (int i = 0; i < 9; i++) {
        if (count[i] == 0) continue;
        score_s += (i + 1) * pow(10, count[i]);
    }

    vector<int> count_t(9, 0);
    for (auto t: T) {
        count_t[t - 1]++;
    }
    int score_t = 0;
    for (int i = 0; i < 9; i++) {
        if (count_t[i] == 0) continue;
        score_t += (i + 1) * pow(10, count_t[i]);
    }

    return score_s > score_t;
}


int main() {
    int K;
    string S, T;
    cin >> K;
    cin >> S >> T;

    vector <int> si, ti;
    for (auto s: S) {
        if (s == '#') break;
        si.push_back(s - '0');
    }
    for (auto t: T) {
        if (t == '#') break;
        ti.push_back(t - '0');
    }

    vector<int> tot_num(9, K);
    for (auto s: si) {
        tot_num[s - 1]--;
    }
    for (auto t: ti) {
        tot_num[t - 1]--;
    }

    double win_case = 0, lose_case = 0;
    for (int s = 1; s <= 9; s++) {
        for (int t = 1; t <= 9; t++) {
            si.push_back(s);
            ti.push_back(t);

            int num_case = 0;
            if (s == t) {
                num_case = tot_num[s - 1] * (tot_num[s - 1] - 1);
            } else {
                num_case = tot_num[s - 1] * tot_num[t - 1];
            }

            if (win(si, ti) == true) {win_case += num_case;}
            else {lose_case += num_case;}
            si.pop_back();
            ti.pop_back();
        }
    }
    double ans = win_case * 1.0L / (win_case + lose_case);

    printf("%f6\n", ans);

}

/*
6
1122#
2228#
*/

提出したのがこのコードですが、まったく突破できない。
というか、テストケースすら突破できない。 何が悪いのかコンテスト中にはわからないまま終わりましたが…

間違い

紆余曲折あったのですが、コンテスト中に最も特定まで時間を食った間違いは、pow に long long 型を突っ込んでいることでした。 ここが間違っているので、自分でプログラムをテストする時の挙動がわけわからないことになりました。

その上で修正すべき点は、

• 12, 22 行目の条件分岐は不要。 (実は、最初は要れていなかったのだが、pow の挙動が変なので入れてしまった。)
• 62, 64 行目の演算でオーバーフローを起こしている。 long long 型でないといけない。

pow の挙動には、すごく騙されました。例えば次のコードです。

このコードを手元環境で実行すると、 100 99 が出力されます。

つまり、long long 型の 10 の 2 乗が 99 として計算されています。

教訓

floor といい、long long 型を使用するときは、標準ライブラリのサポートはないものと考えてプログラムしたほうが良いのでしょうか？

疑問を感じる言語です。 この言語嫌いかもしれない。 緑コーダーの間は慣れるために c++で推し進めるつもりですが、乗換を検討しよう。 でも静的型付言語になれておきたい…

だいぶ冷えました。