M-SOLUTIONS writer: yokozuna A: Sum of Interior Angles For International Readers: English editorial starts on page 7. N 180(N 2) C++ #i n

Size: px

Start display at page:

Download "M-SOLUTIONS writer: yokozuna A: Sum of Interior Angles For International Readers: English editorial starts on page 7. N 180(N 2) C++ #i n"

えりかこしの
4 years ago
Views:

1 M-SOLUTIONS writer: yokozuna A: Sum of Interior Angles For International Readers: English editorial starts on page 7. N 180(N 2) C++ #i n c l u d e <iostream > using namespace std ; i n t main ( ) { i n t N; c i n >> N; cout << (N 2) 180 << endl ; } 1

2 B: Sumo k 8 S x 7 YES 8 NO C++ #i n c l u d e <iostream > #i n c l u d e <s t r i n g > using namespace std ; i n t main ( ) { s t r i n g s ; c i n >> s ; i n t cnt = 0 ; f o r ( i n t i = 0 ; i < s. s i z e ( ) ; i ++){ i f ( s [ i ] == x ) cnt ++; } i f ( cnt <= 7) puts ( YES ) ; e l s e puts ( NO ) ; } 2

3 C: Best-of-(2n-1) X(M) M M N 1, 2N M X(M) = 0 M M 1 N 1 M M 1 N 1 M ( )( M 1 ( A ) N ( B ) M N ( A ) M N ( B ) ) N X(M) = + N 1 M ( ) Y (M) Y (M) = M C Y (0) = 0 M 1 Y (M) 1 Y (M 1) M Y (M) = M 2N 1 M=N X(M)Y (M) = Y (M) = 1 + C C C Y (M) + Y (M 1) Y (M) = C Y (M 1) + 1 Y (M) = Y (M 1) + C C = 2N 1 M=N 2N 1 M=N ( )( M 1 ( A ) N ( B ) M N ( A ) M N ( B ) ) N + M N 1 ( ) M 1 (A N B M N + A M N B N )M N 1 N 1 ( C) O(N) C 3

4 D: Maximum Sum of Minimum c 1 c 2 c N k T T U U k + 1 k c k+1 x 1 x 2 x N 1 x i c i+1 c 2 + c c N c 2 + c c N T 1 (e 1 ) c 1, c 2 k = 2, 3,..., N 1 e 1, e 2,..., e k T T e k e k c k+1 e i c i+1 O(N 2 ) 4

5 E: Product of Arithmetic Progression d = 1 x(x + 1)...(x + n 1) x x + n , (x + n 1)!/(x 1)! O(1) d = 0 (x n ). d 1 x/d, x/d + 1,..., x/d + (n 1) ( ) d n 5

6 F: Random Tournament 1 i < j N dpl[i][j] := i, i + 1,..., j i dpr[j][i] := i, i + 1,..., j j i dpl[i][n] = dpr[i][1] = true i, i + 1,..., j k (i k j) dpl[k][j] = dpr[k][i] = true dpl[i][j] i k dpl[k][j] = dpr[k][i + 1] = true k (i k j) k i + 1, i + 2,..., j dpl[i][j] = true dpl[i][j] = true k i, i + 1,..., j i i k 1, k 2,..., k t (k 1 < k 2 < < k t ) i k 1 k 2 k 3 k t i i 1 k k dpl[i][j] dpr[j][i] dpl[i][j] = k [i + 1, j], A i,k = 1 dpl[k][j] = true dpr[k][i + 1] = true dpr[j][i] = k [i, j 1], A k,i = 0 dpl[k][j 1] = true dpr[k][i] = true j i O(N 3 ) bitset 6

7 M-SOLUTIONS Programming Contest Editorial writer: yokozuna 57 June 1, 2019 A: Sum of Interior Angles The sum of the interior angles of a regular polygon with N sides is 180(N 2). A sample implementation in C++ follows: #i n c l u d e <iostream > using namespace std ; i n t main ( ) { i n t N; c i n >> N; cout << (N 2) 180 << endl ; } 7

8 B: Sumo If Takahashi can have 8 or more wins when he wins all the remaining matches, there is a possibility that he can participate in the next tournament. Conversely, if there is a possibility that Takahashi can participate in the next tournament, he can have 8 or more wins when he wins all the remaining matches. Thus, what we need to do is to check if he can have 8 or more wins when he wins all the remaining matches, which is equivalent to having less than 8 losses in the first k matches. Therefore, we can solve the problem by counting the occurrences of x in the string S, print YES if there are 7 or less x and print NO if there are 8 or more. A sample implementation in C++ follows: #i n c l u d e <iostream > #i n c l u d e <s t r i n g > using namespace std ; i n t main ( ) { s t r i n g s ; c i n >> s ; i n t cnt = 0 ; f o r ( i n t i = 0 ; i < s. s i z e ( ) ; i ++){ i f ( s [ i ] == x ) cnt ++; } i f ( cnt <= 7) puts ( YES ) ; e l s e puts ( NO ) ; } 8

9 C: Best-of-(2n-1) Let us first consider the case with no draws. Let X(M) denote the probability that the game is played exactly M times. If M N 1 or 2N M, X(M) = 0. Otherwise, the game will be played exactly M times if Takahashi has exactly N 1 wins in the first M 1 games and he also wins the M-th game or Aoki has exactly N 1 wins in the first M 1 games and he also wins the M-th game. Thus, X(M) = ( M 1 N 1 )( ( A ) N ( B ) M N ( A ) M N ( B ) ) N + Now, let us consider the case involving draws. Let Y (M) be the expected number of games played until there are M non-draw games, including draw games. Then, Y (M) = M. This is intuitive, and we can prove it as follows. C Y (0) = 0 holds. Let Mbe a positive integer. If the first game is drawn, the expected number of games played from now on is Y (M); If the first game is not drawn, the expected number of games played from now on is Y (M 1). Thus, for any positive integer M, It follows that Y (M) = M Therefore, the answer is 2N 1 M=N X(M)Y (M) = = Y (M) = 1 + C C. 2N 1 M=N 2N 1 M=N C C Y (M) + Y (M 1) Y (M) = C Y (M 1) + 1 Y (M) = Y (M 1) + C ( )( M 1 ( A ) N ( B ) M N ( A ) M N ( B ) ) N + M N 1 ( ) M 1 (A N B M N + A M N B N )M N 1 N 1 ( C) We can precompute the binomial coefficients and powers in the formula in O(N) time. C 9

10 D: Maximum Sum of Minimum We can assume that c 1 c 2 c N by sorting them in advance. Let us choose k of the edges in T, and let U be the subgraph of T consisting of those edges and their endpoints. Since U is a forest, it has k + 1 or more vertices. Thus, the minimum among the integers written on the k edges is c k+1 or smaller. It follows from this observation that, if we let x 1 x 2 x N 1 be the integers written on the edges in T, x i c i+1 holds. Thus, the score never exceeds c 2 + c c N. Conversely, we can make the score c 2 + c c N by writing the integers as follows: Choose an edge e 1 in T and write c 1 and c 2 on its endpoints. Do the following operation for k = 2, 3,..., N 1: We can choose an edge e k in T so that the subgraph of T consisting of e 1, e 2,..., e k and their endpoints. One of the endpoints of such an edge e k is still empty, and we write c k+1 on that endpoint. Then, c i+1 will be written on the edge e i when the score is evaluated. Since it takes only O(N 2 ) time to check all the edges each time we choose an edge, so we can naively implement this algorithm. 10

11 E: Product of Arithmetic Progression Notice that if all queries satisfy d = 1, we can easily solve the problem. In this case, we want to compute the product x(x + 1)...(x + n 1). If there is a multiple of 0003 between x and x + n 1, inclusive, the answer is zero. Otherwise, the answer is (x + n 1)!/(x 1)!, and by precomputing factorials (and their inverses) we can answer each query in O(1). How to solve the problem in general cases? In case d = 0, the answer is x n. Otherwise, notice that if we divide each term by d, we get an arithmetic progression with difference 1: x/d, x/d + 1,..., x/d + (n 1) Thus, the answer is the product of these n terms (which can be computed in the way described above) times d n. 11

12 F: Random Tournament For 1 i < j N, let dpl[i][j] := whether Person i may become the champion when only Person i, Person i + 1,..., Person j are considered dpr[j][i] := whether Person j may become the champion when only Person i, Person i + 1,..., Person j are considered Then, Person i may become the champion if and only if dpl[i][n] = dpr[i][1] = true. More generally, when only Person i, Person i + 1,..., Person j are considered, Person k (i k j) may become the champion if and only if dpl[k][j] = dpr[k][i] = true. Let us consider the transition of dpl[i][j]. First, if there exists k (i k j) such that Person i defeats Person k and dpl[k][j] = dpr[k][i + 1] = true, Person k may become the champion when only Person i + 1, Person i + 2,..., Person j are considered, so dpl[i][j] = true. Conversely, we will show that such k exists if dpl[i][j] = true. Let us only consider Person i, Personi + 1,..., Person j, and assume that they played matches so that Person i becomes the champion. Additionally, let Person k 1, Person k 2,..., Person k t (k 1 < k 2 < < k t ) be the persons defeated by Person i. Then, if we first play all the matches not involving Person i, then play a match between Person k 1 and Person k 2, then between the previous winner and Person k 3,..., then between the previous winner and Person k t, then between the previous winner and Person i, Person i can become the champion by just playing one match. Additionally, if we let Person k be the winner of the second last match, this k satisfies the condition above. Therefore, the transition of dpl[i][j] is: Similarly, the transition of dpr[j][i] is: dpl[i][j] = k [i + 1, j], A i,k = 1 dpl[k][j] = true dpr[k][i + 1] = true dpr[j][i] = k [i, j 1], A k,i = 0 dpl[k][j 1] = true dpr[k][i] = true By finding the values in ascending order of j i, we can compute the whole tables with time complexity O(N 3 ). Finally, we can do such a computation in parallel with bitsets. 12

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(

AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) 29 4 29 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 B: