公式
B - 奨学金の選考 / Scholarship Selection 解説
by
B - 奨学金の選考 / Scholarship Selection 解説
by 
MMNMM
この問題は、それぞれの奨学金について応募者のうち最大の評価点をもつもの（複数いる場合、その中で番号が最小のもの）の応募者番号を求める問題です。 この問題では、主に次のような点に気を付ける必要があります。
- 応募者の選考を（番号によるタイブレークも含めて）正しく行う
- 特に、応募者が \(0\) 人の場合も正しい答えを出せるように実装を行う。
- 配列へのアクセスを \(0\)-indexed で行う言語では、\(1\)-indexed で行われる応募者番号の入力・出力を適切に扱う。
ものが並んだ列から、ある基準に基づいた最大のものを求めるときは、列を順番に見て「これまで見た中で最大のもの」（必要なら「最大のものの基準となる値」）を更新していく形で実装をするとよいでしょう。
入力や出力は除いて、この部分の実装例を見てみましょう。
// P, K, C はすでに入力されているとする
int recipient_id = 0; // これまで見た中で一番評価が良かった応募者の番号（はじめは 0 にしておく）
int recipient_score = 0; // 一番評価が良かった候補者の評価点
for (int j = 0; j < K; ++j) {
if (recipient_score < P[C[i] - 1] || (recipient_score == P[C[i] - 1] && recipient_id > C[i])) { // これまでの候補者の評価点より評価点が高いか、評価点が同じで番号が小さいなら
// 結果を更新
recipient_id = C[i];
recipient_score = P[C[i] - 1];
}
}
# P, K, C はすでに入力されているとする
recipient_id = 0 # これまで見た中で一番評価が良かった応募者の番号（はじめは 0 にしておく）
recipient_score = 0 # 一番評価が良かった候補者の評価点
for c in C:
if recipient_score < P[c] or (recipient_score == P[c] and recipient_id > c): # これまでの候補者の評価点より評価点が高いか、評価点が同じで番号が小さいなら
# 結果を更新
recipient_id = c
recipient_score = P[c]
これでも正しく判定を行うことができ、この問題を正解するには十分です。 この問題では、情報の持ち方を工夫することで条件を少しシンプルにできます。タイブレークを含む比較の実装をする際、組（タプル）の辞書順比較ができる言語ではうまく情報を持つことで辞書順比較に帰着させられる場合があります。
今回の問題では、評価は大きいほうを、番号は小さいほうを取るため、単純な辞書順にはなりません。 一方を \(-1\) 倍するなどして順番を逆転させることで辞書順比較をすることができます。
pair<int, int> recipient_info = {0, 0}; // これまで見た中で一番評価が良かった応募者の評価点と、番号（はじめは 0 にしておく）の -1 倍
for (int j = 0; j < K; ++j) {
pair<int, int> now_candidate_info = {P[C[j] - 1], -C[j]}; // 応募者の評価点と、番号の -1 倍
recipient_info = max(recipient_info, now_candidate_info); // 組の辞書順で大きい方に更新
}
recipient_info = (0, 0) # これまで見た中で一番評価が良かった応募者の評価点と、番号（はじめは 0 にしておく）の -1 倍
for c in C:
now_candidate_info = (P[c - 1], -c) # 応募者の評価点と、番号の -1 倍
recipient_info = max(recipient_info, now_candidate_info) # 組の辞書順で大きい方に更新
上の実装例では番号を \(-1\) 倍しているので、出力するときにはこれを戻す必要があります。
言語によっては、任意の基準に応じてリストから最大値を求める関数が提供されている場合があります。 そのような関数を適切に使うことで、よりシンプルに実装することができるかもしれません。 リストが空だと正しく動かない可能性があることに注意してください。
// C++
ranges::max( // 最大値を求める
C, // 応募者から
{}, // 通常の（辞書順）比較で
[&P](int c) { // 基準は
return make_pair(P[c - 1], -c); // 評価点と、番号の -1 倍の組
}
);
# Python
max(C, key=lambda c:(P[c - 1], -c)) # 評価点と番号の -1 倍の組を基準に最大値を求める
上記の実装例では、評価点の情報は P[0], P[1], …, P[M - 1] に格納されていました。
入力される応募者の番号は \(1,2,\ldots,M\) なので、実装の際はこの \(1\) のズレを正しく扱わなければいけません。
例えば、以下のような方針が考えられるでしょう（他の方針もあるかもしれません）。
- 配列 \(P\) にアクセスする際だけ \(C\) の値を \(1\) 減らす
- 入力されたときに \(1\) 減らし、出力するときに \(1\) 増やす
- 配列 \(P\) の先頭に適当な値を追加し、\(P\) のアクセスも \(1\)-indexed で行う
これらの方針の間に明らかな優劣はありません。 自分のスタイルに合わせた方法を選択し、実装の途中で混乱してしまわないようにしましょう（一般論として、複数の処理の途中で \(0\)-indexed と \(1\)-indexed の扱いを変えたりすると混乱しやすいので、一貫した扱い方をするとよいでしょう）。 この問題においては、それぞれの方針は次のような特徴があります。
- 配列 \(P\) にアクセスする際だけ \(C\) の値を \(1\) 減らす
- 今回の問題では評価点の情報を得る回数が少ないので、最終的なコードが短くなりそうです。デバッグ出力などをしても、入力される値がそのまま出力されることになるのでわかりやすいかもしれません。配列へのアクセスなどの \(0\)-indexed な値が必要な操作が多い問題では、すべての箇所で正しく値を減らす必要があるため、複雑になってしまう場合があります。
- 入力されたときに \(1\) 減らし、出力するときに \(1\) 増やす
- プログラム中でほとんど \(0\)-indexed の値しか扱わないでいられるため、混乱しにくいです。出力の際に値を \(1\) 増やすことを忘れると、サンプルの実行やデバッグ出力で思っていない値が得られるためちょっと躓く可能性があります。
- 配列 \(P\) の先頭に適当な値を追加し、\(P\) のアクセスも \(1\)-indexed で行う
- 候補者がいない場合の番兵も兼ねられるため、今回の問題では処理がすっきりする場合があります。追加した値がうまく扱いにくい場合や、多くの配列を扱う場合には実装が煩雑になってしまうかもしれません。
それぞれの方針での実装例は以下のようになります。
C++ での実装例
#include <iostream>
#include <vector>
using namespace std;
int main(){
int N, M;
cin >> N >> M;
vector<int> P(M);
for (int& p : P) {
cin >> p;
}
for (int i = 0; i < N; ++i) {
int K;
cin >> K;
int recipient_id = 0; // これまで見た中で一番評価が良かった応募者の番号（はじめは 0 にしておく）
int recipient_score = 0; // 一番評価が良かった候補者の評価点
for (int j = 0; j < K; ++j) {
int C;
cin >> C;
if (recipient_score < P[C - 1] || (recipient_score == P[C - 1] && recipient_id > C)) { // これまでの候補者の評価点より評価点が高いか、評価点が同じで番号が小さいなら
// 結果を更新
recipient_id = C;
recipient_score = P[C - 1];
}
}
// 答えを出力
cout << recipient_id << endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main(){
int N, M;
cin >> N >> M;
vector<int> P(M);
for (int& p : P) {
cin >> p;
}
for (int i = 0; i < N; ++i) {
int K;
cin >> K;
pair<int, int> recipient_info = {0, 1}; // これまで見た中で一番評価が良かった応募者の評価点と、番号（はじめは -1 にしておく）の -1 倍
for (int j = 0; j < K; ++j) {
int C;
cin >> C;
--C; // 0-index に直す
pair<int, int> now_candidate_info = {P[C], -C}; // 応募者の評価点と、番号の -1 倍
if (recipient_info < now_candidate_info) { // 組の辞書順で大きかったら
// 結果を更新
recipient_info = now_candidate_info;
}
}
// 答えを出力（-1 倍を戻し、1-indexed に直して出力）
cout << -recipient_info.second + 1 << endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N, M;
cin >> N >> M;
vector<int> P(M + 1); // 先頭に評価点 0 の架空の応募者 0 を入れておく
for (int& p : P | views::drop(1)) { // 先頭以外を読み込む
cin >> p;
}
for (int i = 0; i < N; ++i) {
int K;
cin >> K;
vector<int> C(K);
for (int& c : C) { // 応募者を読み込む
cin >> c;
}
C.emplace_back(); // 架空の応募者を入れておく
cout << ranges::max(C, {}, [&P](int c) { return make_pair(P[c - 1], -c); }) << endl;
}
return 0;
}
Python での実装例
N, M = map(int, input().split())
P = list(map(int, input().split()))
for _ in range(N):
K, *C = map(int, input().split())
recipient_id = 0 # これまで見た中で一番評価が良かった応募者の番号（はじめは 0 にしておく）
recipient_score = 0 # 一番評価が良かった候補者の評価点
for c in C:
if recipient_score < P[c - 1] or (recipient_score == P[c - 1] and recipient_id > c): # これまでの候補者の評価点より評価点が高いか、評価点が同じで番号が小さいなら
# 結果を更新
recipient_id = c
recipient_score = P[c - 1]
# 答えを出力
print(recipient_id)
N, M = map(int, input().split())
P = list(map(int, input().split()))
for _ in range(N):
K, *C = map(int, input().split())
C = [c - 1 for c in C] # 0-indexed に直す
recipient_info = (0, 1) # これまで見た中で一番評価が良かった応募者の評価点と、番号（はじめは -1 にしておく）の -1 倍
for c in C:
now_candidate_info = (P[c - 1], -c) # 応募者の評価点と、番号の -1 倍
recipient_info = max(recipient_info, now_candidate_info) # 組の辞書順で大きい方に更新
# 答えを出力（-1 倍を戻し、1-indexed に直して出力）
print(-recipient_info[1] + 1)
N, M = map(int, input().split())
P = [0] + list(map(int, input().split())) # 先頭に評価点 0 の架空の応募者 0 を入れておく
for _ in range(N):
K, *C = map(int, input().split())
print(max([0] + C, key=lambda c: (P[c], -c))) # 架空の応募者 0 を含めた最大値を求めて出力
投稿日時:
最終更新: