Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は、隠れた言葉を探す遊びが好きです。例えば、「じきゅうりょく」の中には「きゅうり」という言葉が隠れています。
高橋君は今、長さ N の文字列の中に隠れた言葉を探そうとしています。隠れた言葉の候補を列挙するためにまず、この文字列の「部分文字列」の個数を計算してみることにしました。
文字列 S の「部分文字列」とは、文字列 S に含まれるある区間を取り出した文字列のことです。例えば、「すぬけ」の部分文字列は「す」「ぬ」「け」「すぬ」「ぬけ」「すぬけ」の 6 つです。「すけ」や「ぬす」などは部分文字列ではないことに注意してください。
また、文字列 S には同じ文字が 2 回以上現れないことが分かっています。そのため「しょうぼうしょ」における「しょ」のように、異なる場所から取り出した文字列が一致することはありません。
入力
入力は以下の形式で標準入力から与えられる。
N
- 1 行目には、文字列の長さを表す整数 N (1 ≦ N ≦ 1000) が与えられる。
出力
長さ N の文字列の「部分文字列」の個数を 1 行に出力せよ。出力の末尾に改行を入れること。
入力例1
1
出力例1
1
入力例2
2
出力例2
3
入力例3
3
出力例3
6
問題文中で示した「すぬけ」の例の通り、6 つの部分文字列があります。
入力例4
4
出力例4
10
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
「foo」や「bar」「hoge」などの、特に意味を持たない変数の名前に使用される文字列のことを「メタ構文変数」と呼びます。
高橋君は今、メタ構文変数について調べています。メタ構文変数には色々な種類があることが分かり、見つけたメタ構文変数にそれぞれに番号をつけました。高橋君はアリの Ant さんと Bug くんのソースコードを読み、それぞれのソースコードに現れるメタ構文変数の番号を列挙しました。そして、Ant さんと Bug くんの使うメタ構文変数の集合がどれくらい似ているのかを調べるために「Jaccard 係数」を計算することにしました。Ant さんのソースコードに現れるメタ構文変数の集合を S_A、Bug くんのソースコードに現れるメタ構文変数の集合を S_B とするとこれらの集合の Jaccard 係数は、
- ||S_{A} ∩ S_{B}|| / ||S_{A} ∪ S_{B}||
という式で計算できます。ここで、||S|| は集合 S の要素数を表すものとします。別の言い方をすると、
- 「S_{A} と S_{B} の両方に現れる要素の個数」/「S_{A} と S_{B} の少なくともどちらか一方には現れる要素の個数」
となります。
入力
入力は以下の形式で標準入力から与えられる。
N_A N_B A_1 A_2 ... A_{N_A} B_1 B_2 ... B_{N_B}
- 1 行目には、2 つの整数 N_A (1 ≦ N_A ≦ 10^5), N_B (1 ≦ N_B ≦ 10^5) が空白区切りで与えられる。これは、Ant さんのソースコードに N_A 個、Bug くんのソースコードに N_B 個のメタ構文変数が現れたということを表す。
- 2 行目には、Ant さんのソースコードに現れたメタ構文変数の番号を表す N_A 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_i (1 ≦ A_i ≦ 10^9) は、Ant さんのソースコードに A_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき A_p \neq A_q であることが保証される。
- 3 行目には、Bug くんのソースコードに現れたメタ構文変数の番号を表す N_B 個の整数が空白区切りで与えられる。このうち i 番目の整数 B_i (1 ≦ B_i ≦ 10^9) は、Bug さんのソースコードに B_i 番のメタ構文変数が現れることを表す。ただし、p \neq q のとき B_p \neq B_q であることが保証される。
部分点
この問題には部分点が設定されている。
- N_A,N_B ≦ 1000 と A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、40 点が与えられる。
- A_i,B_i ≦ 10^5 を満たすテストケース全てに正解した場合は、70 点が与えられる。
出力
Ant さんと Bug くんのソースコードに現れるメタ構文変数の集合の Jaccard 係数を 1 行に出力せよ。小数点以下何桁でも出力してよいが、10^{-6} を超える絶対誤差を含んではならない。出力の末尾に改行を入れること。
入力例1
3 2 1 3 5 1 2
出力例1
0.2500000000
Ant さんと Bug くんのソースコードの両方に現れるメタ構文変数は 1 番のみで、Ant さんと Bug くんのソースコードの少なくともどちらか一方には現れるメタ構文変数は 1,2,3,5 番の 4 つです。
よって、Jaccard 係数は 1/4 となります。
入力例2
9 10 11 2 33 4 55 6 77 8 99 10 11 14 19 55 1000000000 4 5 7 8
出力例2
0.2666666667
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
数の集合 S に対する以下のクエリを処理してください。
- タイプ 1 : S に数 X を追加する。
- タイプ 2 : S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。
入力
入力は以下の形式で標準入力から与えられる。
Q T_1 X_1 T_2 X_2 : T_Q X_Q
- 1 行目には、クエリの個数を表す整数 Q (1 ≦ Q ≦ 200,000) が与えられる。
-
2 行目からの Q 行には、クエリの情報が与えられる。このうち i 行目では、2 つの整数 T_i (1 ≦ T_i ≦ 2), X_i (1 ≦ X_i ≦ 200,000) が空白区切りで与えられる。これは、
- T_i = 1 の場合、「S に数 X_i を追加する」というクエリを表す。ただし、クエリを処理する前の S には X_i が含まれていないことが保証される。
- T_i = 2 の場合、「S に含まれる数のうち X_i 番目に小さい数を答え、その数を S から削除する」というクエリを表す。ただし、クエリを処理する前の S に含まれる数の個数が X_i 個以上であることが保証される。
出力
タイプ 2 のクエリの個数を Q_2 とすると、出力は Q_2 行からなる。このうち i 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。出力の末尾にも改行を入れること。
入力例1
5 1 11 1 29 1 89 2 2 2 2
出力例1
29 89
入力例2
12 1 8932 1 183450 1 34323 1 81486 1 127874 1 114850 1 55277 1 112706 2 3 1 39456 1 52403 2 4
出力例2
55277 52403
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
高橋君は、見たことのない N 次多項式 P(x) を見つけたそうです。この多項式の係数は全て正整数だそうです。高橋君はあなたに P(0) 〜 P(N) の値を教えてくれました。さてここで、あなたは P(T) の値を当てることができるでしょうか。
入力
入力は以下の形式で標準入力から与えられる。
N A_0 A_1 ... A_N T
- 1 行目には、高橋君が見つけた多項式の次数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
- 2 行目には、N+1 個の整数が空白区切りで与えられる。このうち i 番目の整数 A_{i-1} (0 ≦ A_{i-1} ≦ 10^9+6) は、P(i-1) の値を 1,000,000,007 (10^9+7) で割った余りを表す。
- 3 行目には、整数 T (1 ≦ T ≦ 10^9) が与えられる。これは、あなたが当てなければならない値が P(T) であることを表す。
部分点
この問題には部分点が設定されている。
- N ≦ 100 を満たすテストケース全てに正解した場合は、40 点が与えられる。
- N ≦ 3,000 を満たすテストケース全てに正解した場合は、80 点が与えられる。
出力
P(T) の値を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。このような値は一意に定まることが保証される。出力の末尾に改行を入れること。
入力例1
2 1 3 7 3
出力例1
13
このケースでは、P(0)=1,P(1)=3,P(2)=7 であり、x^2+x+1 という多項式が条件を満たします。このとき P(3)=13 であるため 13 を出力します。他にも x^2+x+10^9+8 などの多項式が条件を満たしますが、P(3) を 10^9+7 で割った余りはいずれも 13 となります。
入力例2
5 4 16 106 484 1624 4384 1000000000
出力例2
999984471