![見出し画像](https://assets.st-note.com/production/uploads/images/31494312/rectangle_large_type_2_30075c1ad586118e37a88b2bbc9dae0b.jpg?width=1200)
M-SOLUTIONS プロコンオープン 2020見直し C - Marks
問題
N学期制の学校で、毎期末に試験が行われる。各学期の成績は以下の様に付けられる。
・1学期からK-1学期は成績がつかない
・k学期からN学期はその学期を含めた直近K学期の成績がつく
N,Kと各学期末試験の結果が与えられるので、K+i学期の成績が前学期よりも真に高い場合は「Yes」をそうでない場合は「No」を出力せよ。
例えば、Nが5、Kが3で、各学期の成績が「1,2,3,4,5」だった場合は、
・3学期の成績は「1*2*3」で「6」
・4学期の成績は「2*3*4」で「24」
・5学期の成績は「3*4*5」で「60」
よって、出力は
・4学期は3学期よりも真に高い成績なので「Yes」
・5学期は4学期よりも真に高い成績なので「Yes」
となります。
単純に掛け算で比較してもイケそうですが、制約を見るとNの最大値が「2*10^6」、成績の最大値が「10^9」なのでオーバーフローしたり、TLEになりそうです。
作成した解答(Python 155ms)
n, k = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(k, n):
if a[i - k] < a[i]:
print("Yes")
else:
print("No")
結構シンプルにかけました。以下の様な考え方です。
掛け算に含まれる要素は、前の学期の最初と後の学期の最後以外は共通しています(上の図で言うとx,y)。よって、学期の大小関係は非共通部分(前の学期の最初と、後の学期の最後)の大小関係と等しくなります。つまり、掛け算は不要で非共通部分のみ比較すれば良いというわけです。
解説を見て作成した解答(CPP 347ms)
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using vi = vector<int>;
int main() {
int n, k;
cin >> n >> k;
vi a(n);
rep(i, n) cin >> a.at(i);
for (int r = k; r < n; r++) {
if(a[r - k] < a[r]) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
Pythonの方が早い。。。理由はわからないですが初めてPythonの方がCPPより早かった。不思議です。
この記事が気に入ったらサポートをしてみませんか?