マルエツのレシート応募キャンペーンの最大口数を知りたい

プログラミング

スーパーのマルエツのキャンペーンでは、レシート３０００円で１口応募できる。（レシート合算可） https://www.ichance.jp/cp/maruetsu-dreamwinter/

たとえば

以下のレシートがあった場合は

  • 600
  • 1000
  • 2000
  • 2500

以下のようにまとめることで「２口応募」できる。

  • 1口目 600, 2500
  • 2口目 1000, 2000

以下のレシートがあった場合はどうだろう。

  • 1676
  • 843
  • 1000
  • 233
  • 1731
  • 321
  • 179
  • 259
  • 460
  • 1594
  • 3544
  • 632
  • 2172
  • 2623
  • 1102
  • 84
  • 466
  • 306
  • 855
  • 3255
  • 1609
  • 1345
  • 1170
  • 4220
  • 6231
  • 180
  • 91
  • 2937
  • 544
  • 1577
  • 421
  • 3899
  • 585
  • 671
  • 1811
  • 875
  • 384
  • 950
  • 1618

これは、パッとわからない。
パッとわからないので、テキトーに組み合わせて出来た結果が「１０口」だとする。
もうすこし組み合わせを頑張れば「１１口」や「１２口」になったりするかもしれない。
しかし、テキトーに手作業だとだいぶ疲れるし、無意味なような気がするので、以下のアルゴリズムを考えた。

アルゴリズム

計算1

  1. レシートから１枚ランダムに選んで、テーブルに置く
  2. テーブルの上にあるレシートを見る
    1. レシートの合計が3000円以上なら、コップを用意してそこにテーブルの上のレシートを入れる。1. を実行する
    2. レシートの合計が3000円未満なら、1. を実行する
    1. と 2. をレシートを取り尽くすまで実行する。
    2. レシートを取り尽くしたら、出来たコップ（3000円以上のレシートが入ったコップ）の数を記録する

計算1をN回繰り返し、出来たコップの数の記録を見る。
最も多い「コップの数」が、乱択の結果、確率的に分かった応募できる最大の口数。（＝必ずしも正解とは言えない）

上のコードを swift で書いた。（Nは100万回）

import Foundation

let passValue: Int = 3000       // 基準値
let tryMax: Int = 1000000       // 試行回数

// 入力
let inputValues: [Int] = [
    1676,
    843,
    1000,
    233,
    1731,
    321,
    179,
    259,
    460,
    1594,
    3544,
    632,
    2172,
    2623,
    1102,
    84,
    466,
    306,
    855,
    3255,
    1609,
    1345,
    1170,
    4220,
    6231,
    180,
    91,
    2937,
    544,
    1577,
    421,
    3899,
    585,
    671,
    1811,
    875,
    384,
    950,
    1618
]


// あらかじめ基準値以上のグループを作成する
var passedGroups: [[Int]] = []          // すでに基準値以上のグループ
var inputValues2: [Int] = []

for value in inputValues {
    if value >= passValue {
        passedGroups.append([value])
        continue
    }
    
    inputValues2.append(value)
}

var groupNumMap: [Int: Int] = [:]     // グループ数の出現頻度のマップ
var bestGroups: [[Int]] = []          // 最適なグループ配列
var lastPercent: Int = 0

// print("- count \(inputValues2.count)")
// print("- sum \(inputValues2.reduce(0, +))")
// print("")

// ランダムに基準値を超えるグループを作成する
for i in 0..<tryMax {
    // 一時変数を準備する
    var tempGroups: [[Int]] = []    // 一時的なグループの配列
    var tempValues: [Int] = inputValues2  // 一時的な値の配列
    var tempGroup: [Int] = []       // 一時的なグループ
    
    // ランダムに基準値以上のグループの配列を作成する
    while true {
        // ランダムなインデックスを得る
        let index: Int = Int.random(in: 0..<tempValues.count)
        let value: Int = tempValues[index]
        tempValues.remove(at: index)
        
        // 一時的なグループに値を追加する
        tempGroup.append(value)
        let reduceValue: Int = tempGroup.reduce(0, +)
        
        if reduceValue >= passValue {
            // 一時的なグループの合計が基準値以上の場合
            // -> グループを、一時的なグループ配列に追加する
            tempGroups.append(tempGroup)
            tempGroup = []  // 一時的なグループをクリア
        }
        
        if tempValues.count > 0 {
            continue
        }

        // 値がなくなったので試行終了
        break
    }
    
    // グループ数の出現カウントを控える
    let groupsCount: Int = tempGroups.count + passedGroups.count
    groupNumMap[groupsCount] = (groupNumMap[groupsCount] ?? 0) + 1
    
    if tempGroups.count > bestGroups.count {
        // 最適なグループ数を超えたら、最適なグループを更新する
        bestGroups = tempGroups
    }
    
    let percent: Int = Int((Float(i) / Float(tryMax)) * 100)
    if percent > lastPercent {
        lastPercent = percent
        print("\(percent)%")
    }
}

// 計算の結果得た最適なグループ配列に、あらかじめ作成したすでに基準値以上のグループを合成する
bestGroups.insert(contentsOf: passedGroups, at: 0)

print("\n\n")

// 結果を出力
print("# Result\n")

// 最適なグループ配列を出力
print("## Best groups")
print("group numbers : \(bestGroups.count)")
print("")

for i in 0..<bestGroups.count {
    print("### Group\(i + 1)")
    for j in 0..<bestGroups[i].count {
        print("- \(bestGroups[i][j])")
    }
    
    print("")
}

// グループ数の出現頻度
print("## Frequency of group numbers\n")
let sortedKeys: [Int] = groupNumMap.keys.sorted()
for key in sortedKeys {
    print("### \(key)")
    print("- count \(groupNumMap[key] ?? 0)")
    
    let percent: Float = (Float(groupNumMap[key] ?? 0) / Float(tryMax)) * 100
    print("- percent \(percent)%")
}

これを実行すると、結果の出力は以下。
１５口応募できるようだ。

全体のうち、口数の出現頻度が

  • 12口が 0.7%
  • 13口が 45%
  • 14口が 52%
  • 15口が 1%

となる。

# Result

## Best groups
group numbers : 15

### Group1
- 3544

### Group2
- 3255

### Group3
- 4220

### Group4
- 6231

### Group5
- 3899

### Group6
- 2623
- 1102

### Group7
- 306
- 855
- 259
- 1609

### Group8
- 233
- 1594
- 544
- 180
- 632

### Group9
- 1676
- 1345

### Group10
- 466
- 2937

### Group11
- 950
- 460
- 321
- 1731

### Group12
- 1577
- 1000
- 585

### Group13
- 84
- 1170
- 2172

### Group14
- 91
- 1618
- 384
- 671
- 843

### Group15
- 179
- 1811
- 421
- 875

## Frequency of group numbers

### 12
- count 7584
- percent 0.7584%
### 13
- count 453582
- percent 45.3582%
### 14
- count 528201
- percent 52.8201%
### 15
- count 10633
- percent 1.0633%