問題文

2014 年に 1 回目の QUPC (九州大学プログラミングコンテストの略称) が開催されてから 2018 年に 2 回目の QUPC が開催されるまで、問題セットの準備に 4 年間かかりました。

このペースでいくと 3 回目の QUPC が開催されるのは 2022 年になりそうです。

整数 N が与えられるので、2014 年から 4 年間隔で QUPC が開催される場合、N 回目の QUPC が開催されるのは何年になるかを求めてください。

制約

• 3 \leq N \leq 1333
• N は整数

入力例 1

3

出力例 1

2022

入力例 2

79

出力例 2

2326

問題文

Treeone 君は 100 円玉を A 枚、10 円玉を B 枚、1 円玉を C 枚持っています。

小銭は邪魔なので たぷちゃん と たぴちゃん の 2 人にお小遣いとしてあげることにしました。

しかし、2 人は仲が悪いので同じ金額をもらえないと喧嘩してしまいます。

全ての硬貨をそれぞれ 2 人のどちらかにあげるとき、2 人に同じ金額のお小遣いをあげることができるかどうかを判定してください。

入力は Q 個のデータセットからなります。

制約

• 1 \leq Q \leq 50
• 0 \leq A, B, C \leq 10^9
• 1 \leq A + B + C
• 入力は全て整数

部分点

• A, B, C \leq 100 を満たすデータセットに正解した場合、20 点が与えられる。

入力例 1

2
2 10 20
1 1 1

出力例 1

Yes
No

1 番目のデータセットでは、例えばそれぞれに 100 円玉を 1 枚、10 円玉を 5 枚、1 円玉を 10 枚あげることで、同じ金額のお小遣いをあげることができます。

2 番目のデータセットでは、どのように分けても 2 人に同じ金額のお小遣いをあげることはできません。

問題文

うしくん と イノシシ が迷路に閉じ込められてしまいました。

迷路は H 行 W 列のマス目で表されています。上から i 行目、左から j 列目にあるマスを (i,j) で表し、マス (i,j) の情報は s_{ij} で与えられます。

• s_{ij} が S のとき、マス (i,j) はスタート地点で、うしくん は最初このマスにいます。
• s_{ij} が G のとき、マス (i,j) はゴール地点です。
• s_{ij} が # のとき、マス (i,j) は壁のマスで、このマスを通ることはできません。
• s_{ij} が @ のとき、マス (i,j) にはイノシシがいます。
• s_{ij} が . のとき、マス (i,j) は空のマスです。

うしくん は壁のマス以外の上下左右に隣接するマスに移動することができます。

' 安全なマス ' を、そこから X 回以下の移動で行くことのできる全てのマスにイノシシがいないようなマスと定義します。

うしくん がスタート地点から安全なマスのみを通ってゴール地点に到達するまでの最小の移動回数を求めてください。

制約

• 4 \leq H, W \leq 10^3
• 0 \leq X \leq 10^6
• s_{ij} は S または G または # または . または @ からなる
• スタート地点とゴール地点はそれぞれ 1 つずつ存在する
• イノシシがいるマスは 1 つ以上存在する
• スタート地点は安全なマスであることが保証されている
• 迷路の外側 1 マスは壁で囲われている
• H,W,X は整数

部分点

• H, W \leq 50 を満たすデータセットに正解した場合、30 点が与えられる。

入力例 1

6 5 1
#####
#S.@#
#...#
#...#
#@.G#
#####

出力例 1

5

(2,2) → (3,2) → (3,3) → (4,3) → (4,4) → (5,4) と移動することで、スタートから安全なマスのみを通ってゴールまで 5 回で移動できます。

入力例 2

5 6 0
######
#S...#
#@@@.#
#G...#
######

出力例 2

8

入力例 3

5 5 1
#####
#S..#
#...#
#.@G#
#####

出力例 3

-1

ゴールが安全なマスとは限りません。

問題文

異世界に転生した Treeone 君は冒険者として商人の護衛依頼を受けてお金を稼ぐことにしました。

転生先の高橋王国には王都以外に N 個の都市があり、各都市には 1, 2, ..., N と番号づけられています。王都と都市 i の間の移動には T_i 日かかります。

王都から王都以外の都市に向かう商人の護衛依頼が M 件あり、i 番目の依頼では王都を A_i 日目に出発し、都市 X_i に A_i + T_{X_i} 日目に到着します。

また、王都以外の都市から王都に向かう商人の護衛依頼が L 件あり、i 番目の依頼では都市 Y_i を B_i 日目に出発し、王都に B_i + T_{Y_i} 日目に到着します。

出発日と到着日を含めて、同じ日に複数の依頼を受けることはできません。また、依頼を受けずに都市間の移動はしません。

報酬はどの依頼を受けても金貨 1 枚です。これらの依頼の中から、最も多くの報酬が得られるように受ける依頼を選んだとき、得られる金貨の枚数を求めてください。

ただし、Treeone 君は最初王都にいて、選んだ全ての依頼を受け終わったときにはどの都市にいても構いません。

制約

• 1 \leq N, M, L \leq 10^5
• 0 \leq T_i \leq 10^9
• 1 \leq X_i \leq N
• 1 \leq A_i \leq 10^9
• 1 \leq Y_i \leq N
• 1 \leq B_i \leq 10^9
• 同一の依頼が複数回与えられることはない
• 入力は全て整数

部分点

• N = 1 を満たすデータセットに正解した場合、30 点が与えられる。

入力例 1

2 3 2
3 1
1 1
2 2
1 6
1 5
2 4

出力例 1

3

次のように依頼を受けることで 3 枚の金貨を得ることができます。

• 2 日目 に王都を出発し、3 日目に都市 2 に到着する。
• 4 日目 に都市 2 を出発し、5 日目に王都に到着する。
• 6 日目 に王都を出発し、9 日目に都市 1 に到着する。

入力例 2

1 2 2
0
1 1
1 2
1 1
1 3

出力例 2

2

この入力例は部分点の制約を満たしています。

出発日と到着日を含めて、同じ日に複数の依頼を受けることはできないことに注意してください。

問題文

数列の 'たぴさ' を、その数列の 連続する 長さ 1 以上の部分列のうち、要素の総和が 0 であるものの個数と定義します。 部分列の中身が同じでも、位置が異なれば別のものとして数えることとします。

長さ N の数列 A_1, A_2, ..., A_N が与えられます。このうち 1 つの要素を好きな整数値に変更できるとき、数列の 'たぴさ' の最小値を求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• |A_i| \leq 10^9
• 入力は全て整数

部分点

• N \leq 5000 を満たすデータセットに正解した場合、40 点が与えられる。

入力例 1

4
0 0 0 0

出力例 1

4

例えば A_2 を 1 に変更すると、総和が 0 である部分列は [1,1], [3,3], [4,4], [3,4] の 4 つとなりこれが最小です。

入力例 2

6
1 -1 -1 2 -2 0

出力例 2

2

問題文

QUPC 2022 九州大学オンサイトには N 人の参加者がいます。i 番目の参加者の AtCoder のレーティングは A_i です。

N 人の参加者を以下の条件を満たすように、いくつかのチームに分けます。

• 各チームの人数は 1 人以上 3 人以下
• 各チームに所属する参加者の AtCoder のレーティングの平均値は K 以下
• AtCoder のレーティングの値に関わらず、1 人チームとして参加することは可能

条件を満たすチームの分け方は何通りあるかを求めてください。この問題の制約下で、答えは 10^{18} を超えないことが保証されています。

制約

• 1 \leq N \leq 18
• 0 \leq K \leq 4208
• 0 \leq A_i \leq 4208
• 入力は全て整数

入力例 1

3 2000
1999 2000 2001

出力例 1

4

3 人以下のチームの組み方は以下の 5 通りで、上の 4 通りが条件を満たします。

• 1 番目の参加者単独のチーム、2 番目の参加者単独のチーム、3 番目の参加者単独のチーム
• 1 番目の参加者と 2 番目の参加者と 3 番目の参加者の 3人チーム
• 1 番目の参加者と 2 番目の参加者の 2 人チーム、3 番目の参加者単独のチーム
• 1 番目の参加者と 3 番目の参加者の 2 人チーム、2 番目の参加者単独のチーム
• 2 番目の参加者と 3 番目の参加者の 2 人チーム、1 番目の参加者単独のチーム

入力例 2

4 2000
2500 3000 1000 2000

出力例 2

6

入力例 3

12 2000
3092 2432 2312 1867 1794 1730 1670 1523 1495 1299 1169 1024

出力例 3

297042

問題文

N 頂点からなる木があり、頂点には 1 から N までの番号がついています。N-1 本の辺のうち i 番目の辺は頂点 A_i と B_i を重み V_i で双方向に結んでいます。

X 匹の たぴちゃん と Y 匹の たぷちゃん がいます。最初 j 番目の たぴちゃん は頂点 P_j、k 番目の たぷちゃん は頂点 Q_k にいます。同じ頂点に複数の たぴちゃん や たぷちゃん は存在しません。

すべての たぴちゃん は隣接する頂点に移動する操作を繰り返すことができます。しかし たぴちゃん と たぷちゃん は仲が悪いです。たぴちゃん が たぷちゃん のいる頂点に移動すると不快な気持ちになるかもしれません。

そこで、いくつかの辺を削除することですべての たぴちゃん が たぷちゃん のいる頂点に移動できなくしたいです。このとき、削除する辺の重みの総和の最小値を求めてください。

制約

• 2 \leq N \leq 5 \times 10^5
• 1 \leq X, Y \leq N
• 1 \leq A_i \lt B_i \leq N
• 1 \leq V_i \leq 10^9
• 1 \leq P_j, Q_k \leq N
• P_1, P_2, ..., P_X, Q_1, Q_2, ..., Q_Y は相異なる
• 与えられるグラフは木
• 入力は全て整数

部分点

• N \leq 500 を満たすデータセットに正解した場合、40 点が与えられる。

入力例 1

5 4 1
1 2 1
2 3 2
3 4 3
4 5 4
1 2 4 5
3

出力例 1

5

2 番目と 3 番目の辺を削除します。このとき、どの たぴちゃん も たぷちゃん がいる頂点 3 には移動できません。

入力例 2

6 2 2
1 2 6
1 3 3
1 4 4
3 5 2
3 6 2
1 2
5 6

出力例 2

3

2 番目の辺を削除します。

問題文

長さ N の数列 A_1, A_2, ..., A_N が与えられます。

i 番目の文字を中心とする最長の回文の長さが A_i であるような、長さ N の英小文字 (a-z) のみからなる文字列 S をどれか 1 つ構成してください。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq N
• 入力は全て整数
• 与えられた入力について、解が存在することは保証されている

入力例 1

5
1 3 5 3 1

出力例 1

ukuku

1 番目の文字を中心とする最長の回文は u

2 番目の文字を中心とする最長の回文は uku

3 番目の文字を中心とする最長の回文は ukuku

4 番目の文字を中心とする最長の回文は uku

5 番目の文字を中心とする最長の回文は u となります。

入力例 2

7
1 1 3 5 5 3 1

出力例 2

ukekeke

問題文

N 個の容器があり、i 番目の容器には A_i リットルの水を入れることができます。

うしくんは N 個の容器の中から 2 個の容器を選んで、以下の操作をそれぞれ任意の回数繰り返し行うことにより、 2 個の容器に合計で K リットルの水が入っている状態にしたいです。

• 操作 1 : 一方の容器を水でいっぱいにする。
• 操作 2 : 容器 X からもう一方の容器 Y に、Y がいっぱいになるか X が空になるまで水をうつす。
• 操作 3 : 一方の容器の中の水を全て捨てる。

上記の方法で K リットルの水を汲み出すことができるような容器のペアの選び方の数を求めてください。

ただし、最初はどの容器も空で、また、選んだ一方の容器を全く使わなくても構いません。

制約

• 2 \leq N \leq 3 \times 10^5
• 1 \leq K \leq 2 \times 10^6
• 1 \leq A_i \leq 10^6
• 入力は全て整数

入力例 1

2 3
4 7

出力例 1

1

1 番目の容器と 2 番目の容器を使って、以下のように操作をすることで 3 リットルの水を汲み出すことができます。

• 2 番目の容器を水でいっぱいにする。
• 2 番目の容器から 1 番目の容器に、1 番目の容器がいっぱいになるまで水をうつす。
• 1 番目の容器の中の水を全て捨てる。

入力例 2

3 11
5 6 11

出力例 2

3

どのペアを選んでも 11 リットルの水を汲み出すことができます。

入力例 3

3 10
3 4 5

出力例 3

0

問題文

a と b からなる文字列 S があって、以下の操作を好きな回数だけ行うことができます。

• S の連続する区間 [l, r] を選ぶ。l \leq k \leq r を満たすすべての整数 k に対し、S_k が a なら S_k を b に、S_k が b なら S_k を a に置き換える。

Q 個の 文字列 T_i が与えられます。各 T_i は a と b からなります。T_i を 10^{100} 回連結し |S|+1 文字目以降をすべて切り落とした文字列を T'_i とします。

それぞれの文字列 T'_i に対し、S を T'_i に一致させるために必要な操作回数の最小値を求めてください。

制約

• 1 \leq |S| \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq |T_i| \leq 2 \times 10^5
• T_i の長さの合計は 2 \times 10^5 以下
• S, T_i は a と b からなる文字列
• Q は整数

入力例 1

babaabbabab
4
abab
b
babaabba
aaaaaaaaaaab

出力例 1

2
4
0
5

それぞれの T'_i は次の通りです。

• T'_1 = abababababa
• T'_2 = bbbbbbbbbbb
• T'_3 = babaabbabab
• T'_4 = aaaaaaaaaaa

例えば S を T'_1 に一致させるために必要な操作回数の最小値は 2 です。babaabbabab → ababbaababa → abababababa の手順で達成可能です。