AtCoder Daily Training MEDIUM 2024/11/19 19:30start

C - Adjacency Matrix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。

G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。

i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。

ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。

制約

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

出力

N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。

入力例 1

出力例 1

頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。

同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。

入力例 2

2
0 0
0 0

出力例 2

G に辺が存在しないこともあります。

入力例 3

出力例 3

Score: 150 points

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

Output

Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.

Sample Input 1

Sample Output 1

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

Sample Output 3

D - Append

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。

1 x: A の末尾に x を追加する。
2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。

制約

1 \leq Q \leq 100
1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数

入力

入力は以下の形式で標準入力から与えられる。

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

クエリは以下の 2 つのいずれかの形式である。

1 x

2 k

出力

2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

30
20

最初 A は空である。
1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。

Score: 200 points

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

1 x: Append x to the end of A.
2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

1 \leq Q \leq 100
In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
In the second type of query, k is a positive integer not greater than the current length of sequence A.

Input

The input is given from Standard Input in the following format:

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 x

2 k

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.

Sample Input 1

Sample Output 1

30
20

Initially, A is empty.
The first query appends 20 to the end of A, making A=(20).
The second query appends 30 to the end of A, making A=(20,30).
The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
The fourth query appends 40 to the end of A, making A=(20,30,40).
The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

E - Index × A(Continuous ver.)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

長さ M の A の連続部分列 B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。

注記

数列の連続部分列とは、数列の先頭から 0 個以上、末尾から 0 個以上の要素を削除して得られる列のことをいいます。

例えば (2, 3) や (1, 2, 3) は (1, 2, 3, 4) の連続部分列ですが、(1, 3) や (3,2,1) は (1, 2, 3, 4) の連続部分列ではありません。

制約

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
入力は全て整数。

入力

入力は以下の形式で標準入力から与えられる。

N M
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 2
5 4 -1 8

出力例 1

B=(A_3,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15 となります。16 以上の値を達成することはできないため、解は 15 です。

B=(A_1,A_4) などを選ぶことができないことに注意してください。

入力例 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

出力例 2

Score : 300 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

Sample Output 2

F - Circular Playlist

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 曲からなるプレイリストがあり、曲には 1, \dots, N の番号が付けられています。
曲 i の長さは A_i 秒です。

プレイリストを再生すると、曲 1、曲 2、\ldots、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。

プレイリストを再生してから T 秒後に流れているのはどの曲ですか？また、その曲が流れ始めてから何秒の時点ですか？
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。

制約

1 \leq N \leq 10^5
1 \leq T \leq 10^{18}
1 \leq A_i \leq 10^9
プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N T
A_1 \ldots A_N

出力

プレイリストを再生してから T 秒後に流れている曲の番号と、その曲が流れ始めてから何秒たったかを表す整数を空白区切りで出力せよ。

入力例 1

3 600
180 240 120

出力例 1

1 60

プレイリストを再生してからの様子は次のようになります。

0 秒後から 180 秒後まで曲 1 が流れる。
180 秒後から 420 秒後まで曲 2 が流れる。
420 秒後から 540 秒後まで曲 3 が流れる。
540 秒後から 720 秒後まで曲 1 が流れる。
720 秒後から 960 秒後まで曲 2 が流れる。
\qquad\vdots

600 秒後の時点で流れているのは曲 1 であり、流れ始めて 60 秒の時点です。

入力例 2

3 281
94 94 94

出力例 2

3 93

入力例 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

6 678912340

Score : 300 points

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

1 \leq N \leq 10^5
1 \leq T \leq 10^{18}
1 \leq A_i \leq 10^9
The playlist does not change songs at exactly T seconds after it starts playing.
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N T
A_1 \ldots A_N

Output

Print an integer representing the song that is playing at exactly T seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.

Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

From time 0 to time 180, song 1 plays.
From time 180 to time 420, song 2 plays.
From time 420 to time 540, song 3 plays.
From time 540 to time 720, song 1 plays.
From time 720 to time 960, song 2 plays.
\qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.

Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340

G - All Assign Point Add

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の数列 A = (A_1, A_2, \dots, A_N) が与えられます。

Q 個のクエリが与えられるので、順番にすべて処理してください。 q 番目 (1\leq q\leq Q) のクエリは以下の 3 つのいずれかの形式で、それぞれ次のようなクエリを表します。

1\ x _ q ： A のすべての要素に x _ q を代入する。
2\ i _ q\ x _ q ： A _ {i _ q} に x _ q を加える。
3\ i _ q ： A _ {i _ q} の値を出力する。

制約

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
q 番目 (1\leq q\leq Q) のクエリが 2 番目もしくは 3 番目の形式のとき、1 \leq i _ q \leq N
q 番目 (1\leq q\leq Q) のクエリが 1 番目もしくは 2 番目の形式のとき、0 \leq x _ q \leq 10^9
3 番目の形式のクエリが存在する
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

ただし、\operatorname{query}_q は q 番目のクエリであり、1 x, 2 i x, 3 i の形式のいずれかで与えられる。

出力

\operatorname{query}_q が 3 番目の形式であるような q\ (1\leq q\leq Q) の個数を X として、X 行出力せよ。 j\ (1\leq j\leq X) 行目にはそのようなクエリのうち j 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

1
8
5

はじめ、A=(3,1,4,1,5) です。それぞれのクエリでは、以下のような処理が行われます。

A_2=1 なので、1 を出力します。
A_3 に 4 を加えます。A=(3,1,8,1,5) となります。
A_3=8 なので、8 を出力します。
A の要素すべてに 1 を代入します。A=(1,1,1,1,1) となります。
A_3 に 4 を加えます。A=(1,1,5,1,1) となります。
A_3=5 なので、5 を出力します。

入力例 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

出力例 2

8000000000

A の要素の値が 32\operatorname{bit} 整数に収まらない可能性があることに注意してください。

入力例 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

出力例 3

Score : 400 points

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N.

Given Q queries, process all of them in order. The q-th (1\leq q\leq Q) query is in one of the following three formats, which represents the following queries:

1\ x _ q: assign x_q to every element of A.
2\ i _ q\ x _ q: add x_q to A _ {i _ q}.
3\ i _ q: print the value of A _ {i _ q}.

Constraints

1 \leq N \leq 2\times10^5
1 \leq Q \leq 2\times10^5
0 \leq A _ i \leq 10^9\ (1\leq i\leq N)
If the q-th (1\leq q\leq Q) query is in the second or third format, 1 \leq i _ q \leq N.
If the q-th (1\leq q\leq Q) query is in the first or second format, 0 \leq x _ q \leq 10^9.
There exists a query in the third format.
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N
Q
\operatorname{query}_1
\operatorname{query}_2
\vdots
\operatorname{query}_Q

Here, \operatorname{query}_q denotes the q-th query, which is in one of following formats: 1 x, 2 i x, and 3 i.

Output

Print X lines, where X is the number of q's (1\leq q\leq Q) such that \operatorname{query}_q is in the third format. The j-th (1\leq j\leq X) line should contain the answer to the j-th such query.

Sample Input 1

Sample Output 1

1
8
5

Initially, A=(3,1,4,1,5). The queries are processed as follows:

A_2=1, so print 1.
Add 4 to A_3, making A=(3,1,8,1,5).
A_3=8, so print 8.
Assign 1 to every element of A, making A=(1,1,1,1,1).
Add 4 to A_3, making A=(1,1,5,1,1).
A_3=5, so print 5.

Sample Input 2

1
1000000000
8
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
2 1 1000000000
3 1

Sample Output 2

8000000000

Note that the elements of A may not fit into a 32-bit integer type.

Sample Input 3

10
1 8 4 15 7 5 7 5 8 0
20
2 7 0
3 7
3 8
1 7
3 3
2 4 4
2 4 9
2 10 5
1 10
2 4 2
1 10
2 3 1
2 8 11
2 3 14
2 1 9
3 8
3 8
3 1
2 6 5
3 7

Sample Output 3