実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君には N 人の友達がいます。N 人の友達はそれぞれ、友達 1 、友達 2 、\ldots 、友達 N というあだ名で呼ばれています。
ある日、高橋君はある恥ずかしい秘密を、友達の一人である友達 X に知られてしまいました。
i = 1, 2, \ldots, N について、友達 i が高橋君の秘密を知ったとき、友達 A_i がまだ高橋君の秘密を知らなければ、友達 i は高橋君の秘密を友達 A_i にも教えてしまいます。
高橋君の秘密は最終的に何人の友達に知られることになるでしょうか？
制約
- 2 \leq N \leq 10^5
- 1 \leq X \leq N
- 1 \leq A_i \leq N
- A_i \neq i
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 A_2 \cdots A_N
出力
答えを出力せよ。
入力例 1
4 2 3 1 1 2
出力例 1
3
高橋君の秘密は以下の流れで友達 1 、友達 2 、友達 3 の 3 人に知れ渡ります。
- ある日、高橋君は秘密を友達 2 に知られてしまいました。
- 秘密を知った友達 2 は、その秘密を友達 1 に教えます。
- 秘密を知った友達 1 は、その秘密を友達 3 に教えます。
高橋君の秘密は最終的に 3 人の友達に知られることになるため、3 を出力します。
入力例 2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
出力例 2
7
Score : 200 points
Problem Statement
Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.
One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.
How many of Takahashi's friends will learn the secret in the end?
Constraints
- 2 \leq N \leq 10^5
- 1 \leq X \leq N
- 1 \leq A_i \leq N
- A_i \neq i
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
4 2 3 1 1 2
Sample Output 1
3
Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.
- One day, Takahashi let Friend 2 learn the secret.
- Friend 2 shares it with Friend 1.
- Friend 1 shares it with Friend 3.
In the end, three of his friends learn the secret, so we print 3.
Sample Input 2
20 12 7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10
Sample Output 2
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1,\ldots,N の番号のついた N 人の選手がゲームを行いました。選手 i のスコアは A_i であり、スコアが小さい方が上位になります。
ブービー賞に該当する選手、すなわち、下位から 2 番目の選手の番号を求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- A_i は相異なる
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 1 123 12345 12 1234 123456
出力例 1
3
6 人中 5 位になるのは、選手 3 です。
入力例 2
5 3 1 4 15 9
出力例 2
5
Score : 200 points
Problem Statement
N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.
The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- A_i are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 \ldots A_N
Output
Print the answer.
Sample Input 1
6 1 123 12345 12 1234 123456
Sample Output 1
3
It is Player 3 who ranks fifth among the six players.
Sample Input 2
5 3 1 4 15 9
Sample Output 2
5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
2 次元グリッド上に 2 つの図形 S と T があります。グリッドは正方形のマスからなります。
S は N 行 N 列のグリッド内にあり、S_{i,j} が # であるようなマス全体からなります。
T も N 行 N 列のグリッド内にあり、T_{i,j} が # であるようなマス全体からなります。
S と T を 90 度回転及び平行移動の繰り返しによって一致させることができるか判定してください。
制約
- 1 \leq N \leq 200
- S,T は
#と.のみからなる - S,T は 1 つ以上
#を含む
入力
入力は以下の形式で標準入力から与えられる。
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
出力
S と T を90 度回転及び平行移動の繰り返しによって一致させることができるとき Yes を、そうでないとき No を出力せよ。
入力例 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
出力例 1
Yes
S を左回りに 90 度回転させ、平行移動することで T に一致させることができます。
入力例 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
出力例 2
No
90 度回転と平行移動の繰り返しによって一致させることはできません。
入力例 3
4 #... ..#. ..#. .... #... #... ..#. ....
出力例 3
Yes
S 及び T は連結とは限りません。
入力例 4
4 #... .##. ..#. .... ##.. #... ..#. ....
出力例 4
No
回転や移動の操作は連結成分ごとにできるわけではなく、S,T 全体に対して行うことに注意してください。
Score : 300 points
Problem Statement
We have two figures S and T on a two-dimensional grid with square cells.
S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.
Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.
Constraints
- 1 \leq N \leq 200
- Each of S and T consists of
#and.. - Each of S and T contains at least one
#.
Input
Input is given from Standard Input in the following format:
N
S_{1,1}S_{1,2}\ldots S_{1,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
T_{1,1}T_{1,2}\ldots T_{1,N}
\vdots
T_{N,1}T_{N,2}\ldots T_{N,N}
Output
Print Yes if it is possible to exactly match S and T by 90-degree rotations and translations, and No otherwise.
Sample Input 1
5 ..... ..#.. .###. ..... ..... ..... ..... ....# ...## ....#
Sample Output 1
Yes
We can match S to T by rotating it 90-degrees counter-clockwise and translating it.
Sample Input 2
5 ##### ##..# #..## ##### ..... ##### #..## ##..# ##### .....
Sample Output 2
No
It is impossible to match them by 90-degree rotations and translations.
Sample Input 3
4 #... ..#. ..#. .... #... #... ..#. ....
Sample Output 3
Yes
Each of S and T may not be connected.
Sample Input 4
4 #... .##. ..#. .... ##.. #... ..#. ....
Sample Output 4
No
Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
英小文字のみからなる N 個の文字列 S_1,S_2,\dots,S_N が与えられます。
S_1,S_2,\dots,S_N から文字列を好きな個数選ぶことを考えます。
このとき、「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。
制約
- 1 \le N \le 15
- 1 \le K \le N
- N,K は整数
- S_i は英小文字からなる空でない文字列である。
- 1 \le i \le N を満たす整数 i に対し、S_i に同じ文字は 2 個以上含まれない。
- i \neq j ならば S_i \neq S_j である。
入力
入力は以下の形式で標準入力から与えられる。
N K S_1 S_2 \vdots S_N
出力
答えを出力せよ。
入力例 1
4 2 abi aef bc acg
出力例 1
3
S_1,S_3,S_4 を選んだ場合、a,b,c がちょうど 2 個の文字列に含まれます。
4 個以上の文字がちょうど 2 個の文字列に含まれるような選び方は存在しないため、答えは 3 です。
入力例 2
2 2 a b
出力例 2
0
同じ文字列を複数回選ぶことはできません。
入力例 3
5 2 abpqxyz az pq bc cy
出力例 3
7
Score : 300 points
Problem Statement
You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.
Consider choosing some number of strings from S_1,S_2,\dots,S_N.
Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."
Constraints
- 1 \le N \le 15
- 1 \le K \le N
- N and K are integers.
- S_i is a non-empty string consisting of lowercase English alphabets.
- For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
- If i \neq j, then S_i \neq S_j.
Input
Input is given from Standard Input in the following format:
N K S_1 S_2 \vdots S_N
Output
Print the answer.
Sample Input 1
4 2 abi aef bc acg
Sample Output 1
3
When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.
There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.
Sample Input 2
2 2 a b
Sample Output 2
0
You cannot choose the same string more than once.
Sample Input 3
5 2 abpqxyz az pq bc cy
Sample Output 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
長さ N の数列 A=(A_1,A_2,\ldots,A_N) と、整数 K が与えられます。
A の連続部分列のうち、要素の和が K になるものはいくつありますか？
すなわち、以下の条件を全て満たす整数の組 (l,r) はいくつありますか？
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
制約
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
6 5 8 -3 5 7 0 -4
出力例 1
3
(l,r)=(1,2),(3,3),(2,6) の 3 組が条件を満たします。
入力例 2
2 -1000000000000000 1000000000 -1000000000
出力例 2
0
条件を満たす (l,r) の組が 1 つも存在しないこともあります。
Score : 400 points
Problem Statement
Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.
How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?
- 1\leq l\leq r\leq N
- \displaystyle\sum_{i=l}^{r}A_i = K
Constraints
- 1\leq N \leq 2\times 10^5
- |A_i| \leq 10^9
- |K| \leq 10^{15}
- 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 answer.
Sample Input 1
6 5 8 -3 5 7 0 -4
Sample Output 1
3
(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.
Sample Input 2
2 -1000000000000000 1000000000 -1000000000
Sample Output 2
0
There may be no pair that satisfies the conditions.