ストーリー

こんにちは。NJPCにご参加いただきありがとうございます。

NJPCの正式名称は「Nara institute of science and technology & Japan advanced institute of science and technology Programming Contest」というのですが、いかんせん長すぎます。

そこであなたに、長過ぎる文字列は初めの L 文字のみを表示するプログラムの作成をお願いしたいのです。

問題文

英小文字のみからなる文字列 S と 表示する最大の長さ L が入力として与えられる。

S の文字数が L より大きい場合は初めの L 文字のみを出力せよ。そうでない場合には S をそのまま出力せよ。

制約

• 1≦L,|S|≦10^5
• L は整数である
• S は英小文字のみからなる

入力例 1

10
hello

出力例 1

hello

入力例 2

37
narasenntannkagakugijyutudaigakuinndaigaku

出力例 2

narasenntannkagakugijyutudaigakuinnda

問題文

H 行 W 列の格子グラフがあります。 このグラフは、頂点が縦に H 行、横に W 列等間隔に並んでいて、上下左右に隣り合う頂点の間のみ辺が張られています。 くじら君はこのグラフの辺に色を塗って遊ぼうと思っていたのですが、N 個の頂点には、誰のいたずらか 'x' マークが描かれていました。 i 番目の 'x' マークは (r_i, c_i) に書かれています。ただし (a,b) は格子グラフの a 行 b 列目の頂点を表し、左上の頂点を (1,1), 右下の頂点を (H,W) とします。 なんだか気味が悪いので、くじら君は 'x' マークが描かれていない頂点どうしを結ぶ辺だけに色を塗ることにしました。

くじら君は自分が塗ることのできる辺すべてに色を塗ります。 このとき、くじら君が色を塗る辺の本数はいくつでしょうか？

なお、出力は32bit型整数に収まらないことがあります。

制約

• 入力は全て整数である。
• 1≦H, W≦10^5
• 0≦N≦10^3
• 1≦r_i≦H
• 1≦c_i≦W
• 入力に同じ位置の頂点が複数与えられることはない。すなわち、すべての i,j (1≦i<j≦N) に対し、r_i ≠ r_j または c_i ≠ c_j が成り立つ。

入力例 1

3 4 4
1 4
2 2
2 4
3 1

出力例 1

7

図1: 入力例1

入力例 2

1 5 2
1 2
1 4

出力例 2

0

図2: 入力例2

入力例 3

100000 100000 0

出力例 3

19999800000

問題文

N 個のハードルが数直線上に置かれている。i 番目のハードルの位置は x_i で、 x_i は正の整数かつ x_1 < x_2 < … < x_N を満たす。

あなたはハードル走の走者である。あなたは数直線上の原点から正の方向に一定の速度で走って進む。途中で走る向きを変えることはできない。あなたは任意の位置(整数座標でなくともよい)でジャンプすることができる。ジャンプすると、そこから L メートルの間空中を移動したのち着地する。しかしジャンプは体力を使うので、着地してから L メートルの間はジャンプできず、地上を走らなければならない。最初、あなたは地上にいる。

あなたはハードルに当たることなくすべてのハードルを飛び越えることができるか？

ただし、位置 x にあるハードルを飛び越えるとは、位置 x で空中にいることである。また、ジャンプする位置、着地する位置ではあなたは地上にいるものとする。つまり、ハードルのある位置でジャンプしたり、ハードルのある位置に着地することはできない。原点でジャンプすることはできる。

制約

• 入力は全て整数である。
• 1 ≦ N ≦ 10^5
• 1 ≦ L ≦ 10^9
• 1 ≦ x_1 < x_2 < … < x_N ≦ 10^9

部分点

400 点分のテストケースでは、以下のすべてが満たされる。

• 1 ≦ N ≦ 2000
• 1 ≦ L ≦ 2000
• 1 ≦ x_1 < x_2 < … < x_N ≦ 2000

入力例 1

3 4
3
5
13

出力例 1

YES

図1: 入力例1での飛び方の例

図1の赤い線はハードルを、青い線はすべてのハードルを飛び越えるための進み方の一例を示している。 この進み方では、まず 0 ≦ x ≦ 1.2 では地上を走る。 次に、x = 1.2 でジャンプする。すると 1.2 < x < 5.2 では空中を進む。ジャンプの影響により、 5.2 ≦ x ≦ 9.2 では地上を走らなければならない。 その後 x = 11 でジャンプすると、すべてのハードルを飛び越えることができる。

このケースは部分点の制約を満たす。

入力例 2

5 3
1
2
5
7
9

出力例 2

NO

どのようにジャンプしても位置 x = 5 のハードルを飛び越えることはできない。

このケースは部分点の制約を満たす。

入力例 3

5 6
1
2
3
4
5

出力例 3

YES

たとえば原点でジャンプするとすべてのハードルを飛び越えることができる。

このケースは部分点の制約を満たす。

入力例 4

3 5
1
3
10

出力例 4

NO

原点から負の方向に移動することはできない。

このケースは部分点の制約を満たす。

入力例 5

4 4
2
3
9
15

出力例 5

NO

このケースは部分点の制約を満たす。

入力例 6

4 1
1
3
5
7

出力例 6

YES

このケースは部分点の制約を満たす。

入力例 7

4 6100991
199010
199110
6300101
9231211

出力例 7

NO

問題文

あなたはNMパズルと呼ばれるパズルゲームで遊んでいる。 このゲームは、1 から NM までの整数のうち一つが書かれたカード NM 枚と、N 行 M 列の盤面を用いて行われる。ここで、カードに書かれた整数に重複は無い。

このゲームの目的は、スコアが K となるようにカードを配置することである。 盤面上の全てのマスにちょうど1枚ずつカードを配置した時、(各行の転倒数の和) + (各列の転倒数の和)がスコアとなる。

スコアがちょうど K となるようなカードの配置を一つ出力しなさい。

なお、条件を満たす出力が複数ある場合、どれを出力しても良い。

ここで、転倒数は以下のように定義される。

C_{ij} は盤面の i 行 j 列目のマスに配置するカードに書かれた整数を表す。ただし、左上を 1 行 1 列目、右下を N 行 M 列目とする。

• 行 i (1 ≦ i ≦ N) の転倒数とは、 1 ≦ j < j’ ≦ M かつ C_{ij} > C_{ij’} を満たす組 (j, j’) の個数である。
• 列 j (1 ≦ j ≦ M) の転倒数とは、 1 ≦ i < i’ ≦ N かつ C_{ij} > C_{i’j} を満たす組 (i, i’) の個数である。

制約

• 入力は全て整数である。
• 1 ≦ N, M ≦ 100
• 0 ≦ K ≦ NM(M-1)/2 + MN(N-1)/2
• スコアが K となるようなカードの配置は必ず存在する。

入力例 1

2 3 5

出力例 1

6 1 4
2 5 3

このように配置すると、転倒数は1行目が2, 2行目が1, 1列目が1, 2列目が0, 3列目が1となるため、スコアは5となり条件を満たす。

なおこれは出力例であり、他にも条件を満たす出力は存在する。

問題文

ゆらふなくんは，山奥にある限界集落の村長である。この限界集落にあるそれぞれの道路には，村の掟によって「縁起の良い通行方向」が決められている。村の掟に背き，縁起の良い通行方向と逆の向きに通行すれば，村民の冷たい視線に晒されてしまうだろう。限界集落は N 個の土地と，土地と土地をつなぐ N-1 本の道路からなり，土地には 1,2,...,N と番号がつけられている。i 番目 (1 ≦ i ≦ N-1) の道路は土地 A_i と B_i をつないでおり，その道路の縁起の良い通行方向は土地 A_i から B_i の向きである。土地 A_i と B_i の間を移動するには C_i 分の時間がかかる。土地を頂点，道路を辺とする無向グラフとみなしたとき，この無向グラフは連結である。ある土地から別の土地へ移動するには，通る必要があるすべての道についての C の総和の時間がかかる。

ゆらふなくんは限界集落に学校を作るための土地を選ぼうとしている。登校に長い時間がかかる学生が出てくるような事態は避けたいので，限界集落の中のどの土地からも D 分以内で登校できる場所に学校を作りたい。また，学生たちが登校中に村民の冷たい視線に晒されてしまうのを防ぐために，いくつかの道路については縁起の良い通行方向を入れ替える必要がある。登校時間の制約を満たす土地の中で，縁起の良い通行方向を変更しなければならない道路の数が最小となるような土地に学校を作りたい。そのような土地に学校を作った時の縁起の良い通行方向の変更回数を求めよ。もし登校時間の制約を満たすような土地が存在しないならば -1 を出力せよ。

制約

• 入力は全て整数である
• 2 ≦ N ≦ 10^5
• 1 ≦ A_i, B_i ≦ N
• A_i ≠ B_i
• i ≠ j, A_i = A_j, B_i = B_j となるものはない
• i ≠ j, A_i = B_j, A_j = B_i となるものはない
• 0 ≦ C_i ≦ 10^3
• 1 ≦ D ≦ 10^9
• 村の掟を無視すれば，どの土地からどの土地へもいくつかの道路を通って到達できる。

入力例 1

7 15
2 1 2
3 2 3
2 4 5
4 5 1
4 6 4
7 6 6

出力例 1

2

登校時間の制約を満たしうる土地は2, 4, 5, 6である。これらの土地が制約を満たすために村の掟を変更しなければならない最小の回数は，それぞれ4, 3, 2, 2である。

問題文

くじら君とかつお君はダブルスのペアを組み、テニスの大会に出場することにしました。 2人は次の試合で敵のボールをすべて打ち返し、完封勝ちしたいと考えています。 そのために自分たちがどれだけ本気を出せばいいか計算することにしました。

簡単のため、テニスコートを1本の数直線で表します(つまり自陣における横方向の移動しか考えず、縦方向の差は考えないものとします)。 2人は最初、時刻 0 において原点に立っています。 2人は任意の時刻において、速さ V 以下で移動するか静止することができます。 2人の速さの上限 V は共通ですが、それ以外は独立に移動することができます。すれちがうことも、同じ時刻に同じ位置にいることもできます。

今から N 個のボールが飛んできます。 i 番目のボールは時刻 T_i に位置 X_i に飛んできます。 i 番目のボールを打ち返すには時刻 T_i に少なくとも1人が位置 X_i にいなければなりません。 2人がすべてのボールを打ち返すための速さの上限 V の最小値を求めてください。

制約

• 入力はすべて整数である。
• 1 ≦ N ≦ 10^5
• 1 ≦ T_i ≦ 10^9
• i < j のとき T_i < T_j
• −10^6 ≦ X_i ≦ 10^6

部分点

• 600 点分のテストケースでは 1 ≦ N ≦ 2000 が満たされる。

入力例 1

4
1 2
2 4
5 0
6 4

出力例 1

2.0000000000

入力例 2

5
1 3
2 -6
3 9
4 -12
5 15

出力例 2

3.0000000000

入力例 3

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

出力例 3

0.0000000000

入力例 4

3
1 0
3 5
5 0

出力例 4

1.6666666667

入力例 5

4
1 5
2 -10
4 0
5 -20

出力例 5

5.0000000000

問題文

いくつかのプログラミング言語では，2つの文字列 s1 と s2 について，文字列の結合を表す演算子 + が定義されています。たとえば，s1=a，s2=b のとき，s1+s2=ab となります。 ところが，文字列の結合を表す演算子 + は，数の和を表す演算子 + とはちがって，交換法則は成立しません。たとえば，s1=a，s2=b のとき，s1+s2=ab であるのに対し，s2+s1=ba となるので，交換法則が成立していません。

ゆらふなくんは，2つの文字列に対する交換法則が成立する演算子として，以下のような演算子 @ を考えました。

• s1@s2=min(s1,s2)+max(s1,s2)

ここで，min, max は辞書順の比較，+ は文字列の結合を表します。たとえば，s1=a，s2=b のとき，s1@s2=min(a,b)+max(a,b)=a+b=ab となります。また，s2@s1=min(a,b)+max(a,b)=a+b=ab となるので，交換法則が成立しています。

ゆらふなくんは，演算子 @ がとても気に入っているので，いろいろな文字列を1文字ごとに分解したあとに，演算子 @ と優先順位を変える括弧のみを使って元の文字列に戻す遊びをしています。たとえば，apple という文字列は ((a@(p@p))@l)@e や e@(((p@p)@a)@l) などの式によって apple という文字列に戻すことができます。しかしながら，pen という文字列は分解してしまうと元に戻すことができないことに気づきました。分解してから元に戻せない文字列では遊ぶことができないので，そのような文字列かどうか判定する必要があります。

文字列 S が与えられます。1文字ごとに分解したあと，演算子 @ と括弧のみを使って元の文字列に戻せるかどうか判定してください。

制約

• 1≦|S|≦3000 (|S| は文字列 S の長さ)
• S はアルファベット小文字のみからなる

入力例 1

abc

出力例 1

Yes

入力例 2

acb

出力例 2

Yes

入力例 3

bca

出力例 3

No

入力例 4

cba

出力例 4

No

入力例 5

aaba

出力例 5

No

問題文

N 頂点の根付き木が与えられます。各頂点には 1, 2, …, N と番号がつけられており，頂点 1 はこの根付き木の根です。辺はすべて無向辺で，i 番目 ( 2 ≦ i ≦ N ) の頂点の親は p_i です。

最初，各頂点は白または黒に塗られており，i 番目の頂点 ( 1 ≦ i ≦ N ) の初期の色は C_i = 0 のとき白色，C_i = 1 のとき黒色です。

Q 個のクエリが与えられるので，順番に処理してください。クエリは以下の2種類のどちらかで，入力形式とクエリの内容は以下のとおりです。

• 1 u：頂点 u を根とする部分木に含まれるすべての頂点の色を反転させる。
• 2 u v：頂点 u から v へ，白い頂点と黒い頂点を交互に通って辿り着くことができるならばYES，そうでなければNOを出力せよ。最初の色は白でも黒でもかまわない。

制約

• 入力は全て整数である。
• 2≦N≦10^5
• 1≦p_i≦N
• C_i = 0 または 1
• 1≦Q≦10^5
• 入力される根付き木は必ず連結である。
• クエリが1 uのとき、1≦u≦N である。
• クエリが2 u vのとき、1≦u,v≦N かつ u≠v である。
• 2 u vというフォーマットのクエリが少なくとも1つ存在することが保証される。

入力例 1

6
1
1
2
2
3
0
1
0
0
1
1
10
2 4 1
2 4 3
2 1 2
1 2
2 4 1
1 3
1 5
2 1 6
1 1
2 5 4

出力例 1

YES
NO
YES
NO
YES
YES

入力例 2

7
1
2
3
3
5
6
0
0
1
0
0
1
1
7
2 1 4
2 4 2
2 4 5
2 4 6
2 6 1
2 7 1
2 2 6

出力例 2

NO
YES
YES
YES
NO
NO
YES

入力例 3

2
1
0
1
11
2 1 2
2 2 1
1 2
2 1 2
2 2 1
1 1
2 1 2
2 2 1
1 2
2 1 2
2 2 1

出力例 3

YES
YES
NO
NO
NO
NO
YES
YES

入力例 4

5
1
2
3
4
0
1
0
1
0
11
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5
1 3
2 1 2
2 1 4
2 3 1
2 5 1
2 4 5

出力例 4

YES
YES
YES
YES
YES
YES
NO
NO
NO
YES

入力例 5

9
4
2
6
8
1
4
1
8
0
0
1
0
0
1
1
1
0
2
2 9 8
2 9 4

出力例 5

YES
YES