ABC381Dを解いた【尺取法?】

筆者はレート800前後の茶～緑コーダ

ABC381のD問題を解いていく

実装コード

解説を見たがよくわからなかったので公式解説の解法2のコードをPythonに移植した。

尺取法みたいな実装でいいようだ。

詳しいコードの解説を生成AIから抜粋したのでどうぞ

生成AIによる解説

1. 連続する同じ数字のグループを見つけるための変数を初期化:

   • ans: 最大値を格納（初期値は0）
   • l: 最後の同じ数字のインデックスを格納（初期値は0）

2. 配列Aの各要素に対してループを行う

3. 条件分岐:

   • if (i-l) % 2 == 0:
     この条件は、偶数番目の要素に対応する
     • if last[a]==i-1:
       最後の同じ数字が1つ前の位置にある場合、lを更新
     • elif last[a]>=l:
       最後の同じ数字が現在の位置以上にある場合、lを更新
   • elif A[i-1] != a:
     これは奇数番目の要素に対応する
     新しい数字が見つかった場合、lをリセット

4. 各ループ内で:

   • 現在の状況をエラー出力（デバッグ用）
   • 現在のグループのサイズ（i-l+1）をansに更新
   • last辞書を更新

5. ループ終了後:

   • ans以下の最大の偶数を出力

main.py

import sys
from collections import defaultdict
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

def main():
    N = rI()
    A = rLI()
    last = defaultdict(lambda: -2)
    
    ans = 0
    l = 0
    for i,a in enumerate(A):
        if (i-l) % 2 == 0:
            if last[a]==i-1:l=last[a]
            elif last[a]>=l:l=last[a]+1
        elif A[i-1] != a:l=i
        # err(f"{i=},{a=},{l=},{ans=},{last[a]=},{i-l+1}")
        ans=max(ans,i-l+1)
        last[a]=i
    print(2*(ans//2))            

if __name__ == '__main__':
    main()

まとめ

ABC381のD問題解いた。

尺取法で使えばいいようだが、解説がよくわからなかったので、詳しい解説ができなかった。