実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
高橋君は,文字列 S を持っています.
高橋君は yahoo
という文字列が好きなので,S を編集することで yahoo
の繰り返しで得られる文字列に変えようとしています.
ここで,yahoo
の繰り返しで得られる文字列とは,yahoo
を 0 個以上つなげてできる文字列です.これらは,短いほうから順に (空文字列),yahoo
,yahooyahoo
,… となります.
高橋君は 1 回の操作で次のうちいずれかを行うことができます.
- S の任意の 1 文字を選んで,それを任意の英小文字に書き換える.
- S の任意の 1 文字を選んで,その文字を S から取り除く.
- S の任意の位置に,任意の英小文字を挿入する.
高橋君が S を yahoo
の繰り返しで得られる文字列にするために,必要な操作の回数の最小値を求めてください.
制約
- 1 \leq |S| \leq 10^5
- S は英小文字からなる
入力
入力は以下の形式で標準入力から与えられる.
S
出力
高橋君が S を yahoo
の繰り返しで得られる文字列にするために,必要な操作の回数の最小値を求めてください.
入力例 1
yfoo
出力例 1
2
例えば,次のようにすればよいです.
- 2 文字目の
f
をh
に変える.S はyhoo
になる. - 1 文字目と 2 文字目の間に
a
を挿入する.S はyahoo
になる.
入力例 2
z
出力例 2
1
1 文字目の z
を取り除くと,S は空文字列になり,yahoo
の繰り返しで得られる文字列になります.
入力例 3
yahooyahooyahooyahooyahoo
出力例 3
0
入力例 4
yahyahoo
出力例 4
2
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 600 点
問題文
ACoder では,チーム高橋とチーム青木の 2 チーム対抗でのプログラミングコンテストを開こうとしています. チーム高橋の参加者の候補は N 人いて,チーム高橋の i 番目の候補者の実力は A_i で表されます. また,チーム青木の参加者の候補は M 人いて,チーム青木の i 番目の候補者の実力は B_i で表されます.
コンテストを開く前に,チーム高橋,チーム青木のそれぞれから K 人ずつの参加者を選ぶことにしました. 参加者は,それぞれのチームの参加者の候補から選ばれます. ここで,K 人ずつの参加者を選んだときの,チーム間の実力差を次のように定義することにしました.
- チーム高橋の参加者の中で i 番目に実力の値が大きい人の実力を X_i,チーム青木の参加者の中で i 番目に実力の値が大きい人の実力を Y_i とする.
- このとき,チーム間の実力差は,max (|X_1 - Y_1|, |X_2 - Y_2|, ..., |X_K - Y_K| ) である.
各チームの参加者を決めたときの,チーム間の実力差の最小値を求めてください.
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq K \leq min (N, M)
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- A_i, B_i は整数
入力
入力は以下の形式で標準入力から与えられる.
N M K A_1 A_2 ... A_N B_1 B_2 ... B_M
出力
チーム間の実力差の最小値を出力せよ.
入力例 1
3 4 2 2 11 16 4 7 9 10
出力例 1
2
チーム高橋からは 1, 2 番目の候補者を,チーム青木からは 1, 3 番目の候補者を,参加者として選ぶことにするとよいです. このとき,チーム高橋の参加者の実力は大きい方から順に 11, 2,チーム青木の参加者の実力は大きい方から順に 9, 4 となります.
入力例 2
6 5 3 15 7 14 3 14 11 20 18 15 18 17
出力例 2
3
実行時間制限: 6 sec / メモリ制限: 512 MB
配点 : 1000 点
問題文
高橋君は,数列 [A_1, A_2, ..., A_N] を持っています. 高橋君は,数列のある区間内の数すべてに同じ値を足すのが好きです.また,高橋君は M の倍数が好きなので,数列のある区間に現れる M の倍数の個数が気になります.
高橋君のために,次のような質問に答えてあげてください.ただし,質問は全部で Q 個与えられるものとします.
- i 番目の質問では,l_i, r_i, d_i が与えられる.まず,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} それぞれの値に d_i を足す.その後,A_{l_i}, A_{l_i + 1}, ..., A_{r_i} の中にある M の倍数の個数を答える.
制約
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq A_i \leq 10^9
- 1 \leq l_i \leq r_i \leq N
- 0 \leq d_i \leq 10^9
- A_i, d_i は整数
入力
入力は以下の形式で標準入力から与えられる.
N M Q A_1 A_2 ... A_N l_1 r_1 d_1 l_2 r_2 d_2 : l_Q r_Q d_Q
出力
i 行目には,i 番目の質問に対する答えを出力せよ.
入力例 1
5 4 4 1 2 4 3 4 1 2 2 2 5 0 4 5 5 1 5 3
出力例 1
1 3 1 1
各質問の後での数列の値は以下のようになります.
- 1 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
- 2 番目の質問の後,数列は [3, 4, 4, 3, 4] になる.
- 3 番目の質問の後,数列は [3, 4, 4, 8, 9] になる.
- 4 番目の質問の後,数列は [6, 7, 7, 11, 12] になる.
入力例 2
10 7 9 6 10 6 10 3 8 1 8 7 2 1 9 6 3 4 9 8 9 6 3 6 3 1 9 9 1 3 7 2 6 2 1 10 0 8 9 4
出力例 2
3 1 0 1 3 1 2 4 0
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1200 点
問題文
高橋君は,長さ N の数列 A を持っています. 高橋君は,A の最長増加部分列を探して遊ぶことにしました. A の最長増加部分列とは,A の部分列であり,かつ狭義単調増加なものの中で,最も長いものを意味します. 高橋君は,A の最長増加部分列をただ探すだけではつまらないと思い,A の最長増加部分列となる部分列の中で,辞書順で K 番目のものを求めることにしました. なお,取り出す位置が異なっても,数列として同じ部分列は区別しないことにしました.
しかし,高橋くんは途中で疲れて寝てしまいました.
高橋君の代わりに,A の最長増加部分列のうち辞書順で K 番目のものを求めて出力するプログラムを書いてください.
なお,そのようなものが存在しない場合は,None
と出力してください.
制約
- 入力は全て整数である
- 1 \leq N \leq 300,000
- 1 \leq K \leq 10^{18}
- 1 \leq A_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる.
N K A_1 A_2 ... A_N
出力
A の最長増加部分列のうち辞書順で K 番目のものを,空白を区切りとして出力せよ.
そのようなものが存在しない場合は,None
と出力せよ.
入力例 1
6 2 3 6 5 1 2 7
出力例 1
3 5 7
A の最長部分増加列となる部分列は,以下の 3 通りあります.
- [1,2,7]
- [3,5,7]
- [3,6,7]
辞書順で 2 番目のものは,[3,5,7] です.
入力例 2
4 2 1 1 2 2
出力例 2
None
A の最長増加部分列は,[1,2] の 1 通りしかないので,None
を出力します.
入力例 3
20 1000 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19
出力例 3
2 4 6 8 10 11 13 16 18 20
実行時間制限: 2 sec / メモリ制限: 512 MB
配点 : 1400 点
問題文
高橋王国には N 個の都市 1, 2, ..., N があります. どの 2 つの異なる都市の間にも,それらの都市間を直接結ぶ瞬間移動装置が設けられています. 都市 x と y を結ぶ瞬間移動装置を使うと,都市 x から都市 y へも,都市 y から都市 x へも移動することができます.
しかし現在,都市 a_i と b_i (i = 1, 2, ..., M) を直接結ぶ瞬間移動装置は故障しており,使うことができません.
次のような形式の Q 個の質問に答えてください.
- i 番目の質問では,c_i と d_i が与えられる.このとき,都市 c_i から都市 d_i まで瞬間移動装置を乗り継いで移動するためには,最小で何回瞬間移動装置を利用すればよいか?
制約
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq a_i < b_i \leq N
- a_i = a_j かつ b_i = b_j を満たす異なる i, j の組は存在しない
- 1 \leq c_i < d_i \leq N
入力
入力は以下の形式で標準入力から与えられる。
N M Q a_1 b_1 a_2 b_2 : a_M b_M c_1 d_1 c_2 d_2 : c_Q d_Q
出力
i 行目には,i 番目の質問に対する答えを出力せよ.ただし,都市 c_i から都市 d_i まで瞬間移動装置を乗り継いで移動することが不可能なときは,代わりに -1
を出力せよ.
入力例 1
6 7 4 1 2 2 4 2 5 2 6 3 5 3 6 5 6 1 2 2 3 5 6 2 5
出力例 1
2 1 2 3
使える瞬間移動装置は,下図のようになります.図の太線はその都市間を結ぶ瞬間移動装置が使えること,点線は故障していることを表します.
入力例 2
4 4 2 1 3 1 4 2 3 2 4 1 2 1 3
出力例 2
1 -1