パ研合宿2019 第3日「パ研杯2019」C - カラオケ
全探索の問題.基本にして大事なんだと思う(ゆるふわっとした表現.)
問題の説明
人の生徒のグループが与えられ,こいつらが「カラオケ大会」に出る事となった.
歌える曲は曲であり,番号
が
曲を歌うと,
点を取る事が分かっている.
コンテストのルールは以下の通り
- まず,グループ全体を通して,
曲から歌う曲を2曲選ぶ.
- それぞれの生徒がこれら2つを歌う.
- 各生徒の得点はこの2曲のうち,高い方の点数とする.
- これらを生徒
人について行い,生徒の得点の合計をグループの得点とする.
このルールの下で,グループの得点の最大値を求めよ.
条件
- 入力は全て整数.
考えた事
問題文の意味は何か.曲を2つ選び,その2つのうち大きい方の値を足していって作成可能な最大値はいくらかという事である.文章が恣意的であるが,大事なのは曲の選び方である事を理解して欲しい.
極端な例であるが,この生徒のグループ皆が十八番*1のものを選んでしまえば難しくもなんともないのである.しかし,なかなかそんな都合よく行く事ばかりではない.
例えばこの曲がめっちゃ得意で200点出せる人がいたとしよう.しかし,その人の声質が極めて独特でその曲にめちゃんこ合っているが,他の人には全く歌えず1点ばかり出してしまうかもしれない.そうした場合,カラオケ大会でその曲を持ち込むのは憚られるだろう.皆が効率よく点を取れる曲を持ち込むのが良さそうだ.*2
いうなれば小学校の頃にあった大縄跳びに近いのだ.あれもすごく俊敏に跳べる人に合わせていると他がついてこれず上手く巡らない.かといって遅くしすぎるとそれはそれで跳んだ回数が稼げない.縄を回す速さを調整する必要があるのだ.
ではこの最適な速さを見つけるにはどうしたらいいか.もちろん全て試せばいいのだ.縄を最遅から最速まで全て試し,そこで得られた跳躍回数を比較して,最大を出力すればいい.
それは今回も同様である.カラオケ大会に持ち込める曲の選び方は通りあるので,それら全てのパターンを試し,点数の最大値を出力すればいい.
for(int k=0;k<N;k++) {
count += max(A.at(k).at(i), A.at(k).at(j));
}
とし,countに持ち込んだ2曲のうち点数の高い方の点数(生徒の得点)を足していく.それを今までの持ち込み曲で得られる合計と比較すれば良いわけだ.計算量はであり,高々
程しかなく間に合う.*3
プログラム
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
for(int i=0;i<N;i++) {
for(int j=0;j<M;j++) {
cin >> A.at(i).at(j);
}
}
int64_t sum = 0;
for(int i=0;i<M;i++) {
for(int j=i+1;j<M;j++) {
int64_t count = 0;
for(int k=0;k<N;k++) {
count += max(A.at(k).at(i), A.at(k).at(j));
}
sum = max(sum, count);
}
}
cout << sum << endl;
}
