Time Limit: 2 sec / Memory Limit: 256 MB
問題文
黒猫のスヌケ君は一人でしりとりをしています。
スヌケ君が使える単語は 26 種類のアルファベットからなる 1 文字以上の文字列全てです。 必ずしも英単語として成立している必要はないことに注意してください。
スヌケ君はしりとりで N 個の単語を使用しました。 これら N 個の単語の長さの合計として考えられる最小値はいくつでしょうか?
制約
- 1≦N≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N
出力
スヌケ君がしりとりで使用した N 個の単語の長さの合計として考えられる最小値を出力せよ。
入力例 1
4
出力例 1
6
例えば、a
→ an
→ n
→ na
というようにしりとりをした場合、単語の長さの合計は 6 となります。
同じ単語を 2 回以上使用してはいけない点に注意してください。
入力例 2
1000
出力例 2
2272
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
キリギリスとスローロリスがクリスマスケーキを買うために行列に並びました。
それを見ていたツーリストさんによると以下の情報が分かっています。
- 合計 N 匹の動物が順番に行列に並んだ。
- 行列に並んだ動物は全てキリギリスかスローロリスのどちらかである。
- i 番目に来て行列に並んだ動物はちょうど A_i 匹の動物を順番抜かしした。
- スローロリスがスローロリスを抜かしたことはなかった。
さて、スローロリスは最大で何匹行列に並んでいるでしょうか?
制約
- 1≦N≦300,000
- 0≦A_i≦i-1
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
行列に並んでいるスローロリスの匹数として考えられる最大値を出力せよ。
入力例 1
3 0 0 1
出力例 1
2
この入力では 3 番目の動物だけが順番抜かしをして、2 番目に来た動物を抜かしました。 そのため、2 番目の動物と 3 番目の動物がスローロリスだということはありえず、スローロリスは 2 匹以下しかいないことが分かります。
また、1 番目の動物と 2 番目の動物がスローロリスだったということはありうるため、答えは 2 匹となります。
入力例 2
4 0 1 2 3
出力例 2
1
この入力では、2 匹以上のスローロリスがいたということはありえません。
入力例 3
7 0 0 1 0 0 2 4
出力例 3
4
Time Limit: 4 sec / Memory Limit: 256 MB
問題文
黒猫のスヌケ君はすごろくで遊んでいます。
このすごろくでは変わったサイコロを使っています。 このサイコロには全部で N 個の面があり、それぞれの面が出る確率は全て同じです。 i 番目の面には整数 A_i が書かれていて、この面が出たときは駒をちょうど A_i マス進めます。
一方、このすごろくで使っているマスはそれほど変わったものではありません。 全部で M 個のマスが一列に並んでいて、1 番目のマスがスタート、M 番目のマスがゴールです。 i 番目のマスには整数 B_i が書かれていて、このマスに止まった場合は B_i の値によって以下のような効果を受けます。
- B_i が 0 以上である場合:駒をちょうど B_i マス進める。ただし、進めた先のマスの効果は受けない。
- B_i が 0 未満である場合:-B_i ターン休みとなる。
さて、スヌケ君がこのすごろくでゴールするまでにかかるターン数の期待値はいくらでしょうか?
なお、このすごろくではゴールを越えて進もうとした場合もゴールとみなされます。
制約
- 1≦N≦10^5
- 2≦M≦10^5
- 1≦A_i≦M
- -10≦B_i≦M
- B_1=B_M=0
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 ... A_N B_1 B_2 ... B_M
出力
ゴールするまでにかかるターン数の期待値を出力せよ。 ただし、絶対誤差または相対誤差が 10^{-4} 以下ならば正解とみなされる。
入力例 1
3 4 1 2 3 0 1 -1 0
出力例 1
2.00000000000000000000
最初のターンで出た目ごとに考えると以下のとおりである。
- 出た目が 1 の場合:1 マス進み、2 番目のマスに止まる。このマスの効果により、3 番目のマスまで進む。次のターンでは何が出てもゴールできるため、ゴールには合計 2 ターンかかる。
- 出た目が 2 の場合:2 マス進み、3 番目のマスに止まる。このマスの効果により、1 ターン休みとなる。次のターンは休みとなり、その次のターンでは何が出てもゴールできるため、ゴールには合計 3 ターンかかる。
- 出た目が 3 の場合:3 マス進み、4 番目のマスに止まる。すなわち、1 ターンでゴールできる。
したがって、期待値は 2/3 + 3/3 + 1/3 = 2 となる。
入力例 2
1 10 1 0 0 0 0 0 0 0 0 0 0
出力例 2
9.00000000000000177636
入力例 3
5 6 1 1 2 3 5 0 0 6 -10 1 0
出力例 3
4.47999999999999953815
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
日下部さんは壁に反射するのが大好きで、今日も元気に壁に反射して遊んでいます。
今日の壁は、直角三角形の部屋の壁です。 下図のように三角形の頂点をそれぞれ A,B,C と呼ぶことにします。 日下部さんは頂点 C から点 P に向かってまっすぐ歩き、点 P に着くと、角 BPC = 角 APQ となるような辺 AC 上の点 Q に向かって再びまっすぐ歩きました。
線分 AB の長さは X、線分 BC の長さは Y、線分 AQ の長さは Z でした。 このとき、線分 AP の長さはいくらでしょうか?
制約
- 1≦X,Y≦100
- 1≦Z<\sqrt{X^2+Y^2}
- X,Y,Z は整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y Z
出力
線分 AP の長さを出力せよ。 ただし、絶対誤差または相対誤差が 10^{-9} 以下ならば正解とみなされる。
入力例 1
6 8 5
出力例 1
4
入力例 2
100 100 1
出力例 2
1.40428377656192537870
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
以下のようなBNFで表されるベクトル式 S が与えられるので、計算してください。
<expr> ::= <number> | "("<expr>"*"<expr>")" | "("<vector>"*"<vector>")" <vector> ::= "("<expr>","<expr>")" | "("<expr>"*"<vector>")" | "("<vector>"*"<expr>")" <number> ::= <digit> | <number><digit> <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<expr>
の値は整数(スカラー)、<vector>
の値は二次元ベクトルとなります。
演算子 *
のこの問題での意味は以下の通りです。
<expr>
どうし場合:整数の積を表す。<vector>
どうしの場合:ベクトルの内積を表す。<expr>
と<vector>
の場合:ベクトルのスカラー倍を表す。
ただし、答えは非常に大きくなることがあるため、998244353 で割った余りで出力してください。
制約
- 1≦|S|≦10^5
- S は問題文中のBNFの
<expr>
で表される式である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
式の計算結果を 998244353 で割った余りを出力せよ。
入力例 1
((1,2)*(3,4))
出力例 1
11
ベクトル (1,2) とベクトル (3,4) の内積を計算すると 1*3 + 2*4 = 11 となります。
入力例 2
((((1*2),3)*4)*(((5,6)*(7,8))*(9,10)))
出力例 2
15936
入力例 3
0000000000099824435399824435399824435399824435399824435398
出力例 3
98
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
文字列 S と Q 個のクエリが与えらます。
i 番目のクエリでは文字列 T_i が与えられるので、T_i を部分列として含むような S の極小な部分文字列のうち最も左にあるものを求めてください。
ただし文字列 s が極小であるとは、s の部分文字列であって T_i を部分列として含むような s より短いものが存在しないことを指すものとします。
制約
- 1≦|S|≦10^5
- 1≦Q≦10^5
- 1≦|T_i|
- |T_i| の和は 10^5 を越えない
- S, T_i は小文字アルファベットのみからなる
入力
入力は以下の形式で標準入力から与えられる。
S Q T_1 T_2 : T_Q
出力
i 番目のクエリの答えの文字列が S の l 文字目から r 文字目までの部分文字列であるとき、i 行目に l,r を空白区切りで出力せよ。ただし、S が T_i を部分列として含まない場合は代わりに -1
を i 行目に出力せよ。
入力例 1
aaxbab 12 ab da subsequence aaxbab a aa aaa aaaa ba x xb xb
出力例 1
2 4 -1 -1 1 6 1 1 1 2 1 5 -1 4 5 3 3 3 4 3 4
1 番目のクエリについて説明します。
答えは 2 文字目から 4 文字目までの部分文字列 axb
となります。
他にも 5 文字目から 6 文字目までの部分文字列 ab
も T_1 を部分列として含む極小な部分文字列ですが、axb
の方が左にあるためこちらは答えとはなりません。
また、aaxb
は極小ではありません。
なぜなら axb
という T_i を部分列として含むような部分文字列を含むためです。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
ツーリストさんは 2 つのリストを持っています。
2 つのリストの長さはいずれも N で、i 個目のリストの j 番目は A_{i,j} です。 A_{i,j} は正または負の整数で、0 ではありません。
ツーリストさんはこれらのリストに対して以下のような操作を行おうとしています。
- まず、2 つのリストに含まれる負の整数を全て正の整数に書き換える。このとき、元々同じだった数は同じ数に、異なっていた数は異なった数に書き換えなければならない。
- 次に、縦 2 マス横 N マスのマス目が書かれた紙を用意し、i 行目 j 列目のマスに i 個目のリストの j 番目の数を書き込む。
- 最後に、隣接したマスに異なる数が書き込まれているような辺と外枠をはさみで切る。すると紙はいくつかのピースに分かれるので、その個数を数える。
ツーリストさんは、うまく負の整数を書き換えることで、分かれるピースの個数をできるだけ少なくしようとしています。 紙はいくつのピースに分かれるでしょうか?
制約
- 1≦N≦10^5
- 1≦|A_{i,j}|≦300
入力
入力は以下の形式で標準入力から与えられる。
N A_{1,1} A_{1,2} ... A_{1,N} A_{2,1} A_{2,2} ... A_{2,N}
出力
紙が分かれたときのピースの個数を出力せよ。
入力例 1
5 1 2 1 2 1 -1 -2 -3 -3 -3
出力例 1
5
例えば -1 を 999 に、-2 を 2 に、-3 を 1 に書き換えると下図のようになり、ピース数は最小の 5 個となります。
入力例 2
15 1 -1 1 -1 -1 -2 2 -1 3 3 3 -3 -2 -2 1 2 -1 1 1 -1 -2 -1 2 -2 3 3 -2 -2 -2 3
出力例 2
9
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
イベルタルは Y 字型のポケモンです。
イベルタルは二次元グリッドの座標 (0,0) にいて、座標 (X,Y) にある巣へ帰ろうとしています。
イベルタルは上・右・左下の三方向に 1 秒で移動することができます。 つまり、座標 (x,y) からは、座標 (x,y+1) または座標 (x+1,y) または座標 (x-1,y-1) に 1 秒で移動することができます。 また、イベルタルは同じ方向に連続で 2 回以上移動することはできません。
このとき、イベルタルが巣に帰るためにかかる秒数の最小値はいくらでしょうか?
制約
- -10^9≦X,Y≦10^9
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
イベルタルが巣に帰るためにかかる秒数の最小値を出力せよ。
入力例 1
2 0
出力例 1
5
図のように移動するのが最短で、5 秒かかります。 同じ方向に 2 回以上連続で移動できない点に注意してください。
入力例 2
-2 -3
出力例 2
7
入力例 3
-1000000000 1000000000
出力例 3
5999999997
入力例 4
0 0
出力例 4
0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
1 辺が 4000 マスのチェス盤があり、その上にルークが N 置かれています。 i 番目のルークは R_i 行目 C_i 列目のマスに置かれています。
それを見た黒猫のスヌケ君は出来るだけ少ない個数のルークを取り除くことによって、どの行や列にもルークが高々 1 個しかないようにしたいと考えました。 スヌケ君はいくつのルークを取り除けばいいでしょうか? また、その個数を達成するために必ず取り除かなければいけないルーク、絶対に取り除いてはいけないルークがどれなのかも求めてください。
制約
- 1≦N≦40000
- 1≦R_i,C_i≦4000
- 同じマスに複数のルークが置かれていることはない
入力
入力は以下の形式で標準入力から与えられる。
N R_1 C_1 R_2 C_2 : R_N C_N
出力
1 行目には取り除くルークの最小個数を出力せよ。 さらに、続く N 行のうち i 行目には、i 番目のルークに関する以下のような値を出力せよ。
- i 番目のルークを必ず取り除かなければならない場合: 1
- i 番目のルークを絶対に取り除いてはいけない場合: -1
- それ以外の場合: 0
入力例 1
6 1 1 1 3 2 1 2 2 2 3 3 2
出力例 1
3 0 0 0 1 0 -1
取り除く個数が最小になるようなルークの取り除き方は下図のような 2 通りが考えられますが、 4 番目のルークはいずれにおいても取り除かれており、6 番目のルークはいずれにおいても取り除かれていません。
入力例 2
9 1 2 2 2 2 1 3 3 4 6 4 5 4 4 5 4 6 4
出力例 2
4 -1 1 -1 -1 0 0 1 0 0
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
約数の和が 98 になるような整数を全て求めてください。
入力
入力は与えられない。
出力
約数の和が 98 になるような整数を全て、昇順に空白で区切ってを出力せよ。
出力例
6 28
これは出力形式の例であり、正しい答えではありません。
ちなみに、6 の約数の和は 1+2+3+6=12 であり、28 の約数の和は 1+2+4+7+14+28=56 となります。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
黒猫のスヌケ君は「パンプキン2」というカードゲームで遊んでいます。
そこでスヌケ君は以下のような問題を考えることにしました。
今、スヌケ君の手元に N 枚のカードがあります。 i 番目のカードのコストは C_i、ゲインは G_i です。
スヌケ君は各カードについて以下のどちらかの操作を 1 度だけ行うことができます。
- 抽出:カードのゲインの値だけマナが増える。ただし、スヌケ君が最初に持っているマナは 0 である。
- 召喚:カードのコストの値だけマナを消費することによって、そのカードを召喚することができる。ただし、マナが足りない場合は召喚を行うことはできない。
操作を行うカードは好きな順番で選ぶことができます。
このとき、スヌケ君が召喚できるカードは最大で何枚でしょうか?
制約
- 1≦N≦10^5
- 0≦C_i≦10^9
- 0≦G_i≦10^9
入力
入力は以下の形式で標準入力から与えられる。
N C_1 G_1 C_2 G_2 : C_N G_N
出力
スヌケ君が召喚できるカードの枚数の最大値を出力せよ。
入力例 1
5 3 0 0 4 2 1 2 0 1 3
出力例 1
3
例えば以下のように操作を行えば、3 枚のカードを召喚することができます。
- 5 番目のカードを抽出する。マナは 3 に増える。
- 3 番目のカードを召喚する。マナは 1 に減る。
- 2 番目のカードを抽出する。マナは 5 に増える。
- 1 番目のカードを召喚する。マナは 2 に減る。
- 4 番目のカードを召喚する。マナは 0 に減る。
入力例 2
7 1 0 2 1 3 1 3 2 3 2 4 0 5 5
出力例 2
3
入力例 3
1 1 0
出力例 3
0
この入力では 1 枚も召喚できません。