Social Infrastructure Information Systems Division, Hitachi Programming Contest 2020

A - Hitachi String

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

文字列 hi が 1 個以上繋がってできる文字列を、 hitachi文字列と定義します。

例えば、 hi や hihi などは hitachi文字列であり、 ha や hii は hitachi文字列ではありません。

文字列 S が与えられるので、 S が hitachi文字列かどうかを判定してください。

制約

S の長さは 1 以上 10 以下
S は英小文字列

入力

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

出力

S が hitachi文字列であれば Yes を、そうでなければ No を出力せよ。

入力例 1

hihi

出力例 1

Yes

hihi は hi を 2 個繋げてできる文字列なので、 hitachi文字列です。

入力例 2

hi

出力例 2

Yes

入力例 3

ha

出力例 3

No

Score : 100 points

Problem Statement

A Hitachi string is a concatenation of one or more copies of the string hi.

For example, hi and hihi are Hitachi strings, while ha and hii are not.

Given a string S, determine whether S is a Hitachi string.

Constraints

The length of S is between 1 and 10 (inclusive).
S is a string consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

Output

If S is a Hitachi string, print Yes; otherwise, print No.

Sample Input 1

hihi

Sample Output 1

Yes

hihi is the concatenation of two copies of hi, so it is a Hitachi string.

Sample Input 2

hi

Sample Output 2

Yes

Sample Input 3

ha

Sample Output 3

No

B - Nice Shopping

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

あなたは、冷蔵庫と電子レンジを買うために、とある家電量販店に来ました。

この家電量販店では、 A 種類の冷蔵庫と B 種類の電子レンジが販売されています。 i 番目( 1 \le i \le A )の冷蔵庫の値段は a_i 円であり、 j 番目( 1 \le j \le B )の電子レンジの値段は b_j 円です。

また、あなたは M 種類の割引券を所持しており、 i 番目 ( 1 \le i \le M )の割引券では、 x_i 番目の冷蔵庫と y_i 番目の電子レンジを同時に買うと、支払総額が c_i 円安くなります。ただし、複数の割引券を同時に使うことはできません。

さて、あなたは冷蔵庫と電子レンジをちょうど 1 台ずつ買おうと思っています。かかる金額の最小値を求めてください。

制約

入力は全て整数
1 \le A \le 10^5
1 \le B \le 10^5
1 \le M \le 10^5
1 \le a_i , b_i , c_i \le 10^5
1 \le x_i \le A
1 \le y_i \le B
c_i \le a_{x_i} + b_{y_i}

入力

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

A B M
a_1 a_2 ... a_A
b_1 b_2 ... b_B
x_1 y_1 c_1
\vdots
x_M y_M c_M

出力

答えを出力せよ。

入力例 1

出力例 1

1 番目の冷蔵庫と 2 番目の電子レンジを買うと、割引券の効果により 3+3-1=5 円になります。

入力例 2

出力例 2

複数の割引券を同時に使うことはできないことに注意してください。

入力例 3

出力例 3

この場合は 1 番目の冷蔵庫と 1 番目の電子レンジを買うと 6 円になり、これが最小です。割引券は使わなくてもよいことに注意してください。

Score : 200 points

Problem Statement

You are visiting a large electronics store to buy a refrigerator and a microwave.

The store sells A kinds of refrigerators and B kinds of microwaves. The i-th refrigerator ( 1 \le i \le A ) is sold at a_i yen (the currency of Japan), and the j-th microwave ( 1 \le j \le B ) is sold at b_j yen.

You have M discount tickets. With the i-th ticket ( 1 \le i \le M ), you can get a discount of c_i yen from the total price when buying the x_i-th refrigerator and the y_i-th microwave together. Only one ticket can be used at a time.

You are planning to buy one refrigerator and one microwave. Find the minimum amount of money required.

Constraints

All values in input are integers.
1 \le A \le 10^5
1 \le B \le 10^5
1 \le M \le 10^5
1 \le a_i , b_i , c_i \le 10^5
1 \le x_i \le A
1 \le y_i \le B
c_i \le a_{x_i} + b_{y_i}

Input

Input is given from Standard Input in the following format:

A B M
a_1 a_2 ... a_A
b_1 b_2 ... b_B
x_1 y_1 c_1
\vdots
x_M y_M c_M

Output

Print the answer.

Sample Input 1

Sample Output 1

With the ticket, you can get the 1-st refrigerator and the 2-nd microwave for 3+3-1=5 yen.

Sample Input 2

Sample Output 2

Note that you cannot use more than one ticket at a time.

Sample Input 3

Sample Output 3

You can get the 1-st refrigerator and the 1-st microwave for 6 yen, which is the minimum amount to pay in this case. Note that using a ticket is optional.

C - ThREE

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木があります。頂点には 1 から N までの番号がついており、 i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

3 が大好きな高橋くんは、以下の条件を満たす 1 から N までの整数の順列 p_1, p_2, \ldots , p_N を探しています。

すべての頂点の組 (i, j) について、頂点 i と頂点 j の距離が 3 であるならば、p_i と p_j の和または積が 3 の倍数である。

ただし、頂点 i と頂点 j の距離とは、頂点 i から頂点 j へ最短経路で移動するときに使用する辺の個数のことを指します。

高橋くんのために条件を満たす順列を 1 つ見つけてください。

制約

2\leq N\leq 2\times 10^5
1\leq a_i, b_i \leq N
与えられるグラフは木である

入力

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

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

出力

問題の条件を満たす順列が存在しない場合は -1 と 1 行に出力せよ。

存在する場合、条件を満たす順列の 1 つを空白区切りで 1 行に出力せよ。

入力例 1

出力例 1

1 2 5 4 3

距離が 3 である頂点の組は (2, 4) と (2, 5) の 2 つです。

p_2 + p_4 = 6
p_2\times p_5 = 6

であるため、この順列は条件を満たします。

Score : 600 points

Problem Statement

We have a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertex a_i and Vertex b_i.

Takahashi loves the number 3. He is seeking a permutation p_1, p_2, \ldots , p_N of integers from 1 to N satisfying the following condition:

For every pair of vertices (i, j), if the distance between Vertex i and Vertex j is 3, the sum or product of p_i and p_j is a multiple of 3.

Here the distance between Vertex i and Vertex j is the number of edges contained in the shortest path from Vertex i to Vertex j.

Help Takahashi by finding a permutation that satisfies the condition.

Constraints

2\leq N\leq 2\times 10^5
1\leq a_i, b_i \leq N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

If no permutation satisfies the condition, print -1.

Otherwise, print a permutation satisfying the condition, with space in between. If there are multiple solutions, you can print any of them.

Sample Input 1

Sample Output 1

1 2 5 4 3

The distance between two vertices is 3 for the two pairs (2, 4) and (2, 5).

p_2 + p_4 = 6
p_2\times p_5 = 6

Thus, this permutation satisfies the condition.

D - Manga Market

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 個の店があり、それぞれ店 1、店 2 、 \cdots 、店 N という名前が付けられています。高橋君は時刻 0 に自宅にいて、これからいくつかの店を訪れる予定です。

高橋君が自宅から各店へ移動する際及び任意の 2 つの店の間を移動する際に要する時間は 1 単位時間です。

高橋君が時刻 t に店 i に着いたとき、その店の列に並び、 a_i \times t + b_i 単位時間待つことにより、その店で買い物をすることが出来ます。(待ち時間以外の時間はかからないとします。)

全ての店の閉店時刻は T + 0.5 です。ある店で列に並んでいる途中に閉店時刻を迎えた場合、その店で買い物をすることは出来ません。

高橋君は同じ店で 2 回以上買い物をしません。

高橋君が閉店時刻までに買い物を出来る店の数の最大値を答えてください。

制約

入力は全て整数
1 \leq N \leq 2 \times 10^5
0 \leq a_i \leq 10^9
0 \leq b_i \leq 10^9
0 \leq T \leq 10^9

入力

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

N T
a_1 b_1
a_2 b_2
\vdots
a_N b_N

出力

答えを出力せよ。

入力例 1

出力例 1

店の回り方の例を 1 つ示します。

時刻 0 から時刻 1 : 自宅から店 1 へ 1 単位時間掛けて移動します。
時刻 1 から時刻 3 : 店 1 で 2 単位時間待ち、買い物をします。
時刻 3 から時刻 4 : 店 1 から店 3 へ 1 単位時間掛けて移動します。
時刻 4 から時刻 7 : 店 3 で 3 単位時間待ち、買い物をします。

以上の回り方では、時刻 7.5 までに 2 箇所の店で買い物を行うことが出来ます。

入力例 2

1 3
0 3

出力例 2

入力例 3

出力例 3

入力例 4

出力例 4

Score : 800 points

Problem Statement

There are N stores called Store 1, Store 2, \cdots, Store N. Takahashi, who is at his house at time 0, is planning to visit some of these stores.

It takes Takahashi one unit of time to travel from his house to one of the stores, or between any two stores.

If Takahashi reaches Store i at time t, he can do shopping there after standing in a queue for a_i \times t + b_i units of time. (We assume that it takes no time other than waiting.)

All the stores close at time T + 0.5. If Takahashi is standing in a queue for some store then, he cannot do shopping there.

Takahashi does not do shopping more than once in the same store.

Find the maximum number of times he can do shopping before time T + 0.5.

Constraints

All values in input are integers.
1 \leq N \leq 2 \times 10^5
0 \leq a_i \leq 10^9
0 \leq b_i \leq 10^9
0 \leq T \leq 10^9

Input

Input is given from Standard Input in the following format:

N T
a_1 b_1
a_2 b_2
\vdots
a_N b_N

Output

Print the answer.

Sample Input 1

Sample Output 1

Here is one possible way to visit stores:

From time 0 to time 1: in 1 unit of time, he travels from his house to Store 1.
From time 1 to time 3: for 2 units of time, he stands in a queue for Store 1 to do shopping.
From time 3 to time 4: in 1 unit of time, he travels from Store 1 to Store 3.
From time 4 to time 7: for 3 units of time, he stands in a queue for Store 3 to do shopping.

In this way, he can do shopping twice before time 7.5.

Sample Input 2

1 3
0 3

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

Sample Output 4

E - Odd Sum Rectangles

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

(2^N - 1) 行 (2^M-1) 列のグリッドがあり、あなたはこれからすべてのマスに 0, 1 のいずれかの数字を書き込みます。上から i 行目、左から j 列目に書き込む数字を a_{i,j} とします。

1\leq i_1 \leq i_2\leq 2^N-1, 1\leq j_1 \leq j_2\leq 2^M-1 をみたす整数の組 (i_1, i_2, j_1, j_2) に対し、 S(i_1, i_2, j_1, j_2) = \displaystyle \sum_{r=i_1}^{i_2}\sum_{c=j_1}^{j_2}a_{r,c} と定義し、さらに、グリッドの「奇妙さ」を S(i_1, i_2, j_1, j_2) が奇数となるような (i_1, i_2, j_1, j_2) の個数と定義します。

奇妙さが最大となるような数字の書き込み方を 1 つ求めてください。

制約

N, M は 1 以上 10 以下の整数

入力

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

N M

出力

奇妙さが最大となる書き込み方の 1 つを、以下の形式で出力せよ。

a_{1,1}a_{1,2}\cdots a_{1,2^M-1}
a_{2,1}a_{2,2}\cdots a_{2,2^M-1}
\vdots
a_{2^N-1,1}a_{2^N-1,2}\cdots a_{2^N-1,2^M-1}

入力例 1

1 2

出力例 1

S(1, 1, 1, 1)、S(1, 1, 2, 2)、S(1, 1, 3, 3)、S(1, 1, 1, 3) が奇数となるため、このグリッドの奇妙さは 4 です。

奇妙さを 5 以上にすることはできないため、これは奇妙さが最大となる書き込み方の 1 つです。

Score : 900 points

Problem Statement

We have a grid with (2^N - 1) rows and (2^M-1) columns. You are asked to write 0 or 1 in each of these squares. Let a_{i,j} be the number written in the square at the i-th row from the top and the j-th column from the left.

For a quadruple of integers (i_1, i_2, j_1, j_2) such that 1\leq i_1 \leq i_2\leq 2^N-1, 1\leq j_1 \leq j_2\leq 2^M-1, let S(i_1, i_2, j_1, j_2) = \displaystyle \sum_{r=i_1}^{i_2}\sum_{c=j_1}^{j_2}a_{r,c}. Then, let the oddness of the grid be the number of quadruples (i_1, i_2, j_1, j_2) such that S(i_1, i_2, j_1, j_2) is odd.

Find a way to fill in the grid that maximizes its oddness.

Constraints

N and M are integers between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

N M

Output

Print numbers to write in the grid so that its oddness is maximized, in the following format:

a_{1,1}a_{1,2}\cdots a_{1,2^M-1}
a_{2,1}a_{2,2}\cdots a_{2,2^M-1}
\vdots
a_{2^N-1,1}a_{2^N-1,2}\cdots a_{2^N-1,2^M-1}

If there are multiple solutions, you can print any of them.

Sample Input 1

1 2

Sample Output 1

For this grid, S(1, 1, 1, 1), S(1, 1, 2, 2), S(1, 1, 3, 3), and S(1, 1, 1, 3) are odd, so it has the oddness of 4.

We cannot make the oddness 5 or higher, so this is one of the ways that maximize the oddness.

F - Preserve Diameter

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

1 から N までの番号がつけられた N 個の頂点を持つ木 G があります。 G の i 番目の辺は頂点 a_i と頂点 b_i を結んでいます。

G に 0 本以上の辺を追加することを考えます。追加後のグラフを H とします。

以下の 4 つの条件を満たす H の個数を 998244353 で割ったあまりを求めてください。

H に多重辺は存在しない
H に自己ループは存在しない
G の直径と H の直径は等しい
H に辺が存在しない任意の頂点対について、H にその頂点対間を結ぶ辺を追加すると、直径が短くなる

制約

3 \le N \le 2 \times 10^5
1 \le a_i, b_i \le N
入力で与えられるグラフは木

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

答えを出力せよ。

入力例 1

出力例 1

例えば、G に辺 (1, 5), (3, 5) を追加したグラフは問題文中の 4 つの条件を満たします。

入力例 2

3
1 2
2 3

出力例 2

H として考えられるグラフは、G のみです。

入力例 3

出力例 3

入力例 4

出力例 4

Score : 1100 points

Problem Statement

We have a tree G with N vertices numbered 1 to N. The i-th edge of G connects Vertex a_i and Vertex b_i.

Consider adding zero or more edges in G, and let H be the graph resulted.

Find the number of graphs H that satisfy the following conditions, modulo 998244353.

H does not contain self-loops or multiple edges.
The diameters of G and H are equal.
For every pair of vertices in H that is not directly connected by an edge, the addition of an edge directly connecting them would reduce the diameter of the graph.

Constraints

3 \le N \le 2 \times 10^5
1 \le a_i, b_i \le N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

Print the answer.

Sample Input 1

Sample Output 1

For example, adding the edges (1, 5), (3, 5) in G satisfies the conditions.

Sample Input 2

3
1 2
2 3

Sample Output 2

The only graph H that satisfies the conditions is G.

Sample Input 3

Sample Output 3

Sample Input 4