Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんはマンハッタンにいます。マンハッタンは南北に伸びる道と東西に伸びる道で区画分けされており、どの道も十分長いため、南北に伸びる道と東西に伸びる道はどの組も交わり、その交わる点で交差点を作ります。また、南北に伸びる道同士、東西に伸びる道同士はそれぞれ交わりません。
西から x 番目の南北に伸びる道と、南から y 番目の東西に伸びる道の交わる交差点を (x,y) と表すことにしましょう。
高橋くんは交差点 (x_1,y_1) から交差点 (x_2,y_2) へ行こうと考えています。このとき、最小でいくつの交差点を通らねばならないでしょうか？通る交差点には、交差点 (x_1,y_1) と交差点 (x_2,y_2) を含みます。
高橋くんが通らなければならない交差点の数を求めるプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
x_1 y_1 x_2 y_2
- 1 行目には、高橋くんが初めにいる交差点の場所を表す x_1, y_1 (1 ≦ x_1, y_1 ≦ 100,000) が与えられる。
- 2 行目には、高橋くんの目的地の交差点の場所を表す x_2, y_2 (1 ≦ x_2, y_2 ≦ 100,000) が与えられる。
- (x_1, y_1) ≠ (x_2, y_2) であることが保証される。つまり、目的地の交差点は初めにいる交差点とは異なる。
出力
1 行目に、高橋くんが初めにいる交差点から目的地の交差点へ行くときに通る最小の交差点の数を出力せよ。
行末の改行を忘れないこと。
入力例1
3 3 2 5
出力例1
4
S が初めにいる交差点、T が目的地の交差点です。
例えば、(3,3) -> (2,3) -> (2,4) -> (2,5) と進むと、4 つの交差点を通って目的地へ行くことができます。4 つ未満の交差点を通って行くことはできません。
入力例2
1 2 1 1
出力例2
2
(1,2) -> (1,1) と進むのが最適です。
入力例3
20 40 32 64
出力例3
37
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは文字列 s を持っており、文字列 t を作りたいと思っています。 高橋くんは、文字列の末尾の 1 文字を先頭に追加し、末尾の 1 文字を削除するという操作を文字列 s に行うことで、文字列 s を文字列 t にしたいと考えています。
最小で何回この操作を行えば、文字列 s を文字列 t にできるでしょうか？最小の操作回数を出力するプログラムを書いてください。この操作では文字列 s を文字列 t に変換することができない場合、-1 と出力してください。
入力
入力は以下の形式で標準入力から与えられる。
s t
- 1 行目には、高橋くんが持っている文字列 s (1 ≦ \|s\| ≦ 1,000) が与えられる。ただし、 \|s\| は文字列 s の長さを表す。s は半角小文字アルファベットa-zのみからなる。
- 2 行目には、高橋くんが作りたい文字列 t (1 ≦ \|t\| ≦ 1,000) が与えられる。t は半角小文字アルファベットa-zのみからなる。
出力
1 行目に、高橋くんが文字列 s を文字列 t に変換するための操作の最小回数を出力せよ。
行末の改行を忘れないこと。
入力例1
abcd dabc
出力例1
1
abcd の末尾の文字を先頭に追加すると、
dabcd となり、ここから末尾の文字を削除すると、
dabc となります。
よって、1 回の操作で s は t に等しくなります。
入力例2
abcabcabc bcabcabca
出力例2
2
問題文中の操作を s に 2 回行うと t と等しくなります。 5 回、8 回行っても t と等しくなりますが、最小のものを求める必要があります。
入力例3
aaa a
出力例3
-1
入力例4
cab cab
出力例4
0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
木とは、頂点とそれを結ぶ辺からなる構造「グラフ」の 1 種で、頂点の数を N 個とすると、辺は N-1 本あり、どの頂点も他の全ての頂点に辺で間接・直接的につながっています。
この問題では、頂点は N 個あり、1 から N まで番号付けられています。
木が与えられたとき、以下の操作で作られる数列のうち、辞書順で最小のものを出力してください。
- 頂点1を選ぶ。
- 今まで選ばれた頂点と辺で結ばれている頂点のうち、まだ選ばれていない頂点を1つ選ぶ、という操作を選ばれていない頂点が無くなるまで繰り返す。
- 頂点の番号を選ばれた順に並べた数列を作る。
ただし、長さ N の列 A=\{a_1,a_2, ...,a_N\} と B=\{b_1,b_2, ...,b_N\} に対し、辞書順で A が B より小さいとは、
- i < k で a_i=b_i
- i = k で a_i<b_i
となるような k(1≦k≦N) が存在するということです。
入力
入力は以下の形式で標準入力から与えられる。
N
a_1 b_1
a_2 b_2
：
a_{N-1} b_{N-1}
- 1 行目には、木の頂点の数を表す整数 N (2 ≦ N ≦ 10^5) が与えられる。
- 2 行目から N-1 行には、木の辺の情報が与えられる。このうち i (1 ≦ i ≦ N-1) 行目には頂点 a_i と頂点 b_i を結ぶ辺があることを表す 2 つの整数 a_i , b_i が与えられる。
- N-1 本の辺で結ばれる N 個の頂点は木を成すことが保障される。
部分点
この問題には部分点が設定されている。
- 50 点分のテストケースにおいて、 1 ≦ N ≦ 3,000 を満たす。
出力
1 行目に、与えられた木から作られる辞書順で最小の数列を空白区切りで出力せよ。
行末の改行を忘れないこと。また，行末に余分な空白を入れてはならない。
入力例1
4 1 3 1 4 2 3
出力例1
1 3 2 4
問題文中の図の木です。
まず、初めに頂点 1 を選びます。
次に、頂点 3 を選びます。頂点 2 は今まで選んだ頂点(この場合、頂点 1 のみ)と辺で結ばれていないので、選ぶことができないことに注意してください。
次に、頂点 2 を選びます。
次に、頂点 4 を選びます。
頂点の番号を選んだ順に並べると、1 3 2 4 となります。この列より辞書順で小さい選び方は存在しません。
入力例2
6 1 2 2 3 2 6 6 4 1 5
出力例2
1 2 3 5 6 4
入力例3
7 1 5 5 2 5 3 5 7 5 6 6 4
出力例3
1 5 2 3 6 4 7
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋くんは長さ N の 1 から C の整数からなる数列 \{a_N\} = \{a_1,a_2, ...,a_N\} を受け取って、 1 以上 C 以下のそれぞれの整数について、その数を1つでも含む連続する部分列の数を返す機械です。
より正確には、 1 以上 C 以下の整数 k について、 1 ≦ l ≦ r ≦ N となるような l,r で、 a_i = k かつ l≦ i ≦ r を満たすものが存在するような (l,r) の組の数を高橋くんは求めます。
連続する部分列の中身が同じでも、(l,r) の組が異なれば異なるものとして認識することに注意してください。 高橋くんの動作を確認するためのプログラムを書いてください。
入力
入力は以下の形式で標準入力から与えられる。
N C a_1 a_2 … a_N
- 1 行目には、数列の長さ N (1 ≦ N ≦ 10^5) と数列の要素の最大値 C (1 ≦ C ≦ N) がスペース区切りで与えられる。
- 2 行目には、高橋くんが受け取った数列の要素の数を表す N 個の数が空白区切りで与えられる。1 ≦ a_i ≦ C であることが保証される。また、1 以上 C 以下のすべての整数 k に対し、 a_i = kを満たす i が存在することが保証される。
部分点
この問題には部分点が設定されている。
- 30 点分のテストケースにおいて、1≦C≦20 を満たす。
出力
i (1 ≦ i ≦ C) 行目には、\{a_N\} のうち i を含む連続する部分列の数を出力せよ。
末尾の改行を忘れないこと。また、それぞれの行の末尾に余計な空白を付け加えないこと。
入力例1
4 2 1 2 2 1
出力例1
7 8
1 を含む連続する部分列として当てはまるものは、 (l,r)=(1,1),(1,2),(1,3),(1,4),(2,4),(3,4),(4,4)
2 を含む連続する部分列として当てはまるものは、 (l,r)=(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4) です。
入力例2
4 4 1 4 2 3
出力例2
4 6 4 6
入力例3
5 1 1 1 1 1 1
出力例3
15