POJ 1868 - Antiarithmetic?

http://poj.org/problem?id=1868

概要

順列 p について，長さが2より大きい等差数列をなしている部分列が存在しないとき，p を antiarithmetic と呼ぶ． たとえば 2, 0, 1, 4, 3 は antiarithmetic であり，0, 5, 4, 3, 1, 2 は部分列 0, 1, 2 が長さ3の等差数列をなしているので antiarithmetic ではない．

与えられた大きさ n の順列が antiarithmetic であるかどうか答える．

制約

• 3 <= n <= 10^4

解法

与えられるのは順列なので，a[i] = i が何番目にあるか という配列をつくって，a[i] < a[i+d] < a[i+2*d] または a[i] > a[i+d] > a[i+2*d] となるようなものが存在するかどうかチェックすればいい．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 bool check(const int *a, int N)
 5 {
 6   for (int i = 0; i < N-2; i++) {
 7     for (int j = 1; i+2*j < N; j++) {
 8       if (a[i] < a[i+j] && a[i+j] < a[i+2*j]) {
 9         return false;
10       }
11       if (a[i] > a[i+j] && a[i+j] > a[i+2*j]) {
12         return false;
13       }
14     }
15   }
16   return true;
17 }
18 
19 int main()
20 {
21   int N;
22   while (scanf("%d", &N) != EOF && N != 0) {
23     scanf("%*c");
24     static int a[10000];
25     for (int i = 0; i < N; i++) {
26       int x;
27       scanf("%d", &x);
28       a[x] = i;
29     }
30     puts(check(a, N) ? "yes" : "no");
31   }
32   return 0;
33 }