Google Code Jam 2020 Round 1C : B. Overrandomized

あまり他のサイトで出てこなさそうな問題。
https://codingcompetitions.withgoogle.com/codejam/round/000000000019fef4/00000000003179a1

問題

数値に対し、0～9の各数字を異なるアルファベットに対応付けることを考える。
今、U桁の整数を考える。以下の処理を10000回行い、その結果を得たとする。

• 1~(10^U-1)の範囲の整数Mを等しい確率で1つ選択する。
• 1~Mの範囲の整数Vを等しい確率で1つ選択する。
• Vを前述の対応付けに応じてアルファベット表記したものを返す。

元の対応付けを求めよ。

解法

Mは9割の確率でU桁になり、Vも高確率でU桁になる。
そこで、結果のうちU文字のものに着目し、先頭の文字の頻度を取ろう。

今回の手続きでは、Vは小さい値の方が登場確率が高い。
よって、先頭の文字の頻度が高いほど、小さい値に対応づくと考えてよい。
ただし先頭に0は来ないので、頻度に応じて1～9に対応づくアルファベットが確定する。

あとは先頭以外にしか現れないアルファベットが1つあるはずなので、それを0に対応付ける。

int U;
vector<string> S;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>U;
	S.clear();
	set<int> DS;
	int C[26]={};
	FOR(i,10000) {
		string s;
		cin>>s;
		cin>>s;
		FORR(c,s) DS.insert(c);
		if(s.size()==U) {
			C[s[0]-'A']++;
		}
	}
	
	vector<pair<int,int>> V;
	FORR(c,DS) V.push_back({-C[c-'A'],c});
	sort(ALL(V));
	string T;
	T+=V.back().second;
	V.pop_back();
	FORR(v,V) T+=v.second;
	
	_P("Case #%d: %s\n",_loop,T.c_str());
}

まとめ

幸い割とすぐに方針を立てられた。