M-SOLUTIONS プロコンオープン 2020見直し C - Marks

問題

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より早かった。不思議です。