問題
学校の募金イベントで数字くじを行います。抽選ではいくつかの異なる当選番号が選ばれ、どのくじにも同じ個数の異なる番号が書かれています。くじに書かれた番号の順番は関係なく、くじの得点はその番号のうち当選番号であるものの個数です。賞を決めるために、主催者は各得点のくじが何枚あるかを知りたいと考えています。
ticket_lottery(winning, tickets) を実装してください。
入力
winning: 互いに異なる当選番号。
tickets: くじ。各行は1枚のくじに書かれた互いに異なる番号で、長さは winning と同じです。
出力
長さ len(winning) + 1 のリストを返してください。位置 k には、当選番号とちょうど k 個一致したくじの枚数が入ります。
制約
1 ≤ len(winning) ≤ 10
0 ≤ くじの枚数 ≤ 5,000
1 ≤ すべての番号 ≤ 99
例
入力:
winning = [3, 11, 20]
tickets = [
[3, 11, 20],
[20, 5, 7],
[1, 2, 4],
[11, 3, 9]
]
期待される出力:
expected = [1, 1, 1, 1]
入力:
std::vector<long long> winning = {3, 11, 20};
std::vector<std::vector<long long>> tickets = {
{3, 11, 20},
{20, 5, 7},
{1, 2, 4},
{11, 3, 9}
};
期待される出力:
std::vector<long long> expected = {1, 1, 1, 1};
入力:
long[] winning = new long[] {3, 11, 20};
long[][] tickets = new long[][] {
new long[] {3, 11, 20},
new long[] {20, 5, 7},
new long[] {1, 2, 4},
new long[] {11, 3, 9}
};
期待される出力:
long[] expected = new long[] {1, 1, 1, 1};
解説
くじはそれぞれ3個、1個、0個、2個一致しているので、0から3の各得点が1回ずつ現れます。結果は [1, 1, 1, 1] です。
入力:
winning = [7, 8]
tickets = [
[8, 7],
[7, 1],
[1, 7]
]
期待される出力:
expected = [0, 2, 1]
入力:
std::vector<long long> winning = {7, 8};
std::vector<std::vector<long long>> tickets = {
{8, 7},
{7, 1},
{1, 7}
};
期待される出力:
std::vector<long long> expected = {0, 2, 1};
入力:
long[] winning = new long[] {7, 8};
long[][] tickets = new long[][] {
new long[] {8, 7},
new long[] {7, 1},
new long[] {1, 7}
};
期待される出力:
long[] expected = new long[] {0, 2, 1};
解説
1枚は両方の番号を含み(順番は関係ありません)、2枚は1個だけ一致しているので [0, 2, 1] です。
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
当選番号を、セットか番号を添字にした真偽値の配列に入れましょう。
ヒント 2
1枚のくじの一致数を数え、その得点の箱に1を足します。
ヒント 3
結果の箱の数は、当選番号の数より1つ多くなります。
目安の計算量
時間 O(t × k)、追加メモリ O(k)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。