公式

E - Perfect Standings 解説 by MMNMM

この問題は、次の \(2\) つのパートに分けることができます。

  1. すべての参加者の名前と得点を作る
  2. それらを順位にそって並べ替える

どちらのパートもいくつか異なる実装方法があります。

1. すべての参加者の名前と得点を作る

1 番のパートのもっとも簡単な方法は、\(31\) 人の得点と名前をそのまま記述してしまうことです。

実装例 (C++)

    vector<pair<int, string>> standings{
        {a, "A"},
        {b, "B"},
        {c, "C"},
        {d, "D"},
        {e, "E"},
        {a + b, "AB"},
        {a + c, "AC"},
        {a + d, "AD"},
        {a + e, "AE"},
        {b + c, "BC"},
        {b + d, "BD"},
        {b + e, "BE"},
        {c + d, "CD"},
        {c + e, "CE"},
        {d + e, "DE"},
        {a + b + c, "ABC"},
        {a + b + d, "ABD"},
        {a + b + e, "ABE"},
        {a + c + d, "ACD"},
        {a + c + e, "ACE"},
        {a + d + e, "ADE"},
        {b + c + d, "BCD"},
        {b + c + e, "BCE"},
        {b + d + e, "BDE"},
        {c + d + e, "CDE"},
        {a + b + c + d, "ABCD"},
        {a + b + c + e, "ABCE"},
        {a + b + d + e, "ABDE"},
        {a + c + d + e, "ACDE"},
        {b + c + d + e, "BCDE"},
        {a + b + c + d + e, "ABCDE"}
    };

実装例 (Python)

standings = [
    (a, "A"),
    (b, "B"),
    (c, "C"),
    (d, "D"),
    (e, "E"),
    (a + b, "AB"),
    (a + c, "AC"),
    (b + c, "BC"),
    (a + d, "AD"),
    (b + d, "BD"),
    (c + d, "CD"),
    (a + e, "AE"),
    (b + e, "BE"),
    (c + e, "CE"),
    (d + e, "DE"),
    (a + b + c, "ABC"),
    (a + b + d, "ABD"),
    (a + c + d, "ACD"),
    (b + c + d, "BCD"),
    (a + b + e, "ABE"),
    (a + c + e, "ACE"),
    (b + c + e, "BCE"),
    (a + d + e, "ADE"),
    (b + d + e, "BDE"),
    (c + d + e, "CDE"),
    (a + b + c + d, "ABCD"),
    (a + b + c + e, "ABCE"),
    (a + b + d + e, "ABDE"),
    (a + c + d + e, "ACDE"),
    (b + c + d + e, "BCDE"),
    (a + b + c + d + e, "ABCDE"),
]

上の方法では「ひとりの参加者だけの得点を間違える」などのバグを埋め込んだ場合に気づきにくく、記述量も多いという欠点があります。

部分集合と整数を対応させるテクニックを用いることで、記述量を減らすことができます。

大きさ \(N\) の集合 \(S=\lbrace s _ 0,s _ 1,\dotsc,s _ {N-1}\rbrace\) について、\(S\) の部分集合は \(2 ^ N\) 個あります。 これらの部分集合を \(0\) 以上 \(2 ^ N-1\) 以下の整数と以下のように対応させます。

  • \(0\) 以上 \(N-1\) 以下の整数 \(i\) について、整数 \(x\) に対応する \(S\) の部分集合 \(X\) は \(x\) を二進法で表記したときの \(2 ^ i\) の位が \(1\) であるとき、かつそのときに限り \(s _ i\) を含む。

例えば今回の問題の場合、\(1\) は二進法で表記すると 00001 なので \(\lbrace A\rbrace\) に、\(10\) は二進法で表記すると 01010 なので \(\lbrace B,D\rbrace\) に対応すると考えることができます。

この方法でそれぞれの参加者を \(1\) 以上 \(31\) 以下の整数と対応させることができるので、これを用いて必要な情報を作ることができます。

この方法を使う場合、「 \(i\) 問目 \((1\leq i\leq5)\) の配点」 を整数 \(i\) を使って取得できると便利なので、配点を入力する際には単に \(5\) つの変数を使うのではなく、長さ \(5\) の配列を使うのがよいでしょう。

実装例 (C++)

    vector<pair<int, string>> standings;
    for (int bit = 1; bit < 32; ++bit) {
        int solved_point = 0;
        string name = "";
        for (int digit = 0; digit < 5; ++digit)
            // digit 桁めのビットが立っているのが digit 問目を解いた人
            if (bit & 1 << digit) {
                // 得点と名前にその問題を追加
                solved_point += point[digit];
                name += "ABCDE"[digit];
            }
        // 得点と名前の情報を追加
        standings.emplace_back(solved_point, name);
    }

実装例 (Python)

standings = []
for bit in range(1, 32):
    solved_point = 0
    name = ""
    for digit in range(5):
        # digit 桁めのビットが立っているのが digit 問目を解いた人
        if bit & 1 << digit:
            # 得点と名前にその問題を追加
            solved_point += point[digit]
            name += "ABCDE"[digit]
    # 得点と名前の情報を追加
    standings.append((solved_point, name))

2. 順位にそって並べ替える

列を順序に沿って並べ替える（ソートする）関数は多くの言語に存在しているので、本問題でもそれらを利用することができるでしょう。 しかし、この問題では得点については降順（大きいほうから小さいほう）に、得点が同じならば名前については昇順（小さいほうから大きいほう）に並べ替える必要があります。 これを実現する方法はいくつかあります。

言語の標準で組（いくつかの値をまとめたもの）の辞書順比較ができる言語の場合、得点をすべて \(-1\) 倍することで、どちらも昇順とすることができます。

実装例 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <ranges>
using namespace std;

int main() {
    array<int, 5> point{};
    for (auto&& p : point)
        cin >> p;

    // ソートのために配点をすべて -1 倍しておく
    for (auto&& p : point)
        p *= -1;

    // すべての参加者の得点と名前の情報
    vector<pair<int, string>> standings;
    for (int bit = 1; bit < 32; ++bit) {
        int solved_point = 0;
        string name = "";
        for (int digit = 0; digit < 5; ++digit)
            // digit 桁めのビットが立っていれば、その問題を解いた人
            if (bit & 1 << digit) {
                solved_point += point[digit];
                name += "ABCDE"[digit];
            }
        // 得点と名前の情報を追加
        standings.emplace_back(solved_point, name);
    }

    // 順番に並べ替える
    ranges::sort(standings);

    // 名前を順に出力
    for (const auto& name : standings | views::values)
        cout << name << endl;

    return 0;
}

実装例 (Python)

point = list(map(int, input().split()))

# ソートのために配点をすべて -1 倍しておく
point = [-p for p in point]

standings = []
for bit in range(1, 32):
    solved_point = 0
    name = ""
    for digit in range(5):
        # digit 桁めのビットが立っているのが digit 問目を解いた人
        if bit & 1 << digit:
            # 得点と名前にその問題を追加
            solved_point += point[digit]
            name += "ABCDE"[digit]
    # 得点と名前の情報を追加
    standings.append((solved_point, name))

# 順番に並べ替え、名前を順に出力
for _, name in sorted(standings):
    print(name)

言語の標準で安定ソートを行う関数が存在する言語で、かつ組をソートする際に、安定ソートを行う関数に「何番目の値でソートするか」を与えられる言語の場合、次のようにして所望の順序でソートを行うことができます。

  • 名前が昇順になるようソートを行う。
  • 得点が降順になるよう安定ソートを行う。

もしくは、昇順ソートしかできない場合（降順ソートを行うのが煩雑な場合）は以下のようにしてもよいです。

  • 名前が昇順になるようソートを行う。
  • 列を反転させる。
  • 得点が昇順になるよう安定ソートを行う。
  • 列を反転させる。

実装例 (C++)

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <ranges>
using namespace std;

int main() {
    array<int, 5> point{};
    for (auto&& p : point)
        cin >> p;

    // すべての参加者の得点と名前の情報
    vector<pair<int, string>> standings;
    for (int bit = 1; bit < 32; ++bit) {
        int solved_point = 0;
        string name = "";
        for (int digit = 0; digit < 5; ++digit)
            // digit 桁めのビットが立っているのが digit 問目を解いた人
            if (bit & 1 << digit) {
                // 得点と名前にその問題を追加
                solved_point += point[digit];
                name += "ABCDE"[digit];
            }
        // 得点と名前の情報を追加
        standings.emplace_back(solved_point, name);
    }

    // 名前の昇順にソート
    ranges::sort(standings, less{}, &pair<int, string>::second);
    // 得点の降順に安定ソート
    ranges::stable_sort(standings, greater{}, &pair<int, string>::first);

    // 名前を順に出力
    for (const auto& name : standings | views::values)
        cout << name << endl;

    return 0;
}

実装例 (Python)

from operator import itemgetter

point = list(map(int, input().split()))

standings = []
for bit in range(1, 32):
    solved_point = 0
    name = ""
    for digit in range(5):
        # digit 桁めのビットが立っているのが digit 問目を解いた人
        if bit & 1 << digit:
            # 得点と名前にその問題を追加
            solved_point += point[digit]
            name += "ABCDE"[digit]
    # 得点と名前の情報を追加
    standings.append((solved_point, name))

# 名前の昇順にソート
standings.sort(key=itemgetter(1))
# 列を反転
standings.reverse()
# 点数の昇順に安定ソート
standings.sort(key=itemgetter(0))
# 列を反転
standings.reverse()

# 名前を順に出力
for _, name in standings:
    print(name)

比較関数（どのような順序でソートを行うか）を記述できる言語では、それを使ってもよいです（実装例は省略します）。

投稿日時:
最終更新: