くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く M-SOLUTIONS プロコンオープン 2020 C - Marks

Python3で解く M-SOLUTIONS プロコンオープン 2020 C - Marks

AtCoder 競プロ 300点 全探索

結構単純。{\displaystyle n}回テストがあって、頭から{\displaystyle k}個ぶんたまったら、累積積（総乗）をずらしながら考える。
この時のポイントは、出と入の大小関係できまるので実際に総乗を計算する必要はないということ。（出と入については後述する。）解説は出と入の割合を計算していたが、大小関係をでも同じこと。

概要

問題

  1. {\displaystyle n}回テストを行う。
  2. {\displaystyle k}回分テスト結果がたまったら、総乗を計算し始める
  3. {\displaystyle k}回目のテストから{\displaystyle n}回目のテストまで、最新のテスト結果を含む過去{\displaystyle k}回ぶんの総乗の結果を{\displaystyle B_i}とすると{\displaystyle B_i}と{\displaystyle B_{i-1}}の大小の結果は？（全部で{\displaystyle n-k}個の結果となる）

解くときに考えた内容

  • これは、単純に{\displaystyle k}個ごとにずれていくだけなので、総乗の結果である{\displaystyle B_i}を計算しなくていい。

  • ずれていくというのは、以下の様なイメージ

    f:id:black_tank_top:20200726085619j:plain
    Ai と Ak+iの差で大小関係が決まっていくイメージ

  • {\displaystyle B_i}と{\displaystyle B_{i+1}}の違いは以下である。

    {\displaystyle A_i}と{\displaystyle A_{k+i}}だけでそれ以外の数値は共通である。

なので、この{\displaystyle A_i}と{\displaystyle A_{k+i}}をそれぞれを出と入と表現していた。

  • コードも非常にシンプルである。

コード

n, k = map(int, input().split())
A = [int(x) for x in input().split()]
for i in range(n-k):
    if A[i] < A[i+k]:
        print('Yes')
    else:
        print('No')