Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
高橋君は体操の大会に参加しています。
大会では、5N 人の審査員それぞれが高橋君の演技に対して評点をつけ、それらを元に次のように高橋君の得点が決定されます。
- 高い評点をつけた方から順に N 人の審査員による評点を無効にする。
- 低い評点をつけた方から順に N 人の審査員による評点を無効にする。
- 残りの 3N 人の審査員による評点の平均点を高橋君の得点とする。
より厳密には、審査員がつけた得点の多重集合 S (|S|=5N) に対して次の操作を行って得られたものが高橋君の得点となります。
- 「S の最大の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
- 「S の最小の要素(複数ある場合はそのうちの 1 つ)を選び、S から取り除く」という操作を N 回繰り返す。
- S に残った 3N 個の要素の平均を高橋君の得点とする。
高橋君の演技に対する、i 人目 (1\leq i\leq 5N) の審査員の評点は X_i 点でした。 高橋君の得点を計算してください。
制約
- 1\leq N\leq 100
- 0\leq X_i\leq 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
X_1 X_2 \ldots X_{5N}
出力
高橋君の得点を出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる。
入力例 1
1 10 100 20 50 30
出力例 1
33.333333333333336
N=1 であるので、評点が高い方と低い方からそれぞれ 1 人ずつの審査員による評点を無効にします。
1 番高い評点をつけた審査員は 2 人目 (100 点) であるため、これを無効にします。
また、1 番低い評点をつけた審査員は 1 人目 (10 点) であるため、これも無効にします。
よって、最終的な平均点は \displaystyle\frac{20+50+30}{3}=33.333\cdots となります。
出力は、真の値との絶対誤差または相対誤差が 10^{-5} 以下であれば正解として扱われる事に注意してください。
入力例 2
2 3 3 3 4 5 6 7 8 99 100
出力例 2
5.500000000000000
N=2 であるので、評点が高い方と低い方からそれぞれ 2 人ずつの審査員による評点を無効にします。
1,2 番目に高い評点をつけた審査員は順に 10 人目 (100 点), 9 人目 (99 点) であるため、これを無効にします。
1 番低い評点をつけた審査員は 1,2,3 人目 (3 点) の 3 人がいるため、このうち 2 人を無効とします。
よって、答えは \displaystyle\frac{3+4+5+6+7+8}{6}=5.5 となります。
1 番低い評点をつけた 3 人のうちどの 2 人を無効にしたかは、答えに影響しない事に注意してください。
Score : 200 points
Problem Statement
Takahashi is participating in a gymnastic competition.
In the competition, each of 5N judges grades Takahashi's performance, and his score is determined as follows:
- Invalidate the grades given by the N judges who gave the highest grades.
- Invalidate the grades given by the N judges who gave the lowest grades.
- Takahashi's score is defined as the average of the remaining 3N judges' grades.
More formally, Takahashi's score is obtained by performing the following procedure on the multiset of the judges' grades S (|S|=5N):
- Repeat the following operation N times: choose the maximum element (if there are multiple such elements, choose one of them) and remove it from S.
- Repeat the following operation N times: choose the minimum element (if there are multiple such elements, choose one of them) and remove it from S.
- Takahashi's score is defined as the average of the 3N elements remaining in S.
The i-th (1\leq i\leq 5N) judge's grade for Takahashi's performance was X_i points. Find Takahashi's score.
Constraints
- 1\leq N\leq 100
- 0\leq X_i\leq 100
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
X_1 X_2 \ldots X_{5N}
Output
Print Takahashi's score.
Your answer will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.
Sample Input 1
1 10 100 20 50 30
Sample Output 1
33.333333333333336
Since N=1, the grade given by one judge who gave the highest grade, and one with the lowest, are invalidated.
The 2-nd judge gave the highest grade (100 points), which is invalidated.
Additionally, the 1-st judge gave the lowest grade (10 points), which is also invalidated.
Thus, the average is \displaystyle\frac{20+50+30}{3}=33.333\cdots.
Note that the output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}.
Sample Input 2
2 3 3 3 4 5 6 7 8 99 100
Sample Output 2
5.500000000000000
Since N=2, the grades given by the two judges who gave the highest grades, and two with the lowest, are invalidated.
The 10-th and 9-th judges gave the highest grades (100 and 99 points, respectively), which are invalidated.
Three judges, the 1-st, 2-nd, and 3-rd, gave the lowest grade (3 points), so two of them are invalidated.
Thus, the average is \displaystyle\frac{3+4+5+6+7+8}{6}=5.5.
Note that the choice of the two invalidated judges from the three with the lowest grades does not affect the answer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
人 1 、人 2 、\ldots 、人 N の N 人の人がルーレットの賭けに参加しました。 このルーレットの出目は、0 から 36 までの 37 個の整数のうちいずれかです。 i = 1, 2, \ldots, N について、人 i は 37 個の目のうち C_i 個の目 A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} に賭けました。
ルーレットが回され、出目は X でした。 X に賭けた人たちのうち、賭けた目の個数が最も少ない人たちの番号を昇順にすべて出力してください。
より形式的には、1 以上 N 以下の整数 i であって、下記の 2 つの条件をともに満たすものを昇順にすべて出力してください。
- 人 i は X に賭けている。
- 任意の j = 1, 2, \ldots, N について「人 j が X に賭けているならば、C_i \leq C_j 」が成り立つ。
出力するべき番号が 1 つも無い場合もあることに注意してください（入力例２を参照）。
制約
- 1 \leq N \leq 100
- 1 \leq C_i \leq 37
- 0 \leq A_{i, j} \leq 36
- 任意の i = 1, 2, \ldots, N について、A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} はすべて異なる。
- 0 \leq X \leq 36
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
C_1
A_{1, 1} A_{1, 2} \ldots A_{1, C_1}
C_2
A_{2, 1} A_{2, 2} \ldots A_{2, C_2}
\vdots
C_N
A_{N, 1} A_{N, 2} \ldots A_{N, C_N}
X
出力
出力するべき番号を昇順にすベて並べた列を、B_1, B_2, \ldots, B_K とする。 下記の形式にしたがい、1 行目には出力するべき番号の個数 K を、 2 行目には B_1, B_2, \ldots, B_K を空白区切りで、それぞれ出力せよ。
K B_1 B_2 \ldots B_K
入力例 1
4 3 7 19 20 4 4 19 24 0 2 26 10 3 19 31 24 19
出力例 1
2 1 4
ルーレットが回され、出目は 19 でした。 19 に賭けた人は人 1 、人 2 、人 4 の 3 人であり、それぞれが賭けた目の個数は 3, 4, 3 です。 よって、19 に賭けた人のうち、賭けた目の個数が最も少ない人は人 1 と人 4 の 2 人です。
入力例 2
3 1 1 1 2 1 3 0
出力例 2
0
ルーレットが回され出目は 0 でしたが、0 に賭けた人は一人もいないため、 出力するべき番号は 1 つもありません。
Score : 200 points
Problem Statement
N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.
The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.
More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:
- Person i has bet on X.
- For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.
Note that there may be no number to print (see Sample Input 2).
Constraints
- 1 \leq N \leq 100
- 1 \leq C_i \leq 37
- 0 \leq A_{i, j} \leq 36
- A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
- 0 \leq X \leq 36
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
C_1
A_{1, 1} A_{1, 2} \ldots A_{1, C_1}
C_2
A_{2, 1} A_{2, 2} \ldots A_{2, C_2}
\vdots
C_N
A_{N, 1} A_{N, 2} \ldots A_{N, C_N}
X
Output
Let B_1, B_2, \ldots, B_K be the sequence of numbers to be printed in ascending order. Using the following format, print the count of numbers to be printed, K, on the first line, and B_1, B_2, \ldots, B_K separated by spaces on the second line:
K B_1 B_2 \ldots B_K
Sample Input 1
4 3 7 19 20 4 4 19 24 0 2 26 10 3 19 31 24 19
Sample Output 1
2 1 4
The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.
Sample Input 2
3 1 1 1 2 1 3 0
Sample Output 2
0
The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
別世界の AtCoder で開催されている AtCoder Big Contest では、 10^{16} 問の問題が一度に出題されます。
問題の ID は 1 問目から順に A, B, ..., Z, AA, AB, ..., ZZ, AAA, ... と付けられています。
つまり、 ID は以下の順番で付けられています。
- 長さ 1 の英大文字からなる文字列を辞書順に並べたもの
- 長さ 2 の英大文字からなる文字列を辞書順に並べたもの
- 長さ 3 の英大文字からなる文字列を辞書順に並べたもの
- ...
このコンテストに含まれる問題の ID である文字列 S が与えられるので、それが何問目か答えてください。
制約
- S は AtCoder Big Contest に含まれる問題の ID として正しい
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
AB
出力例 1
28
ID が AB である問題は、 AtCoder Big Contest の 28 問目です。
入力例 2
C
出力例 2
3
ID が C である問題は、 AtCoder Big Contest の 3 問目です。
入力例 3
BRUTMHYHIIZP
出力例 3
10000000000000000
ID が BRUTMHYHIIZP である問題は、 AtCoder Big Contest の 10^{16} 問目、すなわち最終問題です。
Score : 300 points
Problem Statement
In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...
In other words, the IDs are given in the following order:
- the strings of length 1 consisting of uppercase English letters, in lexicographical order;
- the strings of length 2 consisting of uppercase English letters, in lexicographical order;
- the strings of length 3 consisting of uppercase English letters, in lexicographical order;
- ...
Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)
Constraints
- S is a valid ID of a problem given in AtCoder Big Contest.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
AB
Sample Output 1
28
The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.
Sample Input 2
C
Sample Output 2
3
The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.
Sample Input 3
BRUTMHYHIIZP
Sample Output 3
10000000000000000
The problem whose ID is BRUTMHYHIIZP is the
10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。 このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。
単純無向グラフとは
単純無向グラフとは、自己ループや多重辺を含まず、辺に向きの無いグラフのことをいいます。
閉路とは
単純無向グラフが閉路を持つとは、i \neq j ならば v_i \neq v_j を満たす長さ 3 以上の頂点列 (v_0, v_1, \ldots, v_{n-1}) であって、各 0 \leq i < n に対し v_i と v_{i+1 \bmod n} の間に辺が存在するものがあることをいいます。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- 与えられるグラフは単純
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
答えを出力せよ。
入力例 1
6 7 1 2 1 3 2 3 4 2 6 5 4 6 4 5
出力例 1
2
頂点 1 と頂点 2 を結ぶ辺・頂点 4 と頂点 5 を結ぶ辺の 2 本を削除するなどの方法でグラフが閉路を持たないようにすることができます。
1 本以下の辺の削除でグラフが閉路を持たないようにすることはできないので、2 を出力します。
入力例 2
4 2 1 2 3 4
出力例 2
0
入力例 3
5 3 1 2 1 3 2 3
出力例 3
1
Score : 300 points
Problem Statement
You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.
What is a simple undirected graph?
A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.
What is a cycle?
A cycle in a simple undirected graph is a sequence of vertices (v_0, v_1, \ldots, v_{n-1}) of length at least 3 satisfying v_i \neq v_j if i \neq j such that for each 0 \leq i < n, there is an edge between v_i and v_{i+1 \bmod n}.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- The given graph is simple.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print the answer.
Sample Input 1
6 7 1 2 1 3 2 3 4 2 6 5 4 6 4 5
Sample Output 1
2
One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.
Sample Input 2
4 2 1 2 3 4
Sample Output 2
0
Sample Input 3
5 3 1 2 1 3 2 3
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
キーエンスには N 個の部署があり、i\,(1 \leq i \leq N) 番目の部署には A_i 人の社員が所属しています。異なる部署に同じ社員が所属していることはありません。
キーエンスは、部署をまたいだ全社横断プロジェクトを計画しています。1 つのプロジェクトは K 個の相異なる部署から 1 人ずつ選出して作り、ちょうど K 人から構成されるようにします。
プロジェクトは最大でいくつ作れますか？ただし、1 人が複数のプロジェクトに参加することはできません。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{12}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
プロジェクトの個数の最大値を出力せよ。
入力例 1
3 3 2 3 4
出力例 1
2
3 個の部署それぞれから 1 人ずつ選出したプロジェクトを 2 つ作ることができます。
入力例 2
4 2 1 1 3 4
出力例 2
4
入力例 3
4 3 1 1 3 4
出力例 3
2
Score : 400 points
Problem Statement
KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.
The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.
At most how many projects can be made? No employee can participate in multiple projects.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the maximum possible number of projects.
Sample Input 1
3 3 2 3 4
Sample Output 1
2
There can be two projects, each composed of three employees from distinct departments.
Sample Input 2
4 2 1 1 3 4
Sample Output 2
4
Sample Input 3
4 3 1 1 3 4
Sample Output 3
2