公式
A - 最適な練習相手 / Optimal Practice Partner 解説
by
A - 最適な練習相手 / Optimal Practice Partner 解説
by
physics0523
初心者の方へ
- AtCoder をはじめたばかりで何をしたらよいか分からない方は、まずは practice contest の問題A「Welcome to AtCoder」を解いてみてください。基本的な入出力の方法が載っています。
- また、プログラミングコンテストの問題に慣れていない方は、AtCoder Beginners Selection の問題をいくつか解いてみることをおすすめします。
- C++入門 AtCoder Programming Guide for beginners (APG4b) は、競技プログラミングのための C++ 入門用コンテンツです。
- Python入門 AtCoder Programming Guide for beginners (APG4bPython) は、競技プログラミングのための Python 入門用コンテンツです。
まず、 \(N,L,D\) の情報を標準入力から受け取ります。
その後、先頭から順に以下の判定を行います。
- 暫定的に、解 \(x=-1\) とする。
- \(i=1,2,\dots,N\) について、以下を繰り返す。
- \(D_i \le L\) であれば、部員 \(i\) は推薦される可能性がある。
- 現在の解 \(x=-1\) であれば、暫定的な解を \(x=i\) に更新する。
- そうでなく \(D_x < D_i\) であれば、部員 \(i\) の方が実力値が高いため、暫定的な解を \(x=i\) に更新する。
- そうでないとき、部員 \(i\) の方が実力値が低いか、実力値が同じでも番号が大きいかなので、部員 \(i\) が推薦されることはない。
- \(D_i > L\) であれば、部員 \(i\) が推薦されることはない。
- \(D_i \le L\) であれば、部員 \(i\) は推薦される可能性がある。
- 最終的な \(x\) が解である。
これらは、例えば for 文と if 文の組み合わせで実現できます。
実装例 (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,L;
cin >> N >> L;
vector<int> D(N+1);
for(int i=1;i<=N;i++){
cin >> D[i];
}
int res=-1;
for(int i=1;i<=N;i++){
if(D[i]<=L){
if(res==-1){res=i;}
else if(D[res]<D[i]){res=i;}
}
}
cout << res << "\n";
return 0;
}
投稿日時:
最終更新:
