パ研合宿2020　第1日「SpeedRun」

A - パ研合宿2020

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

この合宿の名前はパ研合宿2020ですが、今年は西暦で何年ですか？

入力

この問題では入力は与えられません。

出力

今年が西暦 n 年であるとして、n を出力してください。出力の最後に改行を忘れないでください。

出力例

\cdots あれ？

B - パ研合宿2403

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

筑駒パ研が成長し，全国有数の大企業と肩を並べる規模となった X 年，「パ研合宿X」が開催されることとなりました．

さて，「パ研合宿X」にはいくつかの団体を招待しなければなりません．担当者のTさんは，以下の規則に従って招待する団体の数を決定することにしました．

現在が X 年であるとして， X の 10 進表記を考える．
招待する団体数は，X の各桁に現れる数のうち最大のものである．

Tさんが招待する団体の数を求めてください．

制約

入力は全て整数である。
1000 \leq X \leq 9999

入力

入力は以下の形式で標準入力から与えられます.

出力

招待する団体の数を一行に出力してください.

出力の最後に改行を忘れないでください．

入力例1

出力例1

2 , 0 , 2 , 1 の中で，最大のものは 2 です.

入力例2

出力例2

入力例3

出力例3

パ研合宿 1736 には，7 団体が参加しました．

C - 皆勤賞

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

筑駒パ研は冬休み中、N 日に渡って活動しました。

i 日目の活動では k_i 人が参加して、参加者それぞれの名前は S_{i,1},\ S_{i,2},\ldots,\ S_{i,k_i} でした。

このとき、皆勤賞である、即ち N 日間の活動全てに参加した部員は何人いたでしょうか？ただし、同じ名前を持つ部員は存在しないものとします。

制約

1\leq N\leq100
1\leq k_i\leq100
1\leq|S_{i,j}|\leq10
S_{i,j}≠S_{i,k}\ (j≠k)
N,\ k_i は全て整数
S_{i,j} は英小文字のみからなる

入力

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

\(N\)
\(k_1\)
\(S_{1,1}\) \(S_{1,2}\) \(\ldots\) \(S_{1,k_1}\)
\(k_2\)
\(S_{2,1}\) \(S_{2,2}\) \(\ldots\) \(S_{2,k_2}\)
\(⋮\)
\(k_N\)
\(S_{N,1}\) \(S_{N,2}\) \(\ldots\) \(S_{N,k_N}\)

出力

皆勤賞である部員の人数を出力してください。出力の最後に改行を忘れないでください。

入力例1

2
2
kaage penguinman
2
penguinman rho

出力例1

皆勤賞なのは penguinman のみなので、1 を出力します。

入力例2

3
1
penguinman
1
kaage
1
rho

出力例2

1 人も皆勤賞がいない場合もあります。

入力例3

3
3
a b c
2
a ba
3
a ba abc

出力例3

おかしな名前のパ研部員もいるものです。

D - 立方体を壊せ！

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

1辺の長さが N の立方体があります．立方体のある頂点は (0,0,0) にあり，全ての辺は x 軸, y 軸, z 軸のいずれかに平行です．

また，立方体の周および内部の任意の点において，座標を (x,y,z) としたとき, 0 \leq x かつ 0 \leq y かつ 0 \leq z を満たします．

この空間を，x+y+z=K を満たす平面 \alpha で切断します．切断後の立方体で，点 (0,0,0) を含む方の体積を 6 倍した値を求めてください．この値が整数となることは示せます．

制約

入力は全て整数である。
1 \leq N \leq 1000
1 \leq K \leq 1000

入力

入力は以下の形式で標準入力から与えられます.

\(N\) \(K\)

出力

切断後の体積の 6 倍を一行に出力してください．

出力の最後に改行を忘れないでください．

入力例1

3 1

出力例1

切断後の体積を求める部分は，三角錐になります．体積は\frac{1}{6}なので，6倍して 1 を出力します．

入力例2

3 4

出力例2

入力例3

3 100

出力例3

切断面が立方体を通らないかもしれません．

E - Amary

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

penguinman は 2 つの正整数 A,\ B を持っていましたが、失くしてしまいました。彼曰く、A,\ B は以下の性質を持っていたそうです。

A を B で割った余りが X
B を A で割った余りが Y
1 \leq A,\ B\leq10^{18}
A,\ B は共に整数

彼の証言に合致する A,\ B の組が存在するか判定し、存在するならあり得るものを 1 つ構築してください。

制約

入力は全て整数である。
0\leq X,\ Y\leq10^9

入力

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

\(X\) \(Y\)

出力

証言に合致する A,\ B の組が存在しない場合、-1 を出力してください。

存在する場合、あり得る A,\ B の組を空白区切りで出力してください。

答えが複数存在する場合いずれを出力しても構いません。

入力例1

10 9

出力例1

10 19

10 を 19 で割った余りは 10、19 を 10 で割った余りは 9 なのでこれは証言に合致します。この他に (10,\ 29) を出力しても正解となります。

入力例2

10 10

出力例2

-1

彼の証言に合致する (A,\ B) の組は存在しません。

F - Fibonaccyan

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

penguinman はフィボナッちゃんに恋をしました。

フィボナッちゃんがある正整数 P を好きなことを知った penguinman は、F_i が P で割り切れる最小の正整数 i を見つけ、プレゼントすることにしました。ここで、F は以下のような漸化式で表される数列です。

F_1=F_2=1
F_{i+2}=F_{i+1}+F_i\ (1\leq i)

penguinman のためにそのような整数 i を見つけるか、そのような i が存在しないことを教えてあげてください。

制約

入力は全て整数である。
1\leq P\leq3000

入力

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

出力

問題文中の条件を満たす整数 i が存在しない場合、-1 を出力してください。

存在する場合、i を出力してください。

出力の最後に改行を忘れないでください。

入力例1

出力例1

F_1=1,\ F_2=1,\ F_3=2,\ F_4=3 より、F_i が 3 で割り切れる最小の i は 4 です。

入力例2

出力例2

入力例3

出力例3

G - 同意書

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

パ研合宿に参加するには、保護者の同意書が必要です。合宿に参加する人は 1 人 1 枚、同意書を提出しなければなりません。

今年のパ研合宿には N 人の人が参加します。各参加者には、1 から N までの番号が振られています。

ところで、Rho さん曰く、i=1,\ 2,\ldots,\ M について、以下のことが成り立っているそうです。

参加者 l_i,\ l_i+1,\ldots,\ r_i のうち x_i 人が同意書を既に提出している。

Rho さんの発言に矛盾がないか判定した上で、なければ既に同意書を出している人の数の最大値を求めてください。

制約

入力は全て整数である。
1\leq N\leq14
1\leq M\leq N(N+1)/2
1\leq l_i\leq r_i\leq N
0\leq x_i\leq r_i-l_i+1
(l_i,\ r_i)≠(l_j,\ r_j)(i≠j)

入力

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

\(N\) \(M\)
\(l_1\) \(r_1\) \(x_1\)
\(l_2\) \(r_2\) \(x_2\)
\(⋮\)
\(l_M\) \(r_M\) \(x_M\)

出力

Rho さんの発言に矛盾がないなら既に同意書を出している人の数の最大値を、矛盾があるなら -1 を出力してください。出力の最後に改行を忘れないでください。

入力例1

3 2
1 2 1
1 1 0

出力例1

Rho さんの証言に矛盾しないのは、以下の 2 通りです。

参加者 2,\ 3 が既に同意書を出している。
参加者 2 が既に同意書を出している。

既に同意書を出している人の数が最大となるのは前者で、その数は 2 です。よって 2 を出力します。

入力例2

4 2
1 3 0
1 2 1

出力例2

-1

Rho さんの発言に矛盾があります。

入力例3

5 2
1 3 2
3 4 2

出力例3

H - その計算、合ってますか？

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

penguinman は非負整数からなる空でない多重集合を持っています。彼が計算したところ、持っている集合の要素たちの

bit ごとの論理和は A
bit ごとの論理積は B
bit ごとの排他的論理和は C

になるそうです。

彼は自分の計算に自信がないので、間違っていないかあなたに確認してもらうことにしました。

T 個のテストケースが与えられるので、そのそれぞれについて、penguinman の発言に矛盾しない非負整数の多重集合が存在するか判定してください。

論理和の定義はこちらを、論理積の定義はこちらを、排他的論理和の定義はこちらを参照してください。

制約

入力は全て整数である。
1\leq T\leq10^4
0\leq A,\ B,\ C<2^{60}

入力

入力は以下の形式で標準入力から与えられます。 i 個目のテストケースにおける A,\ B,\ C を A_i,\ B_i,\ C_i としています。

\(T\)
\(A_1\) \(B_1\) \(C_1\)
\(A_2\) \(B_2\) \(C_2\)
\(⋮\)
\(A_T\) \(B_T\) \(C_T\)

出力

i 行目には i 個目のテストケースに対する答えを出力してください。

penguinman の発言に矛盾しない集合が存在すれば Yes を、存在しなければ No を出力してください。最後に改行してください。

入力例1

出力例1

Yes
No
Yes
No

1 つ目のテストケースでは、\{1,\ 3\} が条件を満たします。 3 つ目のテストケースでは、\{3,\ 3\} が条件を満たします。逆にその他のケースでは、条件を満たす集合が存在しません。

入力例2

10
4294950654 128 1515558086
3651343388 2076315599 1067568134
1006034671 154158080 851876591
4226809790 10486016 870489910
4005491433 1115853312 2889638121
4276043775 68162562 3026001755
2934431727 2822915648 111516079
155997896 3325455178 1339093083
1410500136 1501974124 3058302659
4226801641 2709524480 2846154689

出力例2

Yes
No
Yes
Yes
Yes
Yes
Yes
No
No
Yes

I - くねくね

Time Limit: 3.5 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

縦 H マス、横 W マスの H×W マスからなる迷路があります。上から i 行目、左から j 列目のマス (i,\ j) は、S_{i,j} が # のとき壁であり、. のとき道です。

マス (sx,\ sy) にうなぎがいて、マス (gx,\ gy) まで移動しようとしています。うなぎは 1 回の移動で、今いるマスと隣接する道マスに移動することができます。この際、迷路の外への移動はできません。

うなぎはくねくね動くのが好きです。そこで、迷路をプレイする際に以下の制限を設けることにしました。

i 回目の移動で上下に移動した場合、i+1 回目の移動では左右に移動しなければならない。
i 回目の移動で左右に移動した場合、i+1 回目の移動では上下に移動しなければならない。
最初の移動では、どの方向にも動くことができる。

うなぎはこの制限を守った上で、マス (gx,\ gy) まで移動できるでしょうか？移動できるか判定した上で、移動できる場合は必要な移動回数の最小値を求めてください。

制約

1\leq H,\ W\leq2000
1\leq sx,\ gx\leq H
1\leq sy,\ gy\leq W
S_{i,j} は # か .
S_{sx,sy} と S_{gx,gy} は .
(sx,\ sy)≠(gx,\ gy)
H,\ W,\ sx,\ sy,\ gx,\ gy は整数

入力

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

\(H\) \(W\)
\(sx\) \(sy\) \(gx\) \(gy\)
\(S_{1,1}\) \(S_{1,2}\) \(\ldots\) \(S_{1,W}\)
\(S_{2,1}\) \(S_{2,2}\) \(\ldots\) \(S_{2,W}\)
\(⋮\)
\(S_{H,1}\) \(S_{H,2}\) \(\ldots\) \(S_{H,W}\)

出力

うなぎがマス (gx,\ gy) まで移動できる場合は移動回数の最小値を、移動できない場合は -1 を出力してください。出力の最後に改行を忘れないでください。

入力例1

2 3
1 1 1 3
...
..#

出力例1

(1,\ 1)\ →\ (2,\ 1)\ →\ (2,\ 2)\ →\ (1,\ 2)\ →\ (1,\ 3) と移動するのが最適です。

入力例2

3 4
1 1 3 4
....
.#..
....

出力例2

-1

どう移動してもマス (3,\ 4) まで移動できません。

入力例3

5 7
4 1 5 4
.#..#..
#....#.
...#..#
.#.....
..#..#.

出力例3

J - Output-only

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

大変です！パ研王国にモンスターカアゲが現れました！モンスターカアゲは人を襲うことがあるため、退治しなければなりません。

幸いにも、スパイである penguinman が以下の情報を入手しました。

モンスターカアゲは、10^5 種類の直角三角形を投げつけると倒すことができる。

モンスターカアゲを倒すために、10^5 種類の直角三角形を生成しましょう！

形式的には、以下の条件を全て満たす正整数の組 (a,\ b,\ c) を 10^5 種類生成してください。

1\leq a\leq b\leq c\leq 10^{18}
a^2+b^2=c^2
a,\ b,\ c の最大公約数は 1

入力

この問題では入力は与えられません。

出力

10^5 行に渡って、問題文中の条件を満たす (a,\ b,\ c) の組をこの順で空白区切りで出力してください。

出力される (a,\ b,\ c) の組は互いに相異なっている必要があります。

出力例

3 4 5
5 12 13
8 15 17

このような形式で出力してください。なお、出力される (a,\ b,\ c) の数が足りないのでこの出力は不正解となります。

K - Gcd of Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

penguinman は長さN の数列 A を持っていますが、サイズが大きすぎるので長さが K になるように圧縮することにしました。

具体的には、A を K 個の連続する部分列 B_1,\ B_2,\ldots,\ B_K に切り分けた上で、新たに (B_1 に含まれる要素の総和),\ (B_2 に含まれる要素の総和),\ldots,\ (B_K に含まれる要素の総和) を要素に持つ数列 C を生成することにしました。

ところで、penguinman はある数列 X を持っているとき、X の全要素の最大公約数が大きければ大きいほど嬉しくなります。

うまく数列を圧縮することで、圧縮したあとの数列 C に含まれる要素の最大公約数は最大でいくつになりますか？

K=1,\ 2,\ \ldots,\ N についてこの問題を解いてください。

制約

入力は全て整数である。
1\leq N\leq300
1\leq A_i\leq300

入力

入力は以下の形式で標準入力から与えられます。(10:38 修正)

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

出力

N 行に渡って出力してください。 i 行目には K=i のときの答えを出力してください。最後に改行してください。

入力例1

3
1 2 3

出力例1

6
3
1

K=1 のとき、B_1=\{1,\ 2,\ 3\} と切り分けるしかありません。圧縮後の数列 C は \{6\} となり、その最大公約数は 6 です。 K=2 のとき、B_1=\{1,\ 2\},\ B_2=\{3\} と切り分けるか B_1=\{1\},\ B_2=\{2,\ 3\} と切り分けるかの 2 通りがあります。圧縮後の数列 C はそれぞれ \{3,\ 3\},\ \{1,\ 5\} となり、最大公約数は 3,\ 1 です。最大値を取っているのは前者の 3 なので、3 を出力します。 K=3 のとき、B_1=\{1\},\ B_2=\{2\},\ B_3=\{3\} と切り分けるしかありません。圧縮後の数列 C は \{1,\ 2,\ 3\} となり、その最大公約数は 1 です。

入力例2

6
10 36 28 91 58 11

出力例2

入力例3

10
48 33 57 91 70 63 51 100 300 234

出力例3

L - のびたす

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

筑駒 71 期の数学の授業では、「のびたす」という演算が登場しました。 x のびたす y は、x,\ y を文字列として見て連結する操作を表します。

例えば、10 のびたす 20=1020 です。ある正整数 x に対して、i=1,\ 2,\ldots,\ Q について以下の操作のいずれか片方を選んで行うことを考えます。

x を x+A_i で置き換える
x を x のびたす A_i で置き換える

操作の仕方は 2^Q 通りありますが、それら全てについて最終的な x を求め、その総和を 10^9+7 で割った余りを求めてください。

制約

入力は全て整数である。
1\leq Q\leq10^5
1\leq x\leq10^9
1\leq A_i\leq10^9

入力

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

\(Q\) \(x\)
\(A_1\)
\(A_2\)
\(⋮\)
\(A_Q\)

出力

最終的な x の総和を 10^9+7 で割った余りを出力してください。出力の最後に改行を忘れないでください。

入力例1

1 3
10

出力例1

以下の 2 通りの操作法があります。

1 回目の操作で x を x+A_1 で置き換える。最終的な x は 3+10=13 となる。
1 回目の操作で x を x のびたす A_1 で置き換える。最終的な x は 3 のびたす 10=310 となる。

これらの総和は 323 なので、323 を出力します。

入力例2

出力例2

116122282

入力例3

出力例3

986794595

M - 貢ぎ物

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

ペンギンは N 個の正整数 A_1,\ A_2,\ldots,\ A_N が入った箱を持っています。彼はこの箱に対して、以下の操作を 0 回以上好きなだけ行うことができます。

箱から好きな要素を重複を許して 2 つ選び、それらの bit ごとの論理和を箱に加える。選んだ 2 整数は箱に入ったままである。

ペンギンはこの操作を繰り返したあと、持っている箱を kaage にプレゼントすることにしました。

kaage は色んな種類の整数を見るのが好きなので、箱に入っている整数の種類が多ければ多いほど喜びます。

ペンギンは上記の操作を繰り返すことで、箱に入っている整数の種類数をいくつまで増やせるでしょうか？

論理和の定義はこちらを参照してください。

制約

入力は全て整数である。
1\leq N\leq2×10^5
1\leq A_i<2^{20}

入力

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

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

出力

最終的に箱に入っている整数の種類数の最大値を出力してください。出力の最後に改行を忘れないでください。

入力例1

2
1 2

出力例1

1 と 2 を選んで操作を行うと、箱の中身は \{1,\ 2,\ 3\} になります。これ以上箱に入っている整数の種類数を増やすことはできないので、答えは 3 です。

入力例2

6
1 4 1 3 1 17

出力例2

箱に入っている整数が互いに相異なるとは限りません。

入力例3

10
9321 547 38219 57491 212 8724 59243 8243 39842 982

出力例3

N - 背の順

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 人のパ研部員が左右一列に並んでいます。左から i 番目のパ研部員の身長は A_i です。

あなたの仕事は、以下の操作を 0 回以上繰り返してパ研部員たちが背の順で並んでいる、即ち任意の i\ (1\leq i\leq (列にいる部員の数)-1) に対して (左から i 番目にいる部員の身長)<(左から i+1 番目にいる部員の身長) が成り立つようにすることです。

今列にいるパ研部員の数を M として、整数 l,\ r\ (1\leq l\leq r\leq M) を選ぶ。選んだ時点で左から l 番目にいる部員の身長を L、r 番目にいる部員の身長を R としたとき、コスト L+R を払って左から l,\ l+1,\ldots,\ r 番目のパ研部員を列から取り除く。

あなたは仕事を達成するために、最小で合計いくらのコストを払う必要がありますか？

列に誰もいない状態も背の順で並んでいると見なし、また、操作を繰り返す間部員の身長は変化しません。

制約

入力は全て整数である。
1\leq N\leq2×10^5
1\leq A_i\leq N
A_i≠A_j\ (i≠j)

入力

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

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

出力

払うコストの総和の最小値を出力してください。出力の最後に改行を忘れないでください。

入力例1

4
3 4 1 2

出力例1

l=3,\ r=4 として 1 度だけ操作を行うのが最善です。

入力例2

6
1 2 3 4 5 6

出力例2

1 度も操作をしないのが最善です。

入力例3

7
1 5 4 7 2 3 6

出力例3

O - Xor Sum Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

kaage くんは Xor Sum っぽい問題を作ろうと思いました。次の問題を解いてください。

長さ N の数列 A, B が与えられる。集合 U=\{x|x\in\mathbb{N},1\leq x\leq N\} の空でない任意の部分集合 S をとったとき、S=\{k_1, k_2, \cdots k_l\} として、(A_{k_1} xor A_{k_2} xor\cdots xor A_{k_l})+(B_{k_1} xor B_{k_2} xor\cdots xor B_{k_l}) の最大値を求めよ。ただし、ここで xor はビットごとの排他的論理和を表す。

制約

入力は全て整数である。
1 \leq N \leq 5\times 10^5
0 \leq A_i,B_i < 2^{10}

入力

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

N
\(A_1\) \(A_2\) \(\cdots\ A_N\)
\(B_1\) \(B_2\) \(\cdots\ B_N\)

出力

考えられる最大値を一行に出力してください。

入力例1

4
4 2 6 7
1 5 3 4

出力例1

S=\{4\} が最適です。

writer: kaage