【競プロ精進ログ】【2021/03/26】ABC193: D

競技プログラミングのための精進履歴をブログ形式で残していきます。

目標は AtCoder 水色！
今のレートは茶色です。

本日の精進ツリーは以下のとおり。

精進ツリー

ABC193: D – Poker
まとめ

ABC193: D – Poker

ABC193 より、ABC193: D – Pokerを解きました。
難易度は緑色。

正直強敵でした。
全然実装通らない…。

C++ の言語仕様に結構苦しめられました。
string型の中の数字を一つ抜き出して数値に変換するとき、atoi()だとなぜかうまく行かなかったので、独自の変換関数を使いました。

また、ロジックがわかっても全然 AC できなかったのですが、どうやら余計な除算が発生していたことによる誤差が原因だったようです。
浮動小数点が絡むときは極力除算はしないコードを意識していきたい。

提出コードはこちら。

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))
using namespace std;

#define MAX 100010
#define NIL -1

using lint = long long int;
using P = pair<lint, lint>;

bool check(vector<lint> Tb, vector<lint> Ab)
{
    lint ret = 0;
    lint t = 0;
    lint a = 0;

    for (int i = 1; i < 10; i++)
    {
        t += i * pow(10, Tb[i]);
        a += i * pow(10, Ab[i]);
    }

    if (t > a) return true;
    else return false;
}

int ctoi(char c) {
	switch (c) {
		case '0': return 0;
		case '1': return 1;
		case '2': return 2;
		case '3': return 3;
		case '4': return 4;
		case '5': return 5;
		case '6': return 6;
		case '7': return 7;
		case '8': return 8;
		case '9': return 9;
		default: return 0;
	}
}

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

    vector<lint> cards(11, 0);
    for (int i = 1; i < 10; i++)
    {
        cards[i] += K;
    }

    vector<lint> Tb(11, 0);
    vector<lint> Ab(11, 0);
    for (int i = 0; i < 4; i++)
    {
        Tb[ctoi(T[i])]++;
        Ab[ctoi(A[i])]++;
        cards[ctoi(T[i])]--;
        cards[ctoi(A[i])]--;
    }

    double total = (9*K - 8)*(9*K - 9);
    lint ans = 0;
    for (int i = 1; i < 10; i++)
    {
        if (cards[i] > 0)
        {
            Tb[i]++;
            cards[i]--;
            for (int j = 1; j < 10; j++)
            {
                if (cards[j] > 0)
                {
                    Ab[j]++;
                    if (check(Tb, Ab))
                    {
                        if (i == j)
                        {
                            ans += (cards[i] + 1) * (cards[i]);
                        }
                        else
                        {
                            ans += (cards[i] + 1) * (cards[j]);
                        }
                    }
                    Ab[j]--;
                }
            }
            Tb[i]--;
            cards[i]++;
        }
    }
    double ret = (double)ans / (double)total;
    cout << setprecision(9) << ret << endl;
    return 0;
}