◆ わからない問題はここに書いてね 226 ◆
■ このスレッドは過去ログ倉庫に格納されています
0227132人目の素数さん
2007/08/21(火) 22:35:09各種類の全カードにおける割合に対して,既に並べられたカードにおける
割合が最も不足しているカードを並べていけばいいのではないか?
例えば 3 種類で説明する.A,B,C の 3 種類のカードがそれぞれ a,b,c 枚
あったとして,a + b + c = N とする.a≧b≧c としてよい.
A, B, C の割合はそれぞれ a/N,b/N,c/N …(1)
既に n 枚並べ終わったとき,A,B,C がそれぞれ s,t,u 枚 (s + t + u = n)
並べられたとすると,並べられたカードにおけるそれぞれの割合は
s/n,t/n,u/n だから,(1) とこれとの差は
a/N - s/n, b/N - t/n, c/N - u/n
このうち最大なものに対応するカードを n+1 枚目に並べることにする.
最初だけやってみる.まずは最も枚数の多い A を並べる.
既に並んでいるカードにおける割合は 1,0,0
(1) との差は a/N - 1,b/N,c/N で,このうち最大なのは b/N
なぜなら,a/N - 1 < 0 だし,b/N ≧ c/N だから.
よって 2 枚目は B を並べる.
この時点で,既に並んでいるカードの割合は 1/2,1/2,0
(1) との差は a/N - 1/2,b/N - 1/2,c/N で,このうち最大なものに
対応するカードを次に並べる.
以下同様.
■ このスレッドは過去ログ倉庫に格納されています