A - 塙さん

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

正の整数 X の h 進数での表現が以下の条件を満たすとき X は塙さんであるという。

  • 同じ文字の出現回数は n 回以下である。
  • w 桁である。
  • 0 から始まらない。

塙さんの個数を 1000000007 (十進数) で割った余りを求めよ。

入力

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

h n w
  • 3つの整数 h,n,w がスペース区切りで 1 行に与えられる。
  • 2 \leq h \leq 64
  • 1 \leq n \leq 512
  • 2 \leq w \leq 2048

部分点

  • h \leq 36 かつ n \leq 4 かつ w \leq 4 のケースすべてに正解した場合、部分点として 10 点を与える。

出力

塙さんの個数を 1000000007 (十進数) で割った余りを十進数で標準出力に出力せよ。出力は 1 行とし、末尾には改行をいれること。

入力例1

2 3 4

出力例1

7

二進数表記で、 1000, 1001, 1010, 1011, 1100, 1101, 1110 の 7 つが条件を満たす。

1111 は 1 が 4 回出現するので塙さんではない。

入力例2

10 3 18

出力例2

408595145

Source Name

天下一プログラマーコンテスト2014 本戦
B - 天体位置観測

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

ヨシオくんは天体観測が趣味のナイスガイです。

今夜もいつものように、窓から見える夜空に、自分が考えた星座を見つけて数える遊びを始めました。

ヨシオくんは夜空の星からいくつかの星を選び、それらの星の位置関係が特定の星座と完全に一致した場合に、その星座が1回出現したと数えます。

同じ星座になる星の組み合わせが複数組ある場合、その全てを1つの星座の出現回数として数えます。

また、星座の反転・回転・拡大縮小はしません。

例えば、夜空の星が以下の位置関係である場合を考えます。(oが星のある位置で、.が空白)

o..
.o.
..o

この夜空の中には、

o

という星座は3回出現します。

o.
.o

という星座は2回出現します。このとき、夜空の中央の星は2回使用されます。

o..
...
..o

という星座は1回出現します。星座に存在しない夜空の中央の星は無視します。

o...
....
....
...o

という星座は出現しません。

夜空の星の並びと星座が与えられるので、星座が夜空に何回出現しているか数えるプログラムを作成してください。

入力

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

N M
X1 Y1
:
XN YN
L1
SX1,1 SY1,1
:
SX1,L1 SY1,L1
:
LM
SXM,1 SYM,1
:
SXM,LM SYM,LM
  • 1 行目には、夜空の星の個数 N (1 \leq N \leq 105) と探したい星座の個数 M (1 \leq M \leq 100) が与えられる。
  • 2 行目から N 行は、i 番目の夜空の星の位置の座標 Xi(0 \leq Xi \leq 106) と Yi(0 \leq Yi \leq 106) が与えられる。
  • p \neq q ならば、Xp \neq Xq または Yp \neq Yq を満たす。
  • N+2 行目以降は、下記が M 回繰り返される。
    • j 番目の星座に含まれる星の個数 Lj (1 \leq Lj \leq 100) が与えられる。
    • 続く Lj 行は、j 番目の星座の k 番目の星の位置の座標 SXj,k(0 \leq SXj,k \leq 9) と SYj,k(0 \leq SYj,k \leq 9) が与えられる。
  • p \neq q ならば、SXj,p \neq SXj,q または SYj,p \neq SYj,q を満たす。

部分点

  • N \leq 100のケースすべてに正解した場合、部分点として 40 点を与える。

出力

夜空に表われるそれぞれの星座の出現回数を 1 行づつ合計 M 行で出力せよ。出力の末尾には改行をいれること。

入力例1

3 4
1 1
2 2
3 3
1
0 0
2
0 0
1 1
2
0 0
2 2
2
0 0
3 3

出力例1

3
2
1
0

これは問題文で与えられた例と同じであり、上から順に3, 2, 1, 0となる。

入力例2

11 4
21 11
21 12
21 13
21 14
22 11
23 11
24 11
22 13
23 12
23 13
24 13
3
1 1
2 1
1 2
3
1 1
1 2
2 2
3
3 2
2 3
3 3
3
3 3
4 3
4 4

出力例2

3
2
1
1

与えられた夜空の星は、以下の位置関係である。

oooo
o.o.
oooo
o...

これに対して与えられた星座は、

oo
o.

o.
oo

.o
oo

oo
.o

という配置なので上から順に3, 2, 1, 1となる。

Source Name

天下一プログラマーコンテスト2014 本戦
C - シークエンサー

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

A,T,G,Cのいずれかの文字と任意の 1 文字にマッチするワイルドカード(.)からなる文字列のパターンが N 個与えられる。

1 つのパターンには最大で 1 個のワイルドカードが含まれる。

与えられたパターン全てを部分文字列として含む文字列 X のうち最も短いものの長さを答えよ、ヨシオ君。

入力

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

N
S1
S2
:
SN
  • 1行目には、パターンの数 N(1 \leq N \leq 12) が与えられる。
  • 2行目から N 行には、i番目のパターン Si が与えられる。
  • Si の長さ |Si| は 1 \leq |Si| \leq 600 を満たす。
  • Si はA,T,G,Cのいずれかの文字またはワイルドカード (.) からなる。
  • Si に含まれるワイルドカードの数は最大 1 文字である。

部分点

  • 与えられたパターン全てにワイルドカードが含まれないケースに正解した場合、部分点として 60 点を与える。

出力

最短の文字列 X の長さを 1 行で出力せよ。出力の末尾には改行をいれること。

入力例1

2
TAG
GAT

出力例1

5

最短の文字列 X は TAGATまたはGATAGです。

入力例2

4
AA.
TAT
ATTAC.
TA.T

出力例2

9

最短の文字列 X は AATTACTAT です。

Source Name

天下一プログラマーコンテスト2014 本戦
D - 高橋君

Time Limit: 6 sec / Memory Limit: 256 MB

問題文

文字列 S は、次の条件を満たすとき高橋君であるという。

  • S は、 0, 1のみからなる文字列である。
  • S の長さがちょうど n である。
  • S は高々 k 個の 1 を含む。

高橋君の個数を 1000000007 で割った余りを求めよ。

入力

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

T
n_1 k_1
n_2 k_2
:
n_T k_T
  • 1 行目には、テストケースの数を表す整数 T\ (1≦T≦100000) が与えられる。
  • 2 行目から T 行は、高橋君の条件に関する整数 n, kが、 1 行ごとに与えられる。 このうち i 行目には、 i 番目のテストに対する高橋君の条件 n_i, k_i\ (0≦k_i≦n_i≦100000) が、スペース区切りで与えられる。

出力

高橋君の個数を 1000000007 で割った余りをそれぞれ 1 行ずつ、 T 行で出力せよ。出力の末尾には改行をいれること。

部分点

0≦k_i≦n_i≦3000 の条件を満たすテストケースに全て正解した場合、 50 点が得られる。

全てのテストケースに正解した場合、さらに 150 点が得られる。

高橋君の個数を 1000000007 で割った余りをそれぞれ 1 行ずつ、 T 行で出力せよ。出力の末尾には改行をいれること。

入力例1

10
1 1
3 2
5 2
8 3
12 0
642 246
2222 999
2525 21
50000 25000
100000 100000

出力例1

2
7
16
93
1
321969783
856998846
371661809
969409843
607723520

n=1, k=1 の時、高橋君は、0, 1 の 2 つです。

n=3, k=2 の時、高橋君は、000, 001, 010, 011, 100, 101, 110 の 7 つです。

大きな数の時には、 1000000007 で割った余りを出力することに注意してください。

Source Name

天下一プログラマーコンテスト2014 本戦
E - 田端でバタバタ

Time Limit: 6 sec / Memory Limit: 256 MB

問題文

繰り返し文字列とは、ある空でない文字列 A があって A+A の形で表される文字列のことを表します。言語学では畳語ともいいます。日本語は畳語が非常に多く、通常の文章でも頻繁に出現します。今回はこれを数えてみたいと思います。

小文字アルファベットからなる文字列 S と Q 個のクエリ [a_i,b_i] が与えられます。S[a_i,b_i] の全ての空でない部分文字列のうち、繰り返し文字列となっているものの長さの和を求めてください。同じ文字列が複数存在する場合も、それぞれ別の物として考えてください。

なお、文字列 A と B に対して、連結したものを A+B と表します。また S[x,y] とは、文字列 S の x 文字目から y 文字目までを切り取った部分文字列を表します。

入力

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

S
Q
a_1 b_1
...
a_Q b_Q
  • 1 行目には、文字列 S\ (1 ≦ |S| ≦ 100000) が与えられる。（|S| は文字列 S の長さを表す）
  • 2 行目には、クエリの数を表す整数 Q\ (1 ≦ Q ≦ 100000) が与えられる。
  • 3 行目から Q 行は、クエリの情報が与えられる。 このうち i\ (1 ≦ i ≦ Q) 行目には、 i 番目のクエリの情報を表す整数 a_i, b_i\ (1 ≦ a_i ≦ b_i ≦ |S|) が、スペース区切りで与えられる。

出力

各クエリに対する答えを、 1 行ずつ Q 行で出力せよ。出力の末尾には改行をいれること。

部分点

1 ≦ |S| ≦ 1000 のテストケースに全て正解した場合 、部分点として 100 点が与えられる。

1 ≦ |S| ≦ 20000 のテストケースに全て正解した場合 、部分点としてさらに 100 点が与えられる。

全てのテストケースに正解すると、さらに 150 点が与えられる。

入力例1

kokoropyonpyon
3
1 14
2 14
1 13

出力例1

12
8
4

kokoとpyonpyonが繰り返し文字列に相当します。

1 つ目のクエリでは、kokoropyonpyonについて考えます。koko、pyonpyonの 2つの繰り返し文字列が存在するので、答えは 12 です。

2 つ目のクエリでは、okoropyonpyonについて考えます。pyonpyonが存在するので、答えは 8 です。

3 つ目のクエリでは、kokoropyonpyoについて考えます。kokoが存在するので、答えは 4 です。

入力例2

rattatta
5
2 7
3 8
3 4
3 3
1 8

出力例2

10
10
2
0
16

attatt, ttatta, tt, ttが、繰り返し文字列に該当します。tt 2 個は別物とします。

入力例3

aaaaaaaaaa
1
1 10

出力例3

110

大量の繰り返し文字列が発生するケースが存在することに注意してください。

Source Name

天下一プログラマーコンテスト2014 本戦