中級 0件解決済み 正答率0%

くじの当選集計

当選番号と0個、1個、2個…一致したくじがそれぞれ何枚あるかを数えます。

このチャレンジで学べること

  • セットを使って所属を素早く判定する
  • くじごとの一致数を数える
  • 得点のヒストグラムを作る

問題

原文(英語)を表示

学校の募金イベントで数字くじを行います。抽選ではいくつかの異なる当選番号が選ばれ、どのくじにも同じ個数の異なる番号が書かれています。くじに書かれた番号の順番は関係なく、くじの得点はその番号のうち当選番号であるものの個数です。賞を決めるために、主催者は各得点のくじが何枚あるかを知りたいと考えています。

ticket_lottery(winning, tickets) を実装してください。

入力

winning: 互いに異なる当選番号。

tickets: くじ。各行は1枚のくじに書かれた互いに異なる番号で、長さは winning と同じです。

出力

長さ len(winning) + 1 のリストを返してください。位置 k には、当選番号とちょうど k 個一致したくじの枚数が入ります。

制約

1 ≤ len(winning) ≤ 10

0 ≤ くじの枚数 ≤ 5,000

1 ≤ すべての番号 ≤ 99

例

例 1
入力:
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] です。

例 2
入力:
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用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。