시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 8 | 6 | 5 | 71.429% |
2015 年の国際情報オリンピックはカザフスタンで行われる.カザフスタンの「カザフ」は,アルファベッ トで “QAZAQ” と綴られることがある.この QAZAQ は回文である.このことを知った JOI 君は,回文が 好きになって,目についた文字列から回文を作ることにした.
JOI君が見つけたのは長さが N の文字列である.各文字には1からC までの整数が定まっており,文字列の 文字を整数に置き換えた数列をS = (S1, S2, . . . , SN)とする.この数列のi番目から j番目まで (1 ≦ i ≦ j ≦ N) を取り出した数列 (Si, Si+1, . . . , Sj) を断片 (i, j) と呼ぶ.断片 (i, j) がそれを逆転させた数列と等しいとき, すなわち,(Si , Si+1, . . . , Sj) = (Sj , Sj−1, . . . , Si) が成り立つとき,断片 (i, j) は回文である.
JOI 君は以下の操作により回文を作る.
JOI 君はこの操作により,できるだけ長い回文を作りたい.
JOI 君の見つけた文字列を表す数列 S が与えられる.JOI 君が作ることができる回文の長さの最大値を求 めよ.
標準入力から以下の入力を読み込め.
標準出力に,JOI 君が作ることができる回文の長さの最大値を表す整数を 1 行で出力せよ.
追加の制限はない.
12 26 26 17 17 17 1 26 1 17 19 20 1 14
8
この入力例では,N = 12,C = 26 で,S = (26, 17, 17, 17, 1, 26, 1, 17, 19, 20, 1, 14) である.ここで,断片 (4, 8) を昇順にソートすることで S′ = (26, 17, 17, 1, 1, 17, 17, 26, 19, 20, 1, 14) となり,断片 (1, 8) が回文にな る.この回文の長さは 8 であり,これが最長である.
4 3 1 2 3 2
3
この入力例では,S = (1, 2, 3, 2) である.ここで,断片 (1, 1) を昇順にソートすることで,S′ = (1, 2, 3, 2) となる.S と S′ は同じ数列である.S′ の断片 (2, 4) が回文になる.この回文の長さは 3 であり,これが最 長である.