Ruby と Python で解く TOTO くじ 削減

はじめに

高橋君は、少ないお小遣いでTOTOくじを楽しもうと思っています。
高橋君が楽しいとは、１等もしくは２等が当たることです。
高橋君が楽しむために最適な戦略を取った場合、合計金額の最小値を求めなさい。

TOTOくじ

ここでは、組合せの少ないtotoGoal3で計算を進めます。

例１

一番シンプルな例は、３ダブルです。

２の３乗なので本来８通り（800円）必要ですが、２通りで楽しめます。

ruby

def check(i)
  f = false
  ['000'.to_i(2), '111'.to_i(2)].each do |x|
    f ||= true if (i ^ x).to_s(2).count('1') <= 1
  end
  ct = i.to_s(2).rjust(3, '0')
  puts f ? "#{ct} OK" : "#{ct} NG"
end

(2**3).times do |i|
  check(i)
end

python

def check(i):
    ct = format(i, 'b').rjust(3, '0')
    for x in ['000', '111']:
        f = False
        c = 0
        for i in range(len(x)):
            if ct[i] == x[i]:
                c += 1
        if c >= 2:
            f = True
            break
    if f:
        print(ct, 'OK')
    else:
        print(ct, 'NG')

for i in range(2**3):
    check(i)

# output
000 OK
001 OK
010 OK
011 OK
100 OK
101 OK
110 OK
111 OK

ここでは000と111の２通りで、２等以上（はずれが１つ以下）を確認しています。
一つの買い目で全的中とはずれ１つの４通りに対応可能ですので、８÷４＝２通りでいいわけです。
Rubyの方は、xorを使用していますが、トリプル対応などを考えますと、よろしくないかもしれないです。

応用

応用は、４ダブルです。
３ダブルはシンプルですので、簡単に求めることができましたが、４ダブルの組合せはどのように求めればいいでしょうか。

一つの買い目で５通りに対応可能ですので、（２の４乗）÷５＝３．２となり４通り以上が必要と推定されます。

しかし、ここはatcoderのコンテスト中ではないので、TLEを気にせず全検索することにします。

ruby

def check(cs)
  a = (0...2**N).to_a
  cmb = []

  a.combination(cs) do |xs|
    return cmb.size if xs.include?(0).! || cmb.empty?.!
    h = Hash.new(0)
    a.each do |i|
      f = false
      xs.each do |x|
        if (i ^ x).to_s(2).count('1') <= 1
          f = true
          h[i] += 1
          break
        end
      end
      break if f.!
    end
    if h.size == 2**N
      pt = xs.map{ _1.to_s(2).rjust(N, '0') }
      puts pt.join(', ')
      cmb << pt
    end
  end
end

N = gets.to_i
(2**N / N.next.to_f).ceil.upto(2**N) do |zz|
  break if check(zz) > 0
end

ruby

# input
3
# output
000, 111
# input
4
# output
0000, 0001, 1110, 1111
# input
5
# output
00000, 00001, 00010, 01111, 10111, 11011, 11100

５ダブルまでは、実用的な時間で答えが返ってきます。

補足

TOTOくじは2000年初頭より発売されており、削減の考え方にはそれなりの歴史があります。
例えば、６ダブルの最小値は12であることが知られており、予め計算結果をテーブルに保存しておくことにより、計算時間を縮小する手法がとられることもあります。

まとめ

• TOTOくじに詳しくなった