実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 266 点
問題文
高橋君は N 個の文字列 S_1, S_2, \ldots, S_N のリストを持っています。高橋君はこれらの文字列を、先頭の文字ごとにグループに分類しようとしています。すなわち、先頭の文字が同じ文字列はすべて同じグループに属し、先頭の文字が異なる文字列は異なるグループに属します。
文字列の数が最も多いグループに含まれる文字列の数を求めてください。ただし、リスト中に同じ文字列が複数回現れる場合でも、それらを区別してそれぞれ 1 個ずつ数えるものとします。すなわち、グループに含まれる文字列の数は重複除去をせずに数えます。
制約
- 1 \leq N \leq 10^5
- S_i は英小文字のみからなる長さ 1 以上 20 以下の文字列である。
入力
N S_1 S_2 \vdots S_N
1 行目には、文字列の数を表す整数 N が与えられる。続く N 行のうち i 行目には、文字列 S_i が与えられる。
出力
文字列の数が最も多いグループに含まれる文字列の数を 1 行で出力せよ。
入力例 1
5 apple apricot banana avocado berry
出力例 1
3
入力例 2
6 cat car dog dove eel egg
出力例 2
2
入力例 3
12 alpha atom angle beta banana boat boat cat circle cider apple ant
出力例 3
5
入力例 4
30 moon map milk mango mint mouse melon mild sun sand sea stone smile sound soup apple arrow ant book bird blue cat cloud camel dog drum echo earth zebra zero
出力例 4
8
入力例 5
1 abcdefghijklmnopqrst
出力例 5
1
Score : 266 pts
Problem Statement
Takahashi has a list of N strings S_1, S_2, \ldots, S_N. He wants to classify these strings into groups based on their first character. That is, all strings with the same first character belong to the same group, and strings with different first characters belong to different groups.
Find the number of strings in the group that contains the most strings. Note that even if the same string appears multiple times in the list, each occurrence is counted separately as one string. In other words, the number of strings in a group is counted without removing duplicates.
Constraints
- 1 \leq N \leq 10^5
- S_i is a string consisting only of lowercase English letters with length between 1 and 20, inclusive.
Input
N S_1 S_2 \vdots S_N
The first line contains an integer N representing the number of strings. The i-th of the following N lines contains the string S_i.
Output
Print in one line the number of strings in the group that contains the most strings.
Sample Input 1
5 apple apricot banana avocado berry
Sample Output 1
3
Sample Input 2
6 cat car dog dove eel egg
Sample Output 2
2
Sample Input 3
12 alpha atom angle beta banana boat boat cat circle cider apple ant
Sample Output 3
5
Sample Input 4
30 moon map milk mango mint mouse melon mild sun sand sea stone smile sound soup apple arrow ant book bird blue cat cloud camel dog drum echo earth zebra zero
Sample Output 4
8
Sample Input 5
1 abcdefghijklmnopqrst
Sample Output 5
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は、横幅 W の壁にマスキングテープを貼って装飾をしようとしています。
高橋君は N 本のマスキングテープを横一直線に貼ります。壁の左端を位置 0 、右端を位置 W とします。
各テープ i （ 1 \leq i \leq N ）は長さ w_i を持ち、壁の左端からの位置 l_i から l_i + w_i までの区間に貼られます（ 0 \leq l_i かつ l_i + w_i \leq W ）。テープ同士は重なって貼られることもあります。
すべてのテープを貼り終えた後、壁のうち 少なくとも 1 本以上のテープが貼られている部分の長さの合計 を求めてください。
つまり、壁を 0 から W までの数直線とみなしたとき、 N 個の区間 [l_i, l_i + w_i] の 和集合の長さ を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W \leq 10^9
- 0 \leq l_i \leq W - 1 （ 1 \leq i \leq N ）
- 1 \leq w_i \leq W （ 1 \leq i \leq N ）
- l_i + w_i \leq W （ 1 \leq i \leq N ）
- 入力はすべて整数である。
入力
N W l_1 w_1 l_2 w_2 : l_N w_N
- 1 行目には、テープの本数を表す N 、壁の横幅を表す W が、スペース区切りで与えられる。
- 2 行目から N + 1 行目では、各テープの情報が N 行で与えられる。
- 1 + i 行目では、 i 本目のテープの貼り始め位置 l_i と長さ w_i が、スペース区切りで与えられる。
出力
壁のうち、少なくとも 1 本以上のテープが貼られている部分の長さの合計を 1 行で出力してください。
入力例 1
3 10 1 3 3 2 6 3
出力例 1
7
入力例 2
4 12 0 2 2 3 5 1 9 3
出力例 2
9
入力例 3
8 30 0 4 3 5 10 6 14 4 18 3 22 5 25 3 29 1
出力例 3
26
入力例 4
15 100 0 10 5 20 18 7 30 15 32 8 40 12 55 10 60 5 62 20 75 10 80 15 10 5 27 3 90 10 50 2
出力例 4
95
入力例 5
1 1 0 1
出力例 5
1
Score : 300 pts
Problem Statement
Takahashi is trying to decorate a wall of width W by applying masking tape.
Takahashi applies N strips of masking tape in a horizontal line. Let position 0 be the left edge of the wall and position W be the right edge.
Each tape i (1 \leq i \leq N) has length w_i and is applied to the interval from position l_i to position l_i + w_i from the left edge of the wall (0 \leq l_i and l_i + w_i \leq W). Tapes may overlap with each other.
After all tapes have been applied, find the total length of the parts of the wall that are covered by at least one strip of tape.
In other words, considering the wall as a number line from 0 to W, find the length of the union of the N intervals [l_i, l_i + w_i].
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq W \leq 10^9
- 0 \leq l_i \leq W - 1 (1 \leq i \leq N)
- 1 \leq w_i \leq W (1 \leq i \leq N)
- l_i + w_i \leq W (1 \leq i \leq N)
- All input values are integers.
Input
N W l_1 w_1 l_2 w_2 : l_N w_N
- The first line contains N, the number of tapes, and W, the width of the wall, separated by a space.
- From the 2nd line to the (N + 1)-th line, information about each tape is given over N lines.
- The (1 + i)-th line contains the starting position l_i and the length w_i of the i-th tape, separated by a space.
Output
Print in one line the total length of the parts of the wall that are covered by at least one strip of tape.
Sample Input 1
3 10 1 3 3 2 6 3
Sample Output 1
7
Sample Input 2
4 12 0 2 2 3 5 1 9 3
Sample Output 2
9
Sample Input 3
8 30 0 4 3 5 10 6 14 4 18 3 22 5 25 3 29 1
Sample Output 3
26
Sample Input 4
15 100 0 10 5 20 18 7 30 15 32 8 40 12 55 10 60 5 62 20 75 10 80 15 10 5 27 3 90 10 50 2
Sample Output 4
95
Sample Input 5
1 1 0 1
Sample Output 5
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は学校の園芸委員会で、花壇の管理を担当しています。
花壇には N 株の花が一列に植えられており、左から順に花 1、花 2、…、花 N と番号が付けられています。各花 i には品種ごとに定められた許容水分量 S_i があります。
高橋君はこれから M 回の水やり作業を行います。水やり作業を行う前の時点では、どの花もまだ水を受け取っていません。j 回目の作業では、花 L_j から花 R_j までのすべての花に、それぞれ水量 W_j の水を与えます。
すべての水やり作業が終了した後、花 i が受け取った水の総量（すなわち、花 i に対して行われたすべての水やり作業で与えられた水量の合計）が許容水分量 S_i より真に大きい場合、花 i は「根腐れ」を起こします。許容水分量以下であれば根腐れは起こしません。
根腐れを起こした花の株数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
- 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
- 入力はすべて整数
入力
N M S_1 S_2 \ldots S_N L_1 R_1 W_1 L_2 R_2 W_2 \vdots L_M R_M W_M
- 1 行目には、花の株数を表す N と、水やり作業の回数を表す M が、スペース区切りで与えられる。
- 2 行目には、各花の許容水分量 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
- 続く M 行のうち j 行目には、j 回目の作業で水を与える範囲の左端 L_j、右端 R_j、および各花に与える水量 W_j が、スペース区切りで与えられる。
出力
すべての水やり作業終了後に根腐れを起こした花の株数を 1 行で出力せよ。
入力例 1
5 2 10 5 8 12 3 1 3 4 2 5 6
出力例 1
3
入力例 2
7 4 15 20 10 25 30 5 18 1 4 8 3 6 12 2 5 5 4 7 10
出力例 2
3
入力例 3
10 6 100 50 80 120 60 90 40 110 70 55 1 5 30 3 8 25 6 10 35 2 4 40 5 7 20 1 10 10
出力例 3
4
Score : 366 pts
Problem Statement
Takahashi is in charge of managing the flower bed as part of the school's gardening committee.
The flower bed has N flowers planted in a row, numbered flower 1, flower 2, …, flower N from left to right. Each flower i has a moisture tolerance S_i determined by its species.
Takahashi will perform M watering operations. Before any watering operation is performed, no flower has received any water. In the j-th operation, he gives water of amount W_j to each of the flowers from flower L_j to flower R_j.
After all watering operations are completed, if the total amount of water received by flower i (that is, the sum of the water amounts given to flower i across all watering operations) is strictly greater than its moisture tolerance S_i, then flower i suffers "root rot." If the total amount is less than or equal to the moisture tolerance, root rot does not occur.
Find the number of flowers that suffer root rot.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
- 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
- All inputs are integers
Input
N M S_1 S_2 \ldots S_N L_1 R_1 W_1 L_2 R_2 W_2 \vdots L_M R_M W_M
- The first line contains N, the number of flowers, and M, the number of watering operations, separated by a space.
- The second line contains the moisture tolerances S_1, S_2, \ldots, S_N of each flower, separated by spaces.
- In the following M lines, the j-th line contains the left endpoint L_j, the right endpoint R_j of the range of flowers to water in the j-th operation, and the amount of water W_j given to each flower, separated by spaces.
Output
Print on a single line the number of flowers that suffer root rot after all watering operations are completed.
Sample Input 1
5 2 10 5 8 12 3 1 3 4 2 5 6
Sample Output 1
3
Sample Input 2
7 4 15 20 10 25 30 5 18 1 4 8 3 6 12 2 5 5 4 7 10
Sample Output 2
3
Sample Input 3
10 6 100 50 80 120 60 90 40 110 70 55 1 5 30 3 8 25 6 10 35 2 4 40 5 7 20 1 10 10
Sample Output 3
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君と青木君がカードを使ったゲームをします。
テーブルの上に N 枚のカードが一列に並べられています。左から i 番目のカードには整数 A_i が書かれています（A_i は負の値をとることもあります）。
ゲームのルールは以下の通りです：
- 高橋君が先手となり、高橋君と青木君が交互に手番を行う。
- 自分の手番では、現在の列の左端または右端のカードをちょうど 1 枚選んで取り、自分の手元に加えなければならない。取られたカードは列から除かれ、残りのカードはそのままの順序で列を成す。
- すべてのカードが取られたらゲーム終了となる。
各プレイヤーの 得点 は、そのプレイヤーが手元に集めたカードに書かれた整数の合計とします。両者はともに（自分の得点）-（相手の得点）を最大化するように最適に行動します。
両者が最適に行動したとき、高橋君の得点と青木君の得点をそれぞれ求めてください。
制約
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
N A_1 A_2 \ldots A_N
- 1 行目には、カードの枚数を表す整数 N が与えられる。
- 2 行目には、各カードに書かれた整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
高橋君の得点と青木君の得点を、この順にスペース区切りで 1 行に出力せよ。
入力例 1
4 1 2 3 4
出力例 1
6 4
入力例 2
5 3 -1 2 -5 4
出力例 2
-2 5
入力例 3
8 10 -3 7 2 -8 5 1 6
出力例 3
14 6
入力例 4
20 15 -7 23 -4 8 19 -12 6 3 -1 14 -9 7 25 -3 11 2 -18 20 5
出力例 4
77 27
入力例 5
1 -1000000000
出力例 5
-1000000000 0
Score : 400 pts
Problem Statement
Takahashi and Aoki play a game using cards.
There are N cards arranged in a row on the table. The i-th card from the left has an integer A_i written on it (A_i can be negative).
The rules of the game are as follows:
- Takahashi goes first, and Takahashi and Aoki take turns alternately.
- On their turn, a player must choose exactly 1 card from either the left end or the right end of the current row and add it to their hand. The chosen card is removed from the row, and the remaining cards maintain their order in the row.
- The game ends when all cards have been taken.
Each player's score is the sum of the integers written on the cards they have collected. Both players play optimally to maximize (their own score) - (the opponent's score).
When both players play optimally, find Takahashi's score and Aoki's score, respectively.
Constraints
- 1 \leq N \leq 3000
- -10^9 \leq A_i \leq 10^9
- All input values are integers.
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N, representing the number of cards.
- The second line contains the integers A_1, A_2, \ldots, A_N written on each card, separated by spaces.
Output
Print Takahashi's score and Aoki's score, in this order, separated by a space, on a single line.
Sample Input 1
4 1 2 3 4
Sample Output 1
6 4
Sample Input 2
5 3 -1 2 -5 4
Sample Output 2
-2 5
Sample Input 3
8 10 -3 7 2 -8 5 1 6
Sample Output 3
14 6
Sample Input 4
20 15 -7 23 -4 8 19 -12 6 3 -1 14 -9 7 25 -3 11 2 -18 20 5
Sample Output 4
77 27
Sample Input 5
1 -1000000000
Sample Output 5
-1000000000 0
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は図書館でアルバイトをしています。この図書館には N 個の収納スペースが左から一列に並んだ本棚があり、各収納スペースには1冊の本を入れることができます。収納スペースには左から順に 1 番、 2 番、 \ldots 、 N 番と番号が振られています。最初、すべての収納スペースは空です。
今日は新しく届いた M 冊の本を本棚に並べる作業を担当しています。各本を配置すべき収納スペースの番号はあらかじめ決められており、配置順序が i 番目 (1 \leq i \leq M) である本は収納スペース S_i に配置します。どの2冊の本も異なる収納スペースに配置されます。すなわち S_1, S_2, \ldots, S_M はすべて異なる値です。高橋君は 1 冊目、 2 冊目、 \ldots 、 M 冊目の順に本を1冊ずつ本棚に配置していきます。
作業を効率化するため、高橋君は各本を配置する際に、その本を置くべき収納スペースが「その時点で空いている収納スペースの中で左から何番目にあたるか」を事前に知りたいと考えています。
具体的には、i 番目の本を配置する直前の時点で空いている収納スペースを左から順に 1, 2, \ldots と数えたとき、収納スペース S_i は左から P_i 番目にあたります。各 i = 1, 2, \ldots, M について P_i を求めてください。
制約
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq N
- S_i はすべて異なる
- 入力はすべて整数
入力
N M S_1 S_2 \ldots S_M
- 1 行目には、収納スペースの総数を表す整数 N と、配置する本の冊数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各本を配置すべき収納スペースの番号 S_1, S_2, \ldots, S_M が、スペース区切りで与えられる。
- S_i は配置順序が i 番目である本の収納スペース番号を表す。
出力
P_1 P_2 \vdots P_M
- M 行にわたって出力せよ。
- i 行目には、 i 番目の本を配置する直前の時点で空いている収納スペースを左から順に数えたとき、収納スペース S_i が何番目であるかを表す整数 P_i を出力せよ。
入力例 1
5 3 3 1 5
出力例 1
3 1 3
入力例 2
10 6 2 7 4 1 10 5
出力例 2
2 6 3 1 6 2
入力例 3
20 10 15 3 18 7 1 20 10 5 12 8
出力例 3
15 3 16 6 1 15 7 3 7 4
Score : 433 pts
Problem Statement
Takahashi is working part-time at a library. The library has a bookshelf with N storage spaces arranged in a single row from left to right, and each storage space can hold one book. The storage spaces are numbered 1, 2, \ldots, N from left to right. Initially, all storage spaces are empty.
Today, Takahashi is in charge of placing M newly arrived books on the bookshelf. The storage space number where each book should be placed is predetermined: the book with placement order i (1 \leq i \leq M) is placed in storage space S_i. No two books are placed in the same storage space. That is, S_1, S_2, \ldots, S_M are all distinct values. Takahashi places the books one by one on the bookshelf in the order of the 1st book, the 2nd book, \ldots, the M-th book.
To make the task more efficient, Takahashi wants to know in advance, when placing each book, "among the storage spaces that are currently empty at that moment, what is the position from the left of the storage space where this book should be placed?"
Specifically, just before placing the i-th book, if we number the currently empty storage spaces 1, 2, \ldots from left to right, storage space S_i is the P_i-th from the left. Find P_i for each i = 1, 2, \ldots, M.
Constraints
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq S_i \leq N
- All S_i are distinct
- All input values are integers
Input
N M S_1 S_2 \ldots S_M
- The first line contains an integer N representing the total number of storage spaces and an integer M representing the number of books to be placed, separated by a space.
- The second line contains the storage space numbers S_1, S_2, \ldots, S_M where each book should be placed, separated by spaces.
- S_i represents the storage space number for the book with placement order i.
Output
P_1 P_2 \vdots P_M
- Output M lines.
- On the i-th line, output an integer P_i representing the position of storage space S_i when counting the empty storage spaces from left to right just before placing the i-th book.
Sample Input 1
5 3 3 1 5
Sample Output 1
3 1 3
Sample Input 2
10 6 2 7 4 1 10 5
Sample Output 2
2 6 3 1 6 2
Sample Input 3
20 10 15 3 18 7 1 20 10 5 12 8
Sample Output 3
15 3 16 6 1 15 7 3 7 4