はじめに
１時間以上かけて解きましたが、貰えたのはWAとTLEと絶望でした。
悔しいので、公式解説のk+1・・・の実装の為の解説をします。
稚拙ながら、公式解説に補足する形で話していくので、
まずは、解説の方をご覧になってから読んで頂ればと思います。
探索の目星をつけよう
まず、今からやることを図で示します。
下の数字は、correctの値です。
K=1
K=2
K=3
と、上図の通りになります。（Kはさらに続きます。）
見て考えると、このコードは、
①Ｋ飛ばし分スタート位置を一つずらし、その度実行する(k=1なら(0)、k=2なら(0,1))。
②Ｋずつ飛ばして、解説の問題Ｘのコードと同じように実装する。
①をやる理由は、一度しかやらないと図の赤い部分しかやらないことになる為です。
また、図を見ていると、Ｋ飛ばし分だけスタート位置を変え、実行すると全ての数字が読めることも分かると思います。
コード例
では、①、②の通りに実装してみましょう。
n = int(input())
h = list(map(int,input().split()))
ans = 1
#飛ばす距離をｎまでやる
for k in range(1,n):
#スタート位置を1ずつずらしてそれぞれ実行
for i in range(k):
height = 0
correct = 0
for j in range(i,n,k):
if(height != h[j]):
correct = 0
height = h[j]
correct += 1
ans = max(correct,ans)
print(ans)
見てわかる通り、ほとんど解説の問題Ｘのコードと変わりませんね。
冷静になれば、全探索で出来る問題でしたね・・・・。
締め
ここまで見てくださりありがとうございました。
質問・ご指摘等ございましたら、コメントしていただけると幸いです。
おまけ
ここからは、今回の解説に関係ない部分ですので、興味ない方は、読み飛ばしてください。
今回、私はこの問題を解く上で考察をミスりました。
私は、「同じ数字同士で分けてから考える」という解説とは真逆の方法でやってしまいました。
hの値が３０００以下ということで、「いける！」と思ってしまいました。
とりあえず、そのコード見せます。
n = int(input())
h = list(map(int,input().split()))
same = [[] for _ in range(3001)]
for i in range(n):
same[h[i]].append(i)
ans = 1
for i in range(3001):
if(len(same[i]) > 0):
dic = {}
hai = same[i]
for j in range(len(hai)):
for k in range(j + 1,len(hai)):
tmp = dic.get(hai[k] - hai[j],[])
tmp.append(hai[j])
dic[hai[k] - hai[j]] = tmp
for j in dic.keys():
retu = dic[j]
tmp = 2
tar = retu[0]
for k in range(1,len(retu)):
if(retu[k] - tar > j):
ans = max(ans,tmp)
tmp = 2
tar = retu[k]
elif(retu[k] - tar == j):
tmp += 1
tar = retu[k]
#ここでミス
elif(retu[k] - tar < k):
continue
ans = max(ans,tmp)
print(ans)
それで、このコードがどうなったかというと、
WA1。何度も見たことある悪夢の光景ですね。
では、何故間違えてしまったかというと、コード内の「#ここでミス」ですね。
この部分では、K=3の赤色で１と書かれた７の部分のような場所を飛ばすためのものですね。
もし、コードがこの後も続くとしたらK=3の時のみにこの７の後に７が続く場合、ansの値が１足りず、誤答になってしまいます。
これに気付いて色々やりましたが、無理でした。もし数字で分けて考える方法で出来た人がいたら教えてほしいです。
・・・多分根本の考察ミスってるから無理な気がするんですよね。
もしかしたら、誰かの役に立つかもしれないのでおまけとして書かせていただきました。
ここまで読んで下さり本当にありがとうございました。