Pythonでしゃくとり法

はじめに

こんにちは、なかなか研究が軌道に乗らなくてツラいマンです。

今回はPythonでしゃくとり法を使う場面があったので載せていこうかなと。

しゃくとり法とは

与えられた配列の中から、ある条件を満たす最大の範囲を見つけるアルゴリズムです。

「左端（left）と右端（right）に配列の添字を入れ、rightをインクリメントしつつ、条件を満たさない要素を含んでしまった時に条件を満たさない要素が外にでるまでleftを進める」

という感じ？わかりにくいっすね

使用例

B: 細長いお菓子 - AtCoder Regular Contest 022 | AtCoder
を使います。

問題の解き方として、leftとrightの間に、同じ数字が入らないよう調整、その長さを取る。
という感じです

以下コード

N = int(raw_input())
A = map(int, raw_input().split())

left = 0 #左端初期値
ans = 1 #解初期値（0だとAの要素が１つだけの時にうまくいかない）
#rightはleftの１つ右からスタート
for right in range(1,N):
    #rightをインクリメントした後、同じ要素が含まれていた場合leftをインクリメント
    while A[right] in A[left:right]:
        left += 1
    ans = max(ans, right-left+1) #大きい方に更新
print ans

こんな感じです。
rightを進めてleftを縮める動きがしゃくとり虫っぽいからしゃくとり法なんですね、多分。

ちなみに

この解法だと最後のテストケースでTime Limite Exceededがでてしまい９９点止まりです。
これを抜ける方法募集してます！（切実）

最後に

絶賛競技プログラミング練習中です。
アルゴリズムに苦手意識があるので覚えられる解法は全部覚える勢いで行っちゃいましょうね〜〜。