問題
これの中にある、
です。
数字が被っていないカードがいっぱいあって、
その中から３枚引いたとき数字の合計が7で割り切れるパターン数を出せ、という問題です。
説明
「汎用的に」と題しているのは
これは単純に、
- 「７」で割るとか「３」枚とかの数字は可変にしよう
という話です。(※問題文にはそんな話はまったく出てきません)
３重のfor文とか再帰呼び出しとかは使わないよ、ということですね。
解き方は無難に
公式の解説にある方法も参考にしています。
- カードは「Nで割った余り」だけ見てその個数を数える。
- 重複を承知で、余りのすべての組み合わせを列挙する。 (例 [0,0,0]〜[6,6,6] 7^3通り)
- 余りの合計がNで割り切れる組み合わせだけを選択する。(例 [0,0,0] [0,3,4] [1,1,5] 等)
- それぞれ余りの個数が足りていることを確認する。 (例 [1,1,5]のとき、余り1のカードは最低2枚必要)
- 同じ余りを複数選択した場合の個数に注意してパターン数を算出。(例 10枚中3枚なら10×9×8になるような調整)
- 最後に、重複していた分を排除する。(枚数の階乗で割ると答えになる)
コード
JavaScriptを普段使わない人にもどうにか雰囲気が伝わらないかと頑張った結果がこれ。
count_mod_N.js
// Copyright © 2024 https://qiita.com/tanin_no_sorani
// Released under the CC0 1.0 Universal license.
'use strict';
const N = 7; // mod N
const M = 3; // 組み合わせの枚数
const mod_N = Array(N).fill(0n); // Nで割った余り0〜(N-1)の個数カウント用
let first = true; // 先頭行の判定用
require('node:readline').createInterface({ input: process.stdin })
.on('line', line => {
if (first) { first = false; return; } // 先頭行は不要
mod_N[parseInt(line) % N]++; // Nで割った余りで分類し、その個数だけを数える
})
.on('close', () => {
let total = 0n;
// 重複も含めて全ての「余りの組み合わせ」を列挙
const state = Array(M).fill(0); // 組み合わせの状態 (例 [0, 0, 0]～[6, 6, 6])
let patterns = Math.pow(N, M) ; // 組み合わせの総数 N^M 通り
while (patterns--) {
// 組み合わせの値の合計がNで割り切れるか確認 (例 [0, 3, 4] → 7)
if ((state.reduce((a, b) => (a + b)) % N) === 0) {
// 現在の組み合わせで選択されている余りの回数を数える
const selected = Array(N).fill(0n); // 選択された余りの回数カウント用
state.map(i => selected[i]++); // (例 state[1,1,5]のときseletected[0,2,0,0,0,1,0,0])
// それぞれの余りの個数が不足していないことを確認
if (state.every(i => (selected[i] <= mod_N[i]))) {
// 「余りの組み合わせ」→「余りの個数 - 調整」に置き換え→すべての積を取る
total += state
.map(i => (mod_N[i] - (--selected[i]))) // (調整例 3回なら-2,-1,-0となる)
.reduce((a, b) => (a * b), 1n);
}
}
// 次の組み合わせ (繰り上がりの例 [6,0,0]→[0,1,0])
for (let i = 0; i < M; i++) { // 繰り上がり用のfor
if ((++state[i] % N) !== 0) { break; } // 1加算し、繰り上がりがなければ抜ける
else { state[i] = 0; } // 繰り上がる場合、この桁は0に戻して継続
}
}
// 最後に重複を排除 (枚数の階乗 M! で割る)
for (let i = 2; i <= M; i++) { total /= BigInt(i); }
// (※BigIntのまま渡すと末尾に'n'が付くためtoString()が必要)
console.log(total.toString());
});
感想
テストはすべて0.05秒だったので速度的には大きな問題はなさそうです。
もっと分かりやすく書けないかとは思うのですが、
コードが一度頭の中で固まってしまうとなかなか難しいんですよね。
最後まで読んでいただいてありがとうございました。