AtCoder Beginner Contest 182 D問題

AtCoder Python

前書き

atcoder.jp

D問題

難易度：茶色
時間：タイムオーバー

O(n**2)の処理はできないので計算量を意識しながらコードを書かないといけません。

1回目の提出

はい数個のWA。
累積和を使えば解ける問題と言うのは察していました。
実は動作i終了後でのロボットの位置の最大値だと勘違いしてしまい「簡単やん」と思ったのが運のつき。
動作iの途中位置も含めてのロボットの位置の最大値でした。

最後の処理がまずい事は気付きながら時間がないのでとりあえず提出しました。

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Alis, Sumlis = np.zeros(len(A)), np.zeros(len(A))
 
for i in range(len(A)):
    Alis[i] += Alis[i-1]+A[i]
    Sumlis[i] += Sumlis[i-1]+Alis[i]

np.append(Sumlis,0)
np.append(Alis,0)
print(int(max(np.max(Alis[:np.argmax(Sumlis)+1])+np.max(Sumlis),0)))

2回目

アルゴリズムは以下の通りです。

  1. 動作i(1,2..,n)が増すごとにA[i]の移動変位は累積されていく
  2. 動作nにおいてロボットの移動変位を配列化（Alis）
  3. 動作iではi回の移動をします。i回の中で最も正の方向に移動した移動変位の配列化（Amax）
  4. 動作i終了時点でのロボットの位置を配列化（Sumlis）
  5. 動作i-1での位置（Sumlis）+次の動作iでの最大移動変位（Amax）の和を取得（Ans）
  6. スタート位置が最大の場合・ゴール位置が最大の場合・最大位置（Ans）で最も最大となる地点を出力

私は3の発想がなかったですね。精進しなきゃ。

import numpy as np
import sys
 
N = int(input())
A = np.array(list(map(int, input().split())))
Alis, Amax, Sumlis = np.zeros(len(A)), np.zeros(len(A)), np.zeros(len(A)+1)
 
if N==1:
  print(max(max(A),0))
  sys.exit()
        
# N=1の場合、Alis[i-1]でA[0]を参照してしまうので注意
for i in range(N):
  Alis[i] = Alis[i-1]+A[i]
  Amax[i] = max(Alis[i],Amax[i-1])
  Sumlis[i+1] += Sumlis[i]+Alis[i-1]+A[i]
 
Ans = Sumlis[:N]+Amax
print(int(max(max(np.max(Ans),0),Sumlis[-1])))

結果

WA（数個WA）→WA（1個WA）→AC