AtCoder Weekday Contest 0033 Beta

A - 答案の採点

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 233 点

問題文

高橋君は N 問からなるマークシート式のテストを受けました。各問題の解答は 0 または 1 のいずれかです。

高橋君の解答は長さ N の文字列 S で表されます。S の i 文字目が 1 ならば i 番目の問題に 1 と解答したことを、0 ならば 0 と解答したことを意味します。同様に、正解は長さ N の文字列 T で表されます。

高橋君は解答を提出する前に見直しをして、S の 0 個以上の文字を書き換えることで、不正解の問題数を K 問以下にしたいと考えています。

具体的には、S の各文字について、その文字を 0 から 1 に、または 1 から 0 に変更するか、そのままにするかを選びます。こうして得られた長さ N の文字列を S' とします。

S' の i 文字目と T の i 文字目が異なるような i （1 \leq i \leq N）の個数を不正解の問題数と呼びます。
S の i 文字目と S' の i 文字目が異なるような i （1 \leq i \leq N）の個数を書き換え回数と呼びます。

不正解の問題数が K 以下となるような S' は少なくとも 1 つ存在します（例えば S' = T とすれば不正解は 0 問です）。そのような S' の中での書き換え回数の最小値を求めてください。

制約

1 \leq N \leq 10^6
0 \leq K \leq N
N, K は整数
S は 0 と 1 のみからなる長さ N の文字列
T は 0 と 1 のみからなる長さ N の文字列

入力

N K
S
T

1 行目には、問題数を表す整数 N と、許容される不正解数の上限を表す整数 K が、スペース区切りで与えられる。
2 行目には、高橋君の解答を表す長さ N の文字列 S が与えられる。
3 行目には、正解を表す長さ N の文字列 T が与えられる。

出力

不正解の問題数を K 問以下にするために必要な書き換え回数の最小値を 1 行で出力せよ。

入力例 1

5 2
10100
01010

出力例 1

入力例 2

5 3
11001
10011

出力例 2

入力例 3

20 5
11111111110000000000
11111000001111100000

出力例 3

入力例 4

50 10
11010011100101101001110010011101010011100101101001
00101100011010010110001101100010101100011010010110

出力例 4

入力例 5

1 0
0
1

出力例 5

Score : 233 pts

Problem Statement

Takahashi took a multiple-choice test consisting of N questions. The answer to each question is either 0 or 1.

Takahashi's answers are represented by a string S of length N. If the i-th character of S is 1, it means he answered 1 for the i-th question; if it is 0, it means he answered 0. Similarly, the correct answers are represented by a string T of length N.

Before submitting his answers, Takahashi wants to review and rewrite 0 or more characters of S so that the number of incorrect answers is at most K.

Specifically, for each character of S, he chooses whether to change it from 0 to 1, from 1 to 0, or leave it as is. Let S' be the string of length N obtained in this way.

The number of indices i (1 \leq i \leq N) such that the i-th character of S' and the i-th character of T differ is called the number of incorrect answers.
The number of indices i (1 \leq i \leq N) such that the i-th character of S and the i-th character of S' differ is called the number of rewrites.

There exists at least one S' such that the number of incorrect answers is at most K (for example, setting S' = T gives 0 incorrect answers). Find the minimum number of rewrites among all such S'.

Constraints

1 \leq N \leq 10^6
0 \leq K \leq N
N, K are integers
S is a string of length N consisting only of 0 and 1
T is a string of length N consisting only of 0 and 1

Input

N K
S
T

The first line contains an integer N representing the number of questions and an integer K representing the upper limit on the number of allowed incorrect answers, separated by a space.
The second line contains a string S of length N representing Takahashi's answers.
The third line contains a string T of length N representing the correct answers.

Output

Print in one line the minimum number of rewrites needed to make the number of incorrect answers at most K.

Sample Input 1

5 2
10100
01010

Sample Output 1

Sample Input 2

5 3
11001
10011

Sample Output 2

Sample Input 3

20 5
11111111110000000000
11111000001111100000

Sample Output 3

Sample Input 4

50 10
11010011100101101001110010011101010011100101101001
00101100011010010110001101100010101100011010010110

Sample Output 4

Sample Input 5

1 0
0
1

Sample Output 5

B - 植物の温度管理

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は観葉植物を育てることが趣味で、自宅に多くの植物を置いています。

高橋君の家には N 個の部屋があり、それぞれの部屋にはエアコンが設置されています。i 番目の部屋の現在の室温は T_i 度です。

高橋君が育てている植物は、室温が L 度以上 R 度以下でないとうまく育ちません。そのため、植物を置く部屋の室温がこの範囲外の場合は、エアコンを使って室温を調整する必要があります。

i 番目の部屋にエアコンをかけると、その部屋の室温を好きな温度に変更できます。このとき、温度の変化量 1 度あたり 1 円の電気代がかかります。すなわち、室温を T_i 度から S 度に変更するコストは |T_i - S| 円です。室温がすでに L 度以上 R 度以下であれば、調整の必要はなくコストは 0 円です。

高橋君は N 個の部屋から異なる K 個の部屋を選び、それらの部屋すべての室温を L 度以上 R 度以下に調整して植物を置くことにしました。

K 個の部屋を適切に選んだとき、必要な電気代の総コストの最小値を求めてください。

制約

1 \leq K \leq N \leq 2 \times 10^5
-10^9 \leq L \leq R \leq 10^9
-10^9 \leq T_i \leq 10^9
入力はすべて整数

入力

N K L R
T_1 T_2 \ldots T_N

1 行目には、部屋の数を表す整数 N 、選ぶ部屋の数を表す整数 K 、適切な室温の下限を表す整数 L 、適切な室温の上限を表す整数 R が、スペース区切りで与えられる。
2 行目には、各部屋の現在の室温を表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。

出力

K 個の部屋を選んで、それらすべての室温を L 度以上 R 度以下に調整するために必要な電気代の総コストの最小値を 1 行で出力してください。

入力例 1

5 3 18 22
15 18 25 21 30

出力例 1

入力例 2

4 2 0 0
-5 7 0 3

出力例 2

入力例 3

8 5 -2 4
-10 -2 0 3 5 8 -1 12

出力例 3

入力例 4

18 10 100 130
80 95 99 100 101 110 120 130 131 140 150 70 85 128 129 90 105 160

出力例 4

入力例 5

1 1 -1000000000 -1000000000
1000000000

出力例 5

2000000000

Score : 300 pts

Problem Statement

Takahashi's hobby is growing houseplants, and he keeps many plants in his home.

Takahashi's house has N rooms, each equipped with an air conditioner. The current temperature of the i-th room is T_i degrees.

The plants Takahashi is growing cannot thrive unless the room temperature is at least L degrees and at most R degrees. Therefore, if the temperature of a room where plants are placed is outside this range, the air conditioner must be used to adjust the temperature.

When the air conditioner is used in the i-th room, the room temperature can be changed to any desired temperature. The electricity cost is 1 yen per 1 degree of temperature change. That is, the cost of changing the temperature from T_i degrees to S degrees is |T_i - S| yen. If the room temperature is already at least L degrees and at most R degrees, no adjustment is needed and the cost is 0 yen.

Takahashi will select K distinct rooms from the N rooms, adjust the temperatures of all selected rooms to be at least L degrees and at most R degrees, and place plants in them.

Find the minimum total electricity cost required when the K rooms are chosen optimally.

Constraints

1 \leq K \leq N \leq 2 \times 10^5
-10^9 \leq L \leq R \leq 10^9
-10^9 \leq T_i \leq 10^9
All inputs are integers

Input

N K L R
T_1 T_2 \ldots T_N

The first line contains four space-separated integers: N representing the number of rooms, K representing the number of rooms to select, L representing the lower bound of the suitable temperature, and R representing the upper bound of the suitable temperature.
The second line contains space-separated integers T_1, T_2, \ldots, T_N representing the current temperature of each room.

Output

Print in one line the minimum total electricity cost required to select K rooms and adjust all their temperatures to be at least L degrees and at most R degrees.

Sample Input 1

5 3 18 22
15 18 25 21 30

Sample Output 1

Sample Input 2

4 2 0 0
-5 7 0 3

Sample Output 2

Sample Input 3

8 5 -2 4
-10 -2 0 3 5 8 -1 12

Sample Output 3

Sample Input 4

18 10 100 130
80 95 99 100 101 110 120 130 131 140 150 70 85 128 129 90 105 160

Sample Output 4

Sample Input 5

1 1 -1000000000 -1000000000
1000000000

Sample Output 5

2000000000

C - 噂の拡散

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君の学校には N 人の生徒がおり、生徒には 1 から N までの番号が付けられています。生徒同士の友人関係が M 個与えられ、i 番目の友人関係は生徒 u_i と生徒 v_i が互いに友人であることを表します（友人関係は双方向です）。なお、同じ友人関係が複数回与えられることや、ある生徒が自分自身と友人であるような関係は存在しません。

はじめに、K 人の生徒 C_1, C_2, \ldots, C_K だけがある噂を知っている状態です。この初期状態から、噂は次のルールに従って日ごとに広がります。

> 判定： 各日の開始時点で、まだ噂を知らない生徒それぞれについて、その生徒の友人のうち噂を知っている人数を数えます。この人数が T 人以上であれば、その生徒はその日の終わりに新たに噂を知ります。

> 同時更新： その日に新たに噂を知る生徒が複数いる場合、それらは全員同時にその日の終わりに噂を知ります。ある生徒がその日の終わりに新たに噂を知ったとしても、それは同じ日の他の生徒の判定には影響しません。

この過程を、新たに噂を知る生徒がいなくなるまで毎日繰り返します。

最終的に噂を知っている生徒の人数を求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq K \leq N
1 \leq T \leq N
1 \leq C_i \leq N (1 \leq i \leq K)
C_i はすべて異なる
1 \leq u_i < v_i \leq N (1 \leq i \leq M)
(u_i, v_i) の組はすべて異なる
入力はすべて整数

入力

N M K T
C_1 C_2 \ldots C_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

1 行目には、生徒の数 N、友人関係の数 M、初めに噂を知っている生徒の数 K、噂が伝わるために必要な友人の人数の閾値 T が、スペース区切りで与えられる。
2 行目には、初めに噂を知っている生徒の番号 C_1, C_2, \ldots, C_K がスペース区切りで与えられる。
3 行目から M + 2 行目には、友人関係が M 行で与えられる。
2 + i 行目 (1 \leq i \leq M) には、i 番目の友人関係における生徒の番号 u_i と v_i がスペース区切りで与えられる。

出力

噂の拡散が収束した後に噂を知っている生徒の人数を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

入力例 5

1 0 1 1
1

出力例 5

Score : 366 pts

Problem Statement

There are N students in Takahashi's school, numbered from 1 to N. M friendship relations between students are given, where the i-th friendship relation indicates that student u_i and student v_i are friends with each other (friendships are bidirectional). Note that the same friendship relation is never given more than once, and no student is friends with themselves.

Initially, only K students C_1, C_2, \ldots, C_K know a certain rumor. Starting from this initial state, the rumor spreads day by day according to the following rules:

> Evaluation: At the beginning of each day, for each student who does not yet know the rumor, count the number of their friends who currently know the rumor. If this number is at least T, that student will newly learn the rumor at the end of that day.

> Simultaneous Update: If multiple students newly learn the rumor on a given day, they all learn it simultaneously at the end of that day. Even if a student newly learns the rumor at the end of a day, this does not affect the evaluation of other students on the same day.

This process is repeated every day until no new students learn the rumor.

Determine the number of students who know the rumor in the end.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq K \leq N
1 \leq T \leq N
1 \leq C_i \leq N (1 \leq i \leq K)
All C_i are distinct
1 \leq u_i < v_i \leq N (1 \leq i \leq M)
All pairs (u_i, v_i) are distinct
All input values are integers

Input

N M K T
C_1 C_2 \ldots C_K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

The first line contains the number of students N, the number of friendships M, the number of students who initially know the rumor K, and the threshold number of friends required for the rumor to spread T, separated by spaces.
The second line contains the student numbers C_1, C_2, \ldots, C_K of those who initially know the rumor, separated by spaces.
From the 3rd line to the (M + 2)-th line, M friendship relations are given.
The (2 + i)-th line (1 \leq i \leq M) contains the student numbers u_i and v_i of the i-th friendship relation, separated by spaces.

Output

Print the number of students who know the rumor after the spread has converged, in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

Sample Input 5

1 0 1 1
1

Sample Output 5

D - 最安通勤ルート

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は N 個の駅が M 本の路線で結ばれた鉄道ネットワークを利用して通勤しています。駅には 1 から N までの番号が付けられており、路線 i は駅 U_i と駅 V_i を双方向に結び、運賃が C_i 円かかります。

高橋君は駅 1 にある自宅の最寄り駅から、駅 N にある職場の最寄り駅まで毎日通勤する必要があります。高橋君が使える交通費の予算は K 円しかないため、運賃の合計が K 円以下となるルートを見つけなければなりません。

ここで、ルートとは、駅 1 から出発し路線を順に辿って駅 N へ到達する道順のことを指します。同じ駅を複数回訪れたり、同じ路線を複数回利用したりすることも許されます。ルートの運賃の合計とは、そのルートで利用した路線の運賃をすべて足し合わせたものです。ある路線を複数回利用した場合は、その回数分だけ運賃がかかります。

駅 1 から駅 N へ運賃の合計が K 円以下で到達できるルートが存在するならば、そのようなルートにおける運賃の合計の最小値を出力してください。そのようなルートが存在しない場合は -1 を出力してください。

制約

2 \leq N \leq 10^5
1 \leq M \leq 2 \times 10^5
1 \leq K \leq 10^9
1 \leq U_i, V_i \leq N
U_i \neq V_i
同じ 2 駅間を結ぶ路線が複数存在することもある
1 \leq C_i \leq 10^9
入力はすべて整数である

入力

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

1 行目には、駅の数を表す N 、路線の数を表す M 、高橋君の交通費の予算を表す K が、スペース区切りで与えられる。
2 行目から M + 1 行目では、路線の情報が M 行で与えられる。
1 + i 行目では、路線 i が結ぶ 2 つの駅 U_i , V_i と運賃 C_i がスペース区切りで与えられる。

出力

駅 1 から駅 N へ運賃の合計が K 円以下で到達できるルートが存在する場合、その運賃の合計の最小値を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

3 2 5
1 2 3
2 3 4

出力例 2

-1

入力例 3

出力例 3

Score : 400 pts

Problem Statement

Takahashi commutes using a railway network consisting of N stations connected by M lines. The stations are numbered from 1 to N. Line i bidirectionally connects station U_i and station V_i, with a fare of C_i yen.

Takahashi needs to commute every day from station 1, the nearest station to his home, to station N, the nearest station to his workplace. Since Takahashi's transportation budget is only K yen, he must find a route whose total fare is at most K yen.

Here, a route refers to a path starting from station 1 and following lines in sequence to reach station N. It is permitted to visit the same station multiple times or use the same line multiple times. The total fare of a route is the sum of the fares of all lines used in that route. If a line is used multiple times, the fare is charged for each use.

If there exists a route from station 1 to station N with a total fare of at most K yen, output the minimum total fare among all such routes. If no such route exists, output -1.

Constraints

2 \leq N \leq 10^5
1 \leq M \leq 2 \times 10^5
1 \leq K \leq 10^9
1 \leq U_i, V_i \leq N
U_i \neq V_i
There may be multiple lines connecting the same pair of stations
1 \leq C_i \leq 10^9
All input values are integers

Input

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

The first line contains N representing the number of stations, M representing the number of lines, and K representing Takahashi's transportation budget, separated by spaces.
From the 2nd line to the (M + 1)-th line, information about the M lines is given.
The (1 + i)-th line contains the two stations U_i, V_i connected by line i and the fare C_i, separated by spaces.

Output

If there exists a route from station 1 to station N with a total fare of at most K yen, output the minimum total fare in one line. If no such route exists, output -1 in one line.

Sample Input 1

Sample Output 1

Sample Input 2

3 2 5
1 2 3
2 3 4

Sample Output 2

-1

Sample Input 3

Sample Output 3

E - 飛び石の最小コスト

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は川を渡ろうとしています。川には一列に N 個の飛び石が並んでおり、左岸側から順に石 1, 石 2, \ldots, 石 N と番号が付けられています。高橋君は石 1 からスタートし、石 N に到達すればゴールです。

高橋君は現在いる石 i から、石 i+1, 石 i+2, \ldots, 石 \min(i+K,\, N) のいずれか 1 つへジャンプすることができます。つまり、一度のジャンプで進める石の番号の差は 1 以上 K 以下であり、必ず番号が増える方向にしか進めません。高橋君は最終的に石 N にちょうど着地しなければなりません。

各飛び石 i (1 \leq i \leq N) には正の整数値 A_i が設定されています。高橋君がある石に着地すると、その石の値が累計コストに加算されます。着地しなかった石の値は加算されません。スタート地点である石 1 の値 A_1 と、ゴール地点である石 N の値 A_N も、それぞれ着地時に加算されます。

高橋君が石 1 から石 N まで渡る経路のうち、累計コストが最小となるものを求め、その最小の累計コストを出力してください。

制約

2 \leq N \leq 10^6
1 \leq K \leq N - 1
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
入力はすべて整数である。

入力

N K
A_1 A_2 \ldots A_N

1 行目には、飛び石の個数を表す整数 N と、一度のジャンプで進める石の番号の差の最大値を表す整数 K が、スペース区切りで与えられる。
2 行目には、各飛び石の値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

石 1 から石 N まで渡るときの累計コストの最小値を 1 行で出力せよ。

入力例 1

5 2
1 3 2 4 1

出力例 1

入力例 2

6 3
10 1 1 1 1 10

出力例 2

入力例 3

10 3
5 8 3 7 2 9 1 6 4 3

出力例 3

入力例 4

20 4
3 9 1 8 2 7 4 6 5 10 1 3 8 2 7 5 9 1 6 4

出力例 4

入力例 5

2 1
1000000000 1000000000

出力例 5

2000000000

Score : 466 pts

Problem Statement

Takahashi is trying to cross a river. There are N stepping stones lined up in a row in the river, numbered stone 1, stone 2, \ldots, stone N in order from the left bank. Takahashi starts on stone 1 and reaches the goal when he arrives at stone N.

From his current stone i, Takahashi can jump to any one of stone i+1, stone i+2, \ldots, stone \min(i+K,\, N). In other words, the difference in stone numbers covered in a single jump is between 1 and K inclusive, and he can only move in the direction of increasing numbers. Takahashi must land exactly on stone N at the end.

Each stepping stone i (1 \leq i \leq N) has a positive integer value A_i assigned to it. When Takahashi lands on a stone, that stone's value is added to the cumulative cost. The values of stones he does not land on are not added. The value A_1 of the starting stone 1 and the value A_N of the goal stone N are also each added when he lands on them.

Among all paths Takahashi can take from stone 1 to stone N, find the one that minimizes the cumulative cost, and output that minimum cumulative cost.

Constraints

2 \leq N \leq 10^6
1 \leq K \leq N - 1
1 \leq A_i \leq 10^9 (1 \leq i \leq N)
All inputs are integers.

Input

N K
A_1 A_2 \ldots A_N

The first line contains an integer N representing the number of stepping stones and an integer K representing the maximum difference in stone numbers that can be covered in a single jump, separated by a space.
The second line contains integers A_1, A_2, \ldots, A_N representing the values of each stepping stone, separated by spaces.

Output

Output in one line the minimum cumulative cost when traveling from stone 1 to stone N.

Sample Input 1

5 2
1 3 2 4 1

Sample Output 1

Sample Input 2

6 3
10 1 1 1 1 10

Sample Output 2

Sample Input 3

10 3
5 8 3 7 2 9 1 6 4 3

Sample Output 3

Sample Input 4

20 4
3 9 1 8 2 7 4 6 5 10 1 3 8 2 7 5 9 1 6 4

Sample Output 4

Sample Input 5

2 1
1000000000 1000000000

Sample Output 5

2000000000