7 1 2008 12 22 1 Copyright c 2008 The Japanese Committee for International Olympiad in Informatics
1 n i i 1 i n index = 0; [ index] = 1; = = ; if ( == ) { // [ index ]++; } else if () { if( index == 0 ) { // // // // [ index ]++; = ; } else { // // 1-1
[ index - 1 ] += [ index ] + 1; index--; } } else { // index++; [ index ] = 1; } = ; n 2 2 n 100000 25 O(n 2 ) O(1) O(n) 100% 1-2
2 1 x x. s t. s t n = max{ s, t }. 1 (O(n 4 ) ) s, t. s, s i j (1 i j s ), O( s 2 ). x t ( )., k (1 k t x + 1), t k x x, x y. O( x t )., k x,,., O( s 3 t ). s t, s O( s t min{ s 2, t 2 }), s t.,,, O( x + t ) Boyer Moore., O( s 2 t ). 2 (O(n 3 ) ) s, s t., 1 i s 1 j t i j, s i t j., i j s t, min{ s, t }, O( s t min{ s, t }). (O(n 2 ) ) s t, s t,. 2-1
, 0 i s, s i s t. s j t j a j = 1, a j = 0, a 1,..., a t 1 O( t ). 1 i = 1. s = BRACADABRA t = KCADADABRBCRDARA a = 0010111110000000 i, s t,. O( s t ). 2 n = 50 3, n = 4000 7, 10..,,,,. s t 1 50 50 2 2 50 49 17 2 (G L), G 3 50 50 0 0 4 4000 4000 5 5 4000 3980 1951 2 (E T), E 6 3984 3992 1440 4 (F, K, I, Y), KF 7 4000 4000 904 3 (V, G, H), V 8 3992 3994 719 3 (K, F, V), K 9 3995 3996 3995 C 10 4000 4000 0 0 : 2 2-2
3 1 P 1,..., P N 4 M P 0 = 0 N + 1 P 0, P 1,..., P N 4 0 4 a, b, c, d (0 a, b, c, d N) S a,b,c,d { Pa + P b + P c + P d P a + P b + P c + P d M S a,b,c,d = 0 P a + P b + P c + P d > M max S a,b,c,d 0 a,b,c,d N 1 (O(N 4 ) ) = 0 N + 1 (N + 1) 4 4 O(N 4 ) 0 a b c d N 4! = 4 3 2 1 = 24 1 N = 100 200 2 (O(N 3 log N) ) 4 3 1 3 P a, P b, P c 4 P a + P b + P c + P d M d P d M (P a + P b + P c ) 3-1
d P d d P 0,..., P N O(log N) O(N log N) O(N 3 log N) N = 300 3 (O(N 2 log N) ) 2 4 2 2 2 (N +1) 2 Q 1 Q 2 Q r (r (N + 1) 2 ) O(N 2 log N) 2 Q i 2 3 4 Q i + Q j M j Q j j O(log N) i (1 i r) j O(N 2 log N) O(N 2 log N) N 1000 2 N, M 1 2 3 4 5 6 7 8 9 10 N 50 100 300 300 300 1000 1000 1000 1000 1000 M 2 10 6 2 10 7 10 8 10 8 10 8 2 10 8 2 10 8 2 10 8 2 10 8 2 10 8 1 2 2 5 3 3-2
4 3 1 2 1 3 1,2 1 Danger(i, j, l) i j l Danger(i, j, l) 0 i = n i = n 1 l < m 1 j k i+1 j (d i,j + d i+1,j ) x i,j x i+1,j + Danger(i + 1, j, l) l < m 1 j k i+2 j (d i,j + d i+2,j ) x i,j x i+2,j + Danger(i + 2, j, l + 1) 1 j k 1 j Danger(1, j, 0) m > 0 1 j k 2 j Danger(2, j, 1) 4-1
k m nc i k n i i=0 n 20% 2 1 A B,C A i + 1 j a B, C i j b, j c B Danger(i, j b, l) A Danger(i + 1, j a, l) A C Danger(i, j c, l) A Danger(i + 1, j a, l) A 1 3 memo -1 Danger(i, j, l) memo[i, j, l] = 1 1 memo[i, j, l] memo[i, j, l] 1 memo[i, j, l] k 4-2
Danger i, j, l 3 1 2k k 0 Danger i, j, l 2k = n k (m + 1) 2k 2nmk 2 O(nmk 2 ) 3 2 memo memo memo n 1 j k n, 0 l m j, l memo[n, j, l] = 0 n 1 1 j k n 1, 0 l m 1 j, l memo[n, j, l ] = 0 l = m i j l memo[i, j, l] 1 j k i+1 j (d i,j + d i+1,j ) x i,j x i+1,j + memo[i + 1, j, l] l < m 1 j k i+2 j (d i,j + d i+2,j ) x i,j x i+2,j + memo[i + 2, j, l + 1] memo[i, j, l] 1 i 1 j k 1 j memo[1, j, 0] m > 0 1 j k 2 j memo[2, j, 1] 4-3
k i j l 2k k 0 l m l m + 1 i 1 j k j k 1 i n i n 2k (m + 1) k n 2nmk 2 2 O(nmk 2 ) 3 2 4-4
5 c 0, c 1,, c n i(0 i < n) c i < a 1, a 2 < c i+1 2 a 1, a 2 a 1, a 2 () c 0 n c 0, c 1,, c n 0, 1,, n c n 1000000 n 2n + 2 30% w, h 100 n n n O(n 3 ) m(x, y) i(0 i < n) (a i, b i ) (c i, d i ) m (x, y) (a i, b i d i ) 1 (c i + 1, b i d i ) 1 m(x, y) = x k=0 m (k, y) O(n 2 ) m(x, y) = 0 m(x, y) = 0 m(x, y) = 0 x, y m(x, y) m(x±1, y), m(x, y±1) m(x±1, y), m(x, y±1) m(x, y) m(x, y) = 0 x, y m(x, y) = 0 x, y 5-1
3 n O(n 2 ) 5-2