日別訪問者数の最大平均区間(large)

9465 ワード
Python 初心者 Python3 paiza Python テキストリンク

0.問題

対象となる全日数をDDとし、全日数のうちあるN日間に訪問してくる
人数の平均が最大になる区間の開始日の候補日の数と、それらの候補日の中で
最も早い日をあげなさい。

この問題を解くに当たり考えたことをまとめてみた。
下記の手順でクリアできた。

1.最初に図を書いてみる

与えられのは以下の二行。

一行目に全日数(DD)と求めたい区間の日数(N)\\
二行目にそれぞれの日数の訪問人数(A_i(i=1,,,DD))

5 3
1 2 3 2 1

上記のように考えていくと、
開始日が2日目が日別訪問者数が8人となり最大平均区間になる。
また、この訪問者数が最大になるのは開始日が2日の時のみなので、候補日の数は
1となる。
答えは「1 2」となることがわかる。

2.考え方(パターン分け)

ここで平均が最大になる＝ある区間の日別訪問者数の和が最大になると考える。

(1)DDとNが同じ場合

⇒DDまでの訪問者数の計算する必要はない
候補日も、区間のパターンも一つしかないので、[1 1]が答え

(2)DD>NでかつN>1の場合 

X_1=A_1+...+A_{N}\\
max1=X_1(max1:N日間での最大訪問者数)\\
C_{day}=1(C_{day}:候補日の数)\\
S_{day}=d(S_{day}:N日間での最大訪問者数の開始日)

X_d:dを開始日とした時のN日間の訪問者数とする
前の章より、下記のことがわかる。
この漸化式により、計算回数も減らせる。

X_d=X_{d-1}-A_{d-1}+A_{d-1+N}(d=2,,,DD-N+1)-★\\

ⅰ)ある開始日dのN日間の訪問者数>最大訪問者数の処理 

C_{day}=1\\
max1=X_d\\
S_{day}=d

ⅱ)ある開始日dのN日間の訪問者数＝最大訪問者数の処理 

C_{day}=C_{day}+1\\
max1=X_d

(3)DD>NでかつN=1の場合 

X_d=A_d(d=1,,,DD)

上記に(2)の場合の1)、2)の条件の処理を考えればよい。

3.コード例


in1=input()
in2=input()
arr1=in1.split()
arr2=in2.split()

dn=0

num1=int(arr1[1])
#print(num1)

if num1>1:
    i=0
    for i in range(num1):
        dn=dn+int(arr2[i])

    max_t=dn
    max_i=0
    k_cnt=1

    for i in range(1,int(arr1[0])-num1+1):
        dn=dn+int(arr2[i+num1-1])-int(arr2[i-1])

        if max_t<dn:
            k_cnt=1
            max_i=i
            max_t=dn

        else:
            if max_t == dn:
                k_cnt=k_cnt+1
                max_t=dn

    max_i=max_i+1
    print(str(k_cnt)+' '+str(max_i))

elif num1>1 and num1 == int(arr1[0]):
    print('1 1')
else:
    max_i=0
    max_t=0
    k_cnt=1
    for i in range(int(arr1[0])):
        dn=int(arr2[i])
        if max_t<dn:
            max_t=dn
            k_cnt=1
            max_i=i
        else:
            if max_t == dn:
                max_t=dn
                k_cnt=k_cnt+1

    max_i=max_i+1
    print(str(k_cnt)+' '+str(max_i))