AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(

Size: px

Start display at page:

Download "AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len("

つねたけかむら
4 years ago
Views:

1 AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(b)-1] == c[0]: print( YES ) else: print( NO ) 1

2 B: Choice Integers A A 1 ( ) A%B, 2A%B, 3A%B,... A%B A B (k + B)A%B = (ka + BA)%B = ka%b B A BA B 2

3 C: Sentou i i + 1 T T T min(t, ) 3

4 D: Simple Knapsack N W v i ABC032 D i = 2, 3,, N w 1 w i w (N/4) 4 = 25 4 = O( ) C++ Java D Python Ruby O(1) 4

5 E: Ball Coloring 400, 000 R max, R min, B max, B min 4 MIN = min(x 1, x 2,..., x n, y 1, y 2,..., y n ) MAX = max(x 1, x 2,..., x n, y 1, y 2,..., y n ) R min = MIN, B min = MIN R max = MAX, B max = MAX R min = MIN&B max = MAX R min = MIN&B max = MAX R min = MIN&B max = MAX R min B max R min = MIN&R max = MAX 1-5

6 F: Many Move DP O(N 3 ) DP dp[i][a][b] := i a b O(N 2 ) dp[i][a] := i a x i x 0 = B dp[0][a] = 0, dp[0][x] = (x A) min(dp[q][1], dp[q][2],..., dp[q][n]) DP dp[i][a] = dp[i 1][a] + x i 1 + x i (a x i ) dp[i][x i 1 ] = min(dp[i 1][x i 1 ] + x i 1 + x i, min j=1,2,...,n (dp[i 1][j] + j x i )) DP dp[i 1][1], dp[i 1][2],..., dp[i 1][n] dp[i][1], dp[i][2],..., dp[i][n] 1. x i 1 + xi 2. min j=1,2,...,n (dp[i 1][j] + j x i ) dp[i][x i 1 ] min j=1,2,...,n (dp[i 1][j] + j x i ) j x i min j=1,2,...,xi (dp[i 1][j] j + x i ) min j=xi+1,2,...,n(dp[i 1][j] + j x i ) dp[i 1][j] j dp[i 1][j] + j min dp[i 1][j] dp[i 1][j] j dp[i 1][j] + j 6

7 dp[i 1][j] j dp[i 1][j] + j add min Segment Tree 7

8 AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori python3 example: a, b, c = input ( ). s p l i t ( ) i f a [ l e n ( a ) 1] == b [ 0 ] and b [ l e n ( b) 1] == c [ 0 ] : p r i n t ( YES ) e l s e : p r i n t ( NO ) 1

9 B: Choice Integers The sum of multiples of A is always a multiple of A. Thus, we can assume that we choose only one integer. Consider the sequence A%B, 2A%B, 3A%B,... Since (k + B)A%B = (ka + BA)%B = ka%b, this sequence has a period of B. Therefore, we can check the first B elements of this sequence by brute force. 2

10 C: Sentou After the i-th person pushes the switch, the i + 1-th person If the i+1-th person comes within T seconds, the water keeps emitting. If the i + 1-th person comes after at least T seconds, the water emits for T seconds and stops. Therefore, the answer is the sum of min(t, t i+1 t i ). 3

11 D: Simple Knapsack This problem is known as the knapsack problem, and it s hard to solve in general case. This time we use the constraint w 1 w i w Because of this, there are at most 4 possible weights for a single item. For each weight w, let s fix k w, the number of items of weight w we choose. Obviously, we should choose k w items greedily (in the descending order of values). Let A, B, C, D be the number of items of weights w 1, w 1 +1, w 1 +2, w 1 +3, respectively. This algorithm works in O(ABCD). In the worst case, this is (N/4) 4 = 25 4 =

12 E: Ball Coloring Let MIN = min(x 1, x 2,..., x n, y 1, y 2,..., y n ) MAX = max(x 1, x 2,..., x n, y 1, y 2,..., y n ). One of R min = MIN, B min = MIN will be satisfied, and one of R max = MAX, B max = MAX will be satisfied. Without loss of generality, we can consider the following two cases: R min = MIN&B max = MAX In this case we want to minimize R max and maximize B min. For each bag, we should color the ball with the larger integer blue, and color the other ball blue. R min = MIN&R max = MAX In this case we are only interested in blue balls (the value of B max B min. First, for each bag, we color the ball with the smaller integer blue, and sort the blue balls in ascending order. Call them z 1,..., z n (in ascending order). Then, for each i = 1,..., n, color z i red and color the opponent of z i blue. 5

13 F: Many Move Let dp[i][a][b] be the minimum cost required to process the first i queries such that the tokens are at a and b after the queries. This DP works in O(N 3 ). We ll improve this. Let dp[i][a] be the minimum cost required to process the first i queries such that the tokens are at a and x i after the queries. This DP works in O(N 2 ). Suppose that we have an array dp[i 1][1], dp[i 1][2],..., dp[i 1][n], and we want to convert it to the array dp[i][1], dp[i][2],..., dp[i][n]. The following operations are required: 1. Add x i 1 + xi to the whole array. 2. Compute min j=1,2,...,n (dp[i 1][j] + j x i ). This can be done by two RMQs: one of them holds the values of dp[i 1][j] j and the other one holds the values of dp[i 1][j] + j. 6

1 # include < stdio.h> 2 # include < string.h> 3 4 int main (){ 5 char str [222]; 6 scanf ("%s", str ); 7 int n= strlen ( str ); 8 for ( int i=n -2; i

1 # include < stdio.h> 2 # include < string.h> 3 4 int main (){ 5 char str [222]; 6 scanf (%s, str ); 7 int n= strlen ( str ); 8 for ( int i=n -2; i ABC066 / ARC077 writer: nuip 2017 7 1 For International Readers: English editorial starts from page 8. A : ringring a + b b + c a + c a, b, c a + b + c 1 # include < stdio.h> 2 3 int main (){ 4 int a,