尺取法についてのあれこれ - kira924ageの雑記帳

はじめに

尺取法というものを知った。

尺取法の概要

JOI用語集によると、

配列に対して二つのインデックスを持ち、条件に応じて片方を進める操作を繰り返すことで答えを得る方法のこと。尺取虫の動きにちなんで名付けられた。DPの一種ともとれる。またキューの実装も尺取法の一種である。

とのこと。

例えば、AtCoder Regular Contest 022のB問題はこの尺取法を使って解くことができる。

問題の概要

問題文

高橋君は細長いお菓子を持っています。このお菓子は Ncm の長さのお菓子で、 1cm ごとにブロックに分かれています。それぞれのブロックには $10^5$ 種類の味うちのいずれかの味がついていて、左端から i 番目のブロックには $A_i$ 番目の味がついています。
高橋君はこのお菓子から、出来るだけ長い「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」を切り出したいと思っています。最大で何 cm の部分を切り出すことが出来るでしょうか。ただし、切る場所はブロックとブロックの境界の部分のみとします。

入力

入力は以下の形式で標準入力から与えられる。
$N\\ A_1\ \ \ A_2\ \ \ .\ .\ .\ A_N$

1 行目には、お菓子の長さを cm 単位で表した整数 $N(1\leq N\leq 10^5)$ が与えられる。

2 行目には、お菓子の各ブロックの味の情報を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 $A_i(1\leq A_i\leq 10^5)$ は、左端から i 番目のブロックの味が $Ai$ 番目の味であることを表す。

出力

高橋君がこのお菓子から切り出すことの出来る「同じ味のブロックが 2 つ以上含まれない、ひと繋がりになった部分」の最大の長さを cm 単位で表す 1 つの整数を 1 行に出力せよ。出力の末尾に改行をいれること。

入力例1

7
1 2 1 3 1 4 4

出力例1

3

入力例2

1
100

出力例2

1

要約するとこの問題は、
長さNの数列Aにおいて、同じ数字を2つ以上含まない最長の区間を求めろということ。

実装

Cで実装してみる。

/*http://arc022.contest.atcoder.jp/tasks/arc022_2*/
#include <stdio.h>
#define max(a, b) ((a > b) ? a : b)
 
int main(){
  int N, A[100001], S[100001]={0};
  int ans=0, r=0, l;
 
  scanf("%d", &N);
 
  for(l=0; l<N; l++) scanf("%d", &A[l]);
 
  for(l=0; l<N; l++){
    while(r<N && S[A[r]]==0){
      S[A[r]]++;
      r++;
  }
  ans = max(ans, r-l);
  S[A[l]]--;
}
 
  printf("%d\n", ans);
 
  return 0;
}

重要なのは13行目から20行目までのfor文の中の処理。
確かに尺取虫のような動きをしている。

参考

http://www.slideshare.net/chokudai/arc022