練習（SRMs 1 144 DIV 1 550)

問題を読む為の英単語

単語	意味
gamblers	ギャンブラー
variety	多様な
wide variety	種類が豊富
lottery	運、くじ
represent	代表する
inclusive	すべてを含んだ
appear	出現する
indicate	指し示す
restriction	制限
descending	降下的な
order	順序
likewise	同様に
distinct	別個の
corresponding	一致する、対応する
probability	起こりそうな、見込み
alphabetically	順に
Tie	ひきわけ
unconditionally	条件に従っていない
odds	確率
eliminate	除去する
additional	追加の

問題概要

与えられるくじ(ticket)で、最も勝つ確率の高い順に並び替える問題。
入力：5つの要素からなるチケットが0~50枚
5つの要素とは、
Name, choices, blanks, sorted, uniqueである。
Nameはチケットの名前である。
choicesは、10~100までの数値で、そのくじが取りうる値の範囲を示す。
blanksは、1~8までの数値で、そのくじの値の個数を示す。
(つまり、チケットは、choicesの中の数値から、blanks個選んだ数値で構成される)
sortedは、bool値を持ち、当たりくじの条件の一つである、
「くじがソートされている必要があるか」を示す。
(Tである場合、チケットの数値は、ソートされていなければならない,
Fである場合はソートの状態は問わない)
uniqueは、sortedと同様にbool値をもち、「くじの数値がユニーク(重複がない)である必要があるか」を示す。
(Tである場合は、チケットの数値はすべてユニークでなければならない、、
Fである場合は、ユニークであるかは問わない)

以上のチケットにおいて、確率(1/そのゲームでチケットが取りうる数値の組み合わせ)を計算し
確率の高い順に並べる。確率が同じである場合は、名前のアルファベット順に並べること。

例示

{"PICK ANY TWO: 10 2 F F"
,"PICK TWO IN ORDER: 10 2 T F"
,"PICK TWO DIFFERENT: 10 2 F T"
,"PICK TWO LIMITED: 10 2 T T"}

PICK ANY TWO は10個の数字から2つ選び、ソート、ユニーク条件を問わないため、
すべての組み合わせが有効である。
よって、確率 = (1/ 10*10) = ( 1 / 100)となる。

PICK TWO IN ORDER は、ソートの条件をもつ。
ソートは先頭が「１０」であれば、二つ目は「１〜１０」が有効。
先頭が「９」であれば、二つ目は「１〜９」が有効。
以下繰り返し。。。により、
確率 = ( 1/ 10+9+8+....+3+2+1) = 1/55となる。

PICK TWO DIFFERENTは、ユニークの条件をもつ。
「１・１」、「２・２」、...、「10・10」は無効であるため、残りの条件を考慮し、
確率 = ( 1 / (100-10)) = ( 1 / 90 )となる。

PICK TWO LIMITED は、両方の条件をもつ。
故に、OREDER とDIFFERENT無効条件の差になるため、
確率 = (1 / (55 - 10 )) = 1/45となる。

結果を確率の高いものからソートし、
{ "PICK TWO LIMITED",
"PICK TWO IN ORDER",
"PICK TWO DIFFERENT",
"PICK ANY TWO" }
を出力すれば良い。

問題の解き方

ソート、ユニークの各々の場合で起こりうる組み合わせの数を計算し、
確率を計算することとする。

以下に、一般解を示す。(choiseをn, blanksをmとする）
1. ソート条件無し・ユニーク条件無しの場合
重複を許し、他に制約がないため、重複を含んだ順列の式で求めることができる。
\[組み合わせ数 = n^m \]

2. ソート条件有り・ユニーク条件無しの場合
本項目が一番難しい。あまり自信が無いが以下の通り。
▶︎下記内容は間違い。重複組み合わせの公式を使えば解けます。

まず、単純に重複が無く、ソートされた組み合わせ数は以下のとおり、
\[重複無し組み合わせ = _n\mathrm{C}_m \]
重複無かつ順番を意識せず得られた組み合わせでは、
重複無し組み合わせの数と等しい
※順番を意識しないとは、(1,2,3)も(1,3,2)も(3,2,1)も同じとカウント
また、その中でソート順のものはただ一つ。

次に、重複分を算出する。
重複には、数値がすべてが重複している場合と、部分重複の２つのパターンが存在する。
数値がすべて重複している場合は単純に、
\[すべて重複組み合わせ = _n\mathrm{C}_1 \]
である。
部分重複は、重複可能箇所に注目する。
例えば、４つの数字があり２つの数字が重複した場合、重複可能な場所は以下の３つである。
{ A, A, B, C }, { A, B, B, C}, { A, B, C ,C }
３つの数字が重複した場合は、以下の２つ。
{A, A, A, B}, { A, B, B, B}

ここから重複部分を一つの数字と考えて組み合わせを得ることを考える。
つまり、{A, A, B, C}は、{A, B, C}の組み合わせを得ると同等ということになる。
ただし、m個の数字からk個値が重複する場合の、重複可能箇所は k + 1種ある。

以上より、部分重複およびすべてが重複をひとまとめにし、以下の式が得られる。

重複組み合わせ

最後に重複無しと重複ありを合計し、
組み合わせ数

となる。

3.ソート条件無し、ユニーク条件有りの場合
重複を含む組み合わせを除外すれば良いので、
順序関係あり、組み合わせの式から得られる。
\[組み合わせ = _n\mathrm{P}_m \]

4.ソート条件有り、ユニーク条件有り
本項目は、2.ですでに得られているため、問題無し。
\[組み合わせ = _n\mathrm{C}_m \]

以上で、各々得られた組み合わせの逆数が大きい順にソートする。

解答コード

using System;



namespace Application
{
	class Lottery
	{
		const int NAME = 0;
		const int CHOICES = 1;
		const int BLANKS = 2;
		const int SORTED = 3;
		const int UNIQUE = 4;

		const int IT_CHOICES = 0;
		const int IT_BLANKS = 1;

		public String[] sortByOdds(String[] rules){
			string[,] st_rules = new string[rules.Length, 5];
			long[] ans = new long[rules.Length]; //確率
			string[] nameAns = new string[rules.Length];

			// 入力の分割
			for (int i = 0; i < rules.Length; i++) {
				string[] st_tmp = rules [i].Split (':');
				st_rules [i, 0] = st_tmp [0];	// Name を格納
				nameAns [i] = st_tmp [0];	//解答用

				for (int j = 1; j < 5; j++) {
					string[] st_tmp2 = st_tmp [1].Split (' ');
					st_rules [i, j] = st_tmp2 [j];
				}
			}

			// 整数変換
			int[,] it_rules = new int[rules.Length, 2];
			for (int i = 0; i < rules.Length; i++) {
				it_rules [i, IT_CHOICES] = int.Parse (st_rules [i, CHOICES]);
				it_rules [i, IT_BLANKS] = int.Parse (st_rules [i, BLANKS]);
			}

			//確率算出
			for (int cnt = 0; cnt < rules.Length; cnt++) {
				//SORTED == F && UNIQUE == F
				if (st_rules [cnt, SORTED] == "F" && st_rules [cnt, UNIQUE] == "F") {
					//CHOICES^BLANKS
					long l_tmp = 1;
					for (int i = 0; i < it_rules [cnt, IT_BLANKS]; i++) {
						l_tmp = l_tmp * it_rules [cnt, IT_CHOICES];
					}
					ans [cnt] = l_tmp;
				}
				//SORTED == T && UNIQUE == F
				else if (st_rules [cnt, SORTED] == "T" && st_rules [cnt, UNIQUE] == "F") {

					ans[cnt] = Combination(it_rules[cnt, IT_CHOICES]+it_rules[cnt, IT_BLANKS]-1,it_rules[cnt, IT_BLANKS]);
					/*	ans [cnt] = Combination (it_rules [cnt, IT_CHOICES], it_rules [cnt, IT_BLANKS]);

					for (int i = 1; i < it_rules [cnt, IT_BLANKS]; i++) {
						ans [cnt] = ans [cnt] + (i * Combination (it_rules [cnt, IT_CHOICES], i));
					}
					*/
				}
				//SORTED == F && UNIQUE == T
				else if (st_rules [cnt, SORTED] == "F" && st_rules [cnt, UNIQUE] == "T") {
					ans [cnt] = Permutation (it_rules [cnt, IT_CHOICES], it_rules [cnt, IT_BLANKS]);
				}
				//SORTED == T && UNIQUE == T
				else {
					ans [cnt] = Combination (it_rules [cnt, IT_CHOICES], it_rules [cnt, IT_BLANKS]);
				}
			}


			//ソート(数値ソート)
			for (int i = 0; i < rules.Length; i++) {
				for (int j = rules.Length-1; j > i; j--) {
					if (ans [j - 1] > ans [j]) {
						//値交換
						long tmp = ans [j - 1];
						ans [j - 1] = ans [j];
						ans [j] = tmp;
						//String交換
						string s_tmp = nameAns [j - 1];
						nameAns [j - 1] = nameAns [j];
						nameAns [j] = s_tmp;
					}
				}
			}
			//ソート(アルファベットソート)
			for (int i = 0; i < rules.Length; i++) {
				for (int j = rules.Length-1; j > i; j--) {
					if (ans [j - 1] == ans [j]) {
						if (nameAns [j - 1].CompareTo(nameAns [j]) > 0) {
							//値交換
							long tmp = ans [j - 1];
							ans [j - 1] = ans [j];
							ans [j] = tmp;
							//String交換
							string s_tmp = nameAns [j - 1];
							nameAns [j - 1] = nameAns [j];
							nameAns [j] = s_tmp;
						}
					}
				}
			}


			for (int i = 0; i < rules.Length; i++) {
				System.Console.WriteLine("ans[" + i + "]=");
				System.Console.WriteLine (ans [i]);
				System.Console.WriteLine ("nameAns[" + i + "]=");
				System.Console.WriteLine (nameAns [i]);
			}


			return nameAns;
		}

		//mCnを返す
		public long Combination(int m, int n){
			long child = Factorial(m, m-n);
			long mum = Factorial(n,0);

			return child / mum;
		}

		//mPnを返す
		public long Permutation(int m, int n){
			long child = Factorial(m, m-n);
			long mum = 1;

			return child / mum;
		}

		//m!を返す
		public long Factorial(long m, long limit){

			long ret = 1;

			if (m < 1 || m <= limit) {
				return ret;
			} else {
				ret = m * Factorial (m - 1, limit);
			}
			return ret;
		}
	}


	class MainClass
	{
		public static void Main (string[] args)
		{
			Lottery lot = new Lottery();

			string[] test = new string[7] {"INDIGO: 93 8 T F",
				"ORANGE: 5 4 T F",
				"VIOLET: 76 6 F F",
				"BLUE: 100 8 T T",
				"RED: 99 8 T T",
				"GREEN: 78 6 F T",
				"YELLOW: 75 6 F F"
			};

			lot.sortByOdds (test);

		}
	}
}

気づいたこと

ソートあり　かつ　ユニーク無し　条件は
「重複組み合わせ」の公式を使えばあっさりと解くことができた。
ちなみに、上に書いたやつは間違っていました。
(重複組み合わせが不足しています。。。)
\[ _n \mathrm{H} _r = _{n+r-1} \mathrm{C} _ r \]
が公式でした。

勉強不足です。