【今日の精進】ABC128F - Frog Jump

毎日格上の問題を倒すやつの40日目です。

問題リンク

atcoder.jp

問題概要

横 マスのグリッドがあり、それぞれ数字が書かれてるよ。はじめ、カエルが マス目にいるよ。

を決めて、「 歩進んで 歩下がる」ことを繰り返すよ。

同じマスに2度立ち入るか、範囲から出た場合、大失敗となり、得点が 点となるよ。

無事 マス目についた場合、スコアは1回通ったマス目の数字の和の合計だよ。

スコアの最大値を求めてね。

解法

明らかに答えは0以上です。

また、操作の仕様上、先頭から等間隔、末尾から等間隔にマスを選ぶことがわかります。この間隔を全探索します。

実現できないパターンがいくつかあることに注意すると、個々の実装は比較的容易です*1。計算量を評価しましょう。

これは有名な話で、計算量は と評価できます。

提出コード

N=int(input())
s=list(map(int,input().split()))
ans=0
for i in range(1,N):
    lf=0
    ri=N-1
    score=0
    used={0,N-1}
    while True:
        lf+=i
        ri-=i
        if ri<i:
            break
        if lf in used:
            break
        if ri in used:
            break
        if lf==ri:
            break
        score+=s[lf]
        score+=s[ri]
        ans=max(ans,score)
        used.add(lf)
        used.add(ri)
print(ans)

Submission #47077676 - AtCoder Beginner Contest 128

感想

橙のわりには結構簡単?

*1:相変わらず雑