CPSCO2019 Session4

A - Swimming

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

長さ L メートルのプールがあります。

ラスク君はプールの左端から泳ぎ始め、端まで泳いだらターンして逆方向に泳ぐことを繰り返します。

X メートル泳いだとき、ラスク君はプールの左端から何メートルのところにいるでしょうか。

制約

入力はすべて整数である。
1 \leq L \leq 100
1 \leq X \leq 1000

入力

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

L X

出力

X メートル泳いだときラスク君がいる位置がプールの左端から何メートルかを、1 行に出力せよ。

入力例 1

25 80

出力例 1

ラスク君は次のように行動します。

左端から右端まで 25 メートル泳ぐ。
ターンして、右端から左端まで 25 メートル泳ぐ。
ターンして、左端から右端まで 25 メートル泳ぐ。
ターンして、右端から 5 メートル泳ぐ。

このとき、ラスク君は左端から 20 メートルのところにいます。

入力例 2

50 100

出力例 2

入力例 3

20 15

出力例 3

B - Meeting

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

A社のあるプロジェクトチームにはリーダーと社員 1, 2, \ldots , N の合計 N+1 人が属しています。

D 日間のうち、リーダーは毎日出勤します。1, 2, \ldots , D 日目についての、リーダー以外の各社員の出勤予定はそれぞれ長さ N の文字列 S_1, S_2, \ldots , S_D で与えられます。i 日目に社員 j (1 \leq j \leq N) が出勤する場合 S_i の j 文字目は o であり、出勤しない場合 x です。

リーダーは、ある重要事項を他の社員たちに伝達するため、D 日間のうち 2 日を選んで会議を行おうとしています。

各社員は、その社員の出社日のみ会議に参加することができます。

重要事項ははじめリーダーのみが知っており、他の社員は会議に参加すると知ることができます。

リーダー以外の N 人のうち、最大で何人の社員に重要事項を伝達できるか求めてください。

制約

1 \leq N \leq 10
2 \leq D \leq 10
N, D は整数である。
S_i は長さ N の文字列である。
S_i の各文字は o または x である。

入力

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

N D
S_1
S_2
:
S_D

出力

D 日間のうち 2 日選んで会議を行ったとき、リーダー以外の N 人のうち最大何人の社員に重要事項を伝達できるかを、1 行に出力せよ。

入力例 1

2 3
xx
ox
oo

出力例 1

2 日目にリーダーと社員 1 で会議を行うと、社員 1 が重要事項を知ります。

次に 3 日目にリーダーと社員 1, 2 で会議を行うと、社員 2 が重要事項を知ります。

入力例 2

3 3
xox
oxx
xxo

出力例 2

2 日目にリーダーと社員 1 で会議を行うと、社員 1 が重要事項を知ります。

次に 3 日目にリーダーと社員 3 で会議を行うと、社員 3 が重要事項を知ります。

全員が重要事項を知っている状態にすることは不可能なので、2 と出力します。

入力例 3

5 4
oxxox
xoxxx
xxoxo
oxxxo

出力例 3

C - Make a Team

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

ラスク君の通う大学の競技プログラミング部には部員が N 人います。i 人目の部員のレートは R_i です。

大学対抗のプログラミングコンテストのために、部員から 3 人を選んでチームを 1 つ作ることになりました。

ここで、チーム内でレートが一番高い人と一番低い人のレートの差が D 以下になるようにします。

このようなチームの作り方が何通りあるか求めてください。

制約

入力はすべて整数である。
3 \leq N \leq 10^5
1 \leq D \leq 10^9
1 \leq R_i \leq 10^9

入力

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

N D
R_1 R_2 \ldots R_N

出力

条件を満たすチームの作り方が何通りあるかを出力せよ。

答えが 32 ビット整数型に収まらない場合があることに注意せよ。

入力例 1

5 400
300 700 1000 800 500

出力例 1

(部員 1, 部員 2, 部員 5), (部員 2, 部員 3, 部員 4), (部員 2, 部員 4, 部員 5) の 3 通りあります。

入力例 2

3 1000
2000 2000 4000

出力例 2

条件を満たすチームの作り方が 1 つもない場合もあります。

入力例 3

6 314159265
358979323 846264338 327950288 419716939 93751058 209749445

出力例 3

D - Boring Sequence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

ラスク君は長さ N の数列 a を持っています。

数列の退屈さとは、連続する部分列であってすべて同じ要素からなるものの長さの最大値のことをいいます。

ラスク君は、数列 a の要素を K 個まで任意の整数に書き換えて、退屈さをできるだけ小さくしようとしています。

達成できる退屈さの最小値を求めてください。

制約

入力はすべて整数である。
1 \leq K \leq N \leq 2\times 10^5
1 \leq a_i \leq N

入力

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

N K
a_1 a_2 \ldots a_N

出力

数列 a の要素を K 個以下書き換えたときの退屈さの最小値を出力せよ。

入力例 1

10 2
3 3 3 3 4 4 4 4 4 4

出力例 1

左から 1 番目の要素を 1 に、7 番目の要素を 2 に書き換えると、数列は

1, 3, 3, 3, 4, 4, 2, 4, 4, 4

となり、退屈さは 3 となります。

入力例 2

9 2
3 3 4 4 4 4 4 4 4

出力例 2

左から 4 番目の要素を 5 に、7 番目の要素を 1 に書き換えると、数列は

3, 3, 4, 5, 4, 4, 1, 4, 4

となり、退屈さは 2 となります。

入力例 3

5 5
3 1 4 1 5

出力例 3

全く書き換えを行わなくても構いません。

E - ox Concatenation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

ラスク君は o と x からなる長さ N の文字列 S を作ろうとしています。

そこで、ラスク君は文字列 ox を A 個、文字列 xo を B 個、文字 o を C 個、文字 x を D 個買ってきました。

ここで、2A+2B+C+D=N が成り立っています。

これらを好きな順番でつなげて文字列 S を作れるか判定してください。ただし、文字列 ox や文字列 xo をばらしたり反転させたりして用いてはいけません。

制約

1 \leq N \leq 2\times 10^5
0 \leq A, B, C, D \leq N
2A+2B+C+D=N
N, A, B, C, D は整数である。
S は長さ N の文字列である。
S の各文字は o または x である。

部分点

この問題には部分点が設定されている。

N \leq 4000 を満たす入力に正解すると、300 点が与えられる。

入力

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

N
S
A B C D

出力

文字列 S を作れるなら Yes、作れないなら No を出力せよ。

入力例 1

6
oxoxox
1 1 1 1

出力例 1

Yes

ox, o, xo, x の順でつなげればよいです。

入力例 2

6
oxoxox
2 1 0 0

出力例 2

No

入力例 3

7
xxxxxxx
1 1 1 2

出力例 3

No

入力例 4

9
xoxoxxoxo
2 2 0 1

出力例 4

Yes

F - Lost Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

出力する木の辺の重みに関する問題文の修正を行いました。ご迷惑をおかけして申し訳御座いません。(12:06)

問題文

ラスク君は木を持っていましたが、なくしてしまいました。

この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には 1 以上 10^9 以下の整数の重みが定まっていました。

頂点数は K 以上 1000 以下であり、1 \leq i, j \leq K に対し、頂点 i と頂点 j の距離は D_{ij} でした。ただし、頂点 i と頂点 j の距離とは、頂点 i と頂点 j を結ぶ単純パスに含まれる辺の重みの総和のことをいいます。

これらの情報から、ラスク君の持っていた木として考えられるものを一つ出力してください。なお、この問題で与えられる入力に対しては、いずれも条件に整合する木が少なくとも一つ存在することが保証されています。

制約

入力はすべて整数である。
2 \leq K \leq 300
i < j のとき 1 \leq D_{ij} \leq 10^9
D_{ij}=D_{ji}
D_{ii}=0
問題文の条件を満たす木が少なくとも 1 つ存在する。

入力

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

K
D_{11} D_{12} \ldots D_{1K}
D_{21} D_{22} \ldots D_{2K}
:
D_{K1} D_{K2} \ldots D_{KK}

出力

ラスク君の持っていた木として考えられるものを一つ、次の形式で出力せよ。

N
a_1 b_1 c_1
a_2 b_2 c_2
:
a_{N-1} b_{N-1} c_{N-1}

頂点数が N で、頂点 a_i と頂点 b_i を重み c_i の辺でつないでできるグラフが条件を満たす木になるとき、正解となる。

条件を満たす木が複数考えられる場合、どれを出力してもよい。

ただし、c_i の値は 1 以上 10^9 以下の整数である必要があります。

入力例 1

出力例 1

例えば、下図のような木が条件を満たします。

入力例 2

出力例 2

例えば、下図のような木が条件を満たします。

入力例 3

出力例 3