等差数列〜横へな 2013.6.1 参考問題

問題

数列の中から最も長い等差数列を見つけ出し、その長さを答える。
等差数列というのは Wikipedia - 等差数列を見ると分かる通り、等間隔に並んだ数の列のことである。
例えば。

[1,2,3,4] や [5,6] は間隔が 1 なので等差数列。
[4,7] や [11,16,21,26,31] は、間隔が 2 あるいは 5 なので等差数列。
[4,6,7,9,10,11,13] や [1,2,3,4,6] は、間隔が1のところと2のところが混じっているので等差数列ではない。

入力と出力

入力は、 12345abcz のようになっている。各文字は数を示している。文字と値の対応は下表の通り：

文字	0〜9	a〜z
値	0〜9	10〜35

例えば、 012abku は [0, 1, 2, 10, 11, 20, 30] という数列を意味している。この数列に埋まっている等差数列のうち、最長のものは [0, 10, 20, 30] となる。この等差数列の長さは 4 なので、 4 を出力すればよい。

補足

出力する数値の形式は普通の 10 進数とする。
入力の数列はには同じ数を含まない。
入力の数列は昇順に整列済みである。
長さ1でも等差数列とみなす。
不正な入力 ( 11112222 ( 重複がある ) や 12abcd9 ( 整列済みになっていない ) 、 零壱弐参 ( 0〜9、a〜z に当てはまらない ) など ) に対処する必要はない。
実装ができた方は Qiitaの記事のコメント欄からリンクを張っていただくと見つけやすくて助かります。

サンプルデータ

#	入力	期待	最長等差数列
0	`12345abcz`	`5`	`12345`
1	`012abku`	`4`	`0aku`
2	`01245689cdeghik`	`6`	`048cgk`
3	`0`	`1`	`0`
4	`m`	`1`	`m`
5	`01`	`2`	`01`
6	`az`	`2`	`az`
7	`0az`	`2`	`0a` 他 2 件
8	`0ak`	`3`	`0ak`
9	`05ak`	`3`	`05a` 他 1 件
10	`01349acdrsuv`	`2`	`01` 他 65 件
11	`01245789efgipqstux`	`3`	`012` 他 31 件
12	`0123456789abcdefghijklmnopqrstuvwxyz`	`36`	`0123456789abcdefghijklmnopqrstuvwxyz`
13	`02468acegikmoqsuwy`	`18`	`02468acegikmoqsuwy`
14	`0369cfilorux`	`12`	`0369cfilorux`
15	`048cgkosw`	`9`	`048cgkosw`
16	`05afkpuz`	`8`	`05afkpuz`
17	`0123456789abcdefghjklmnopqrstuvwxyz`	`18`	`0123456789abcdefgh` 他 1 件
18	`0123456789bcdefghijklmopqrstuvwxyz`	`12`	`0369cfilorux` 他 3 件
19	`0156abfgklpquv`	`7`	`05afkpu` 他 1 件
20	`0167cdijopuv`	`6`	`06ciou` 他 1 件
21	`0178eflmst`	`5`	`07els` 他 1 件
22	`0189ghopwx`	`5`	`08gow` 他 1 件
23	`019aijrs`	`4`	`09ir` 他 1 件
24	`012567abcfghklmpqruvw`	`7`	`05afkpu` 他 2 件
25	`012678cdeijkopquvw`	`6`	`06ciou` 他 2 件
26	`012789efglmnstu`	`5`	`07els` 他 2 件
27	`01289aghiopqwxy`	`5`	`08gow` 他 2 件
28	`0129abijkrst`	`4`	`09ir` 他 2 件
29	`01235678abcdfghiklmnpqrsuvwx`	`7`	`05afkpu` 他 3 件
30	`01236789cdefijklopqruvwx`	`12`	`0369cfilorux`
31	`0123789aefghlmnostuv`	`5`	`07els` 他 3 件
32	`012389abghijopqrwxyz`	`5`	`08gow` 他 3 件
33	`01239abcijklrstu`	`4`	`0123` 他 9 件
34	`368acdknouvz`	`4`	`68ac`
35	`369chikmnopqruwx`	`6`	`mnopqr`
36	`05689cdefghijklmnopqrstvwy`	`18`	`cdefghijklmnopqrst`
37	`2489abdeiklrsuvwz`	`4`	`28ek` 他 2 件
38	`678bhijklnpqrsuvwxyz`	`6`	`hjlnpr` 他 1 件
39	`1246cfjkopquxz`	`5`	`fkpuz`
40	`123459abcefhilmotuvx`	`6`	`9cfilo`
41	`02578acdefikmopqsuvwxz`	`8`	`05afkpuz` 他 1 件
42	`135abdefghijlopstuwz`	`7`	`defghij`
43	`0126789fgjnotuvxy`	`5`	`29gnu`
44	`2345678defjkmnoqrtvwxy`	`7`	`2345678`
45	`02568bdemnostw`	`5`	`258be`
46	`145689bdfhilnqrstvwxz`	`6`	`159dhl` 他 2 件
47	`4aghjrtuvwxyz`	`7`	`tuvwxyz`
48	`158achklmqstwy`	`3`	`5ht` 他 13 件
49	`012346abceghjknortv`	`5`	`01234` 他 2 件

C/C++/Java 用のテストデータ

/*0*/ test( "12345abcz", "5" );
/*1*/ test( "012abku", "4" );
/*2*/ test( "01245689cdeghik", "6" );
/*3*/ test( "0", "1" );
/*4*/ test( "m", "1" );
/*5*/ test( "01", "2" );
/*6*/ test( "az", "2" );
/*7*/ test( "0az", "2" );
/*8*/ test( "0ak", "3" );
/*9*/ test( "05ak", "3" );
/*10*/ test( "01349acdrsuv", "2" );
/*11*/ test( "01245789efgipqstux", "3" );
/*12*/ test( "0123456789abcdefghijklmnopqrstuvwxyz", "36" );
/*13*/ test( "02468acegikmoqsuwy", "18" );
/*14*/ test( "0369cfilorux", "12" );
/*15*/ test( "048cgkosw", "9" );
/*16*/ test( "05afkpuz", "8" );
/*17*/ test( "0123456789abcdefghjklmnopqrstuvwxyz", "18" );
/*18*/ test( "0123456789bcdefghijklmopqrstuvwxyz", "12" );
/*19*/ test( "0156abfgklpquv", "7" );
/*20*/ test( "0167cdijopuv", "6" );
/*21*/ test( "0178eflmst", "5" );
/*22*/ test( "0189ghopwx", "5" );
/*23*/ test( "019aijrs", "4" );
/*24*/ test( "012567abcfghklmpqruvw", "7" );
/*25*/ test( "012678cdeijkopquvw", "6" );
/*26*/ test( "012789efglmnstu", "5" );
/*27*/ test( "01289aghiopqwxy", "5" );
/*28*/ test( "0129abijkrst", "4" );
/*29*/ test( "01235678abcdfghiklmnpqrsuvwx", "7" );
/*30*/ test( "01236789cdefijklopqruvwx", "12" );
/*31*/ test( "0123789aefghlmnostuv", "5" );
/*32*/ test( "012389abghijopqrwxyz", "5" );
/*33*/ test( "01239abcijklrstu", "4" );
/*34*/ test( "368acdknouvz", "4" );
/*35*/ test( "369chikmnopqruwx", "6" );
/*36*/ test( "05689cdefghijklmnopqrstvwy", "18" );
/*37*/ test( "2489abdeiklrsuvwz", "4" );
/*38*/ test( "678bhijklnpqrsuvwxyz", "6" );
/*39*/ test( "1246cfjkopquxz", "5" );
/*40*/ test( "123459abcefhilmotuvx", "6" );
/*41*/ test( "02578acdefikmopqsuvwxz", "8" );
/*42*/ test( "135abdefghijlopstuwz", "7" );
/*43*/ test( "0126789fgjnotuvxy", "5" );
/*44*/ test( "2345678defjkmnoqrtvwxy", "7" );
/*45*/ test( "02568bdemnostw", "5" );
/*46*/ test( "145689bdfhilnqrstvwxz", "6" );
/*47*/ test( "4aghjrtuvwxyz", "7" );
/*48*/ test( "158achklmqstwy", "3" );
/*49*/ test( "012346abceghjknortv", "5" );

等差数列 〜 横へな 2013.6.1 参考問題

問題

入力と出力

補足

サンプルデータ

C/C++/Java 用のテストデータ

等差数列〜横へな 2013.6.1 参考問題