A - IOI列車で行こう2

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

E869120国ではIOI国に続き, 新たに鉄道を敷設した。

E869120国の鉄道を走る列車はいくつかの車両が連結されたものであり, 車両には I, O の 2 種類がある。

しかし, 次のような規則でつながなければならない。

  • 車両はそれぞれ異なる種類の車両としか連結できない。
  • 列車に運転席を設ける関係上，列車の両端の車両は種類 I でなければならない。

列車は車両の種類を表す文字を順につなげた文字列で表され, 列車の長さはその文字列の長さであるとする。

例えば, IOIOI , IOIOIOIOIOIOIOIOI などが条件を満たす。

今, 車庫には文字列 S で表されるような車両が連結された状態がある。

編成する車両は, S の部分列でなければならない。

そのとき, 最大で何両の列車が編成できるだろうか。

入力

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

S
  • 1 行目には、車庫の状態を表す文字列 S が与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • 編成できる車両の両数を 1 行で出力せよ。
  • ただし, 列車が編成できない場合は 0 と出力せよ。

制約

  • 1≦|S|≦50,000

小課題

小課題 1 [ 25 点 ]

  • 1 ≦ | S | ≦ 100 を満たす。

小課題 2 [ 75 点 ]

  • 追加の制約はない。

入力例1

IOOIIOIOIIOI

出力例1

9
  • 1, 2, 4, 6, 7, 8, 9, 11, 12 両目を選べば, 列車「 IOIOIOIOI 」が作れます。

入力例2

IOIOIIOIOI

出力例2

9
  • 1, 2, 3, 4, 5, 7, 8, 9, 10 両目を選べば, 列車「 IOIOIOIOI 」が作れます。

入力例3

IIOOII

出力例3

3

問題文担当者:square1001

B - Division 2

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

うさぎは, プログラミングコンテストで今 Division 2 であり, なかなか Division 1 に上がれない。

そのため, うさぎは整数を 2 で割ることに対して恨みを持っている。

ところで, 今, うさぎは, 1 から n までの数字を黒板に書き, 以下の操作を q 回しようとしている。

  • i 回目の操作のとき, 黒板に書かれている数の中で a_i で割り切れるものがあればその数を a_i で 1 回だけ割る。

最終的に 1 が何個残るでしょうか？

入力

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

n q
a_1
:
a_q
  • 1 行目には, 黒板に書く数の個数n と処理の回数qが空白区切りで与えられる。
  • 2 行目から, q 行にわたって a_i が与えられる。 a_i は i 番目の処理で割る数を表す。

出力

出力は以下の形式で標準出力に従うこと。

  • 最終的に、黒板に「1」が何個書かれているか、1行で出力してください。

制約

  • 1 ≦ n ≦ {10}^{13}
  • 1 ≦ q ≦ 24
  • 3 ≦ a_i ≦ 50

小課題

小課題 1 [ 25 点 ]

  • 1≦n≦10^6 を満たす。

小課題 2 [ 75 点 ]

  • 追加の制約はない。

入力例1

7 2
3
6

出力例1

2

数字は以下のように変化する。

1 2 3 4 5 6 7
3で割る 1 2 1 4 5 2 7
6で割る 1 2 1 4 5 2 7

よって、1,3の2つの場合最終的に1になる。

入力例2

7 2
6
3

出力例2

3

数字は以下のように変化する。

1 2 3 4 5 6 7
6で割る 1 2 3 4 5 1 7
3で割る 1 2 1 4 5 1 7

よって、1,3,6の3つの場合最終的に1になる。

入力例3

8 4
4
8
16
32

出力例3

2

数字は以下のように変化する。

1 2 3 4 5 6 7 8
4で割る 1 2 3 1 5 6 7 2
8で割る 1 2 3 1 5 6 7 2
16で割る 1 2 3 1 5 6 7 2
32で割る 1 2 3 1 5 6 7 2

よって、1,4の2つの場合最終的に1になる。

入力例4

50 4
8
6
4
3

出力例4

9

問題文担当者:square1001

C - 何通りの分割方法がある？

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

square1001の部分文字列である「1001」は、各位の数字の和が1+0+0+1=2と非常に少なく、

しかも「1001」を分割しても{1,0,01}や{1,001}のようにすると和がそれぞれ1+0+1=2,1+1=2と非常に少なくなります。

1001はとても不思議な数です。それについて、彼は考えてみることにしました。

整数nを分割するとき、その和がD以下にならなければなりません。

ここでいう「分割」の定義は以下のようになります。

  • 整数Nを文字列と考えられる。これをSと置く。
  • Sをいくつかのパーツに分ける。
  • 例えば「"1234567"」だと{"1","234567"}や{"12","34","56","7"}や{"1234567"}など、というように分けることができる。
  • 分けたパーツをそれぞれ数字としてとらえるようにする。
  • 例えば、"1234"は1234という数字ととらえることができる。
  • ただし、各パーツは0から始まってもよい。

例えば、「1355」を和が50以下になるように分割する方法は、以下の3通りがあります。

分割方法合計
1+3+5+514
13+5+523
1+35+541

何通りの分け方があるか数え上げましょう。1,000,000,007で割った余りを求めなさい。

入力

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

N
D
  • 1 行目には、分割されるもののもととなる整数 N が与えられる。
  • 2 行目には、数の合計の上限 Dが与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • 分割の通り数を1,000,000,007で割った余りを 1 行で出力せよ。

制約

  • 1≦N≦{10}^{100}
  • 1≦D≦100,000

小課題

小課題 1 [ 10 点 ]

  • 解は全て1通り以下である。

小課題 2 [ 30 点 ]

  • 1≦N≦10,000,000,000を満たす。

小課題 3 [ 60 点 ]

  • 追加の制約はない。

入力例1

1355
50

出力例1

3
  • 問題文中の例と同じである。

入力例2

2439
100

出力例2

5
  • 以下の5通りの条件を満たす分け方がある。
分割方法合計
2+4+3+918
24+3+936
2+4+3945
2+43+954
24+3963

入力例3

1225
20

出力例3

2

入力例4

123456
10000

出力例4

29

問題文担当者:E869120

D - 2016

Time Limit: 3 sec / Memory Limit: 128 MB

問題文

今年の 8 月 5 日から, リオデジャネイロオリンピックが開催される。

夏季オリンピックは, 4 の倍数の年に開催されることになっている。

また, 今年の 5 月 26 日に, 伊勢志摩サミットが開催される。

日本で開催されるサミットは, 2000, 2008, 2016,... 年と, 近年では 8の倍数となっている。

とにかく, 今年は「約数が多い」。なんと, 36 個もの約数があるのだ。

これは, 世の中のだれもが思っていることであろう。なぜなら, このような「約数の多い年」は, めったに経験しないことであるからだ。

中学 2 年生の私でさえ, これを重く受け止めているのであるから。

そこで, 私は皆さんに次のような問題を出す。

「 1 以上 n 以下の整数の中で, 最も約数が多い数と, その約数の個数を求めなさい。」

未来の人々のためにも, この問題を解いてあげましょう。

入力

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

Q
n_1
:
n_Q
  • 1 行目には、クエリの数 Q が与えられる。
  • 2行目からQ行にわたって、整数 nが与えられる。
  • n_iとは、i回目のクエリにおけるnを表す。

出力

出力は以下の形式で標準出力に従うこと。

  • n以下の整数の中で最大の約数の個数と、その約数の個数を持つ数のなかで最小の整数を空白区切りで出力すること。
  • 例えばn=96のとき、約数が12個の数字は60,72,84,90,96の5つありますが、その中で最小の60を最小の整数として出力します。
  • この場合、この行は"12 60"という出力となります。
  • 各クエリごとに出力するため、出力はQ行からなる。

制約

  • 1≦n≦{10}^{17}
  • 1≦Q≦1,000

小課題

小課題 1 [ 8 点 ]

  • 1≦n≦10,000を満たす。
  • Q≦100を満たす。

小課題 2 [ 34 点 ]

  • 1≦n≦1,000,000,000を満たす。
  • Q≦100を満たす。

小課題 3 [ 58 点 ]

  • 追加の制約はない。

入力例1

1
50

出力例1

10 48

48の約数は{1,2,3,4,6,8,12,16,24,48}の10個である。

入力例2

1
96

出力例2

12 60

問題文中の例と同じである。

入力例3

3
240
480
1200

出力例3

20 240
24 360
32 840

840は1から8まですべて割り切れる最小の数である。

また、出力はクエリごとに改行することに注意せよ。

入力例4

2
2016
423

出力例4

40 1680
24 360

2016はとても約数が多いが、1680の約数の個数にはかなわない。

また、今日は2016年4月23日である。ちなみに、423の約数の個数は6個である。

問題文担当者:E869120

E - 部分文字列

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

square1001「E869120は全て文字のcharacterが違うが、square1001は文字のcharacterが一致するものが2個もある！」

E869120「ということは、部分文字列の種類数も違うのでは…」

square1001「たとえば1001では、2文字目だけの'0'と3文字目だけの'0'が重複しているのではないか！('1'もそうです)」

ということで、今回は文字列Sの部分文字列を全て列挙し、文字列の重複を1つにまとめて数えたときのの文字数の合計を求めてください。

例えば、"aba"のとき、{"a","b","a","ab","ba","aba"}の6通りが考えられますが、"a"は重複しているので、

部分文字列としては5種類が考えられます。

{"a","b","ab","ba","aba"}の合計1+1+2+2+3= 9文字となります。

注意：答えは32ビット整数型に収まらない可能性があります。

入力

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

S
  • 1 行目には, 調べる文字列S が与えられる。

出力

出力は以下の形式で標準出力に従うこと。

  • 部分文字列として考えられる文字列(重複は1つにまとめて数える)の合計の長さを1行で出力してください。
  • ただし、答えは32ビット整数型に収まらない可能性があります。

制約

  • 1 ≦ |S| ≦ 100,000
  • 含まれる文字の種類はalphabetの小文字だけ

小課題

小課題 1 [ 15 点 ]

  • 1≦|S|≦100 を満たす。

小課題 2 [ 35 点 ]

  • 1≦|S|≦2,000 を満たす。

小課題 3 [ 50 点 ]

  • 追加の制約はない。

入力例1

abc

出力例1

10
  • a, b, c, ab, bc, abc が abc の部分文字列であり, 合計は 10 文字である。

入力例2

aaqqz

出力例2

33
  • 重複があることに注意してください。

入力例3

atcoder

出力例3

84

問題文担当者:square1001

F - Range Sum Queries

Time Limit: 1 sec / Memory Limit: 128 MB

問題文

数列Aがあります。

A={{b}^{0},{b}^{1},{b}^{2},…,{b}^{a-1}}とします。

c 回, 次のような操作をする。

  • すべての i に対して, A_i= current A_0+A_1+,...+A_iとする。

例えば、a=4,b=3,c=2のとき、次のようになります。

1 3 9 27
1回目 1 4 13 40
2回目 1 5 18 58

一番最後の操作が終わったときのA_{a-1}の値を1,000,000,007で割った余りを出力してください。上の例の場合、答えは58となります。

入力

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

a b c
  • 1 行目には, a,b,c が空白区切りで与えられる。
  • aは数列の長さです。
  • bは、数列の初期値に関係する定数です。i番目の要素は、{b}^{i}です。一番左を0番目とします。
  • cは、操作をする回数です。

出力

出力は以下の形式で標準出力に従うこと。

  • c 回操作をした後の数列の最後の要素の値を1,000,000,007で割った余りを1行に出力してください。

制約

  • 1≦a≦100,000
  • 1≦b,c≦1,000,000,000

小課題

小課題 1 [ 12 点 ]

  • 1≦a,b,c≦1,000 を満たす。

小課題 2 [ 48 点 ]

  • 1≦a,b,c≦100,000を満たす。

小課題 3 [ 40 点 ]

  • 追加の制約はない。

入力例1

4 3 2

出力例1

58

問題文中の例と同じです。

入力例2

6 1 5

出力例2

252

以下のようになります。

1 1 1 1 1 1
1回目 1 2 3 4 5 6
2回目 1 3 6 10 15 21
3回目 1 4 10 20 35 56
4回目 1 5 15 35 70 126
5回目 1 6 21 56 126 252

入力例3

123 456 789

出力例3

271208111

1,000,000,007で割った余りを求めることに注意してください。

問題文担当者:E869120

G - 道とN個のAtCoder社

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

Atcoder運送会社には、N個の工場が存在します。

217X年、この会社では、1つだけ困っていることがあります。これは、会社と会社を結ぶ道が存在しないことです。

運送会社社長「これは大問題だ!!すぐにでも直さないとやばいぞ!!」

よって、今すぐ計画を立てることになりました。

この会社は、運送関連のことをやっているため、製品を地方から都市、都市から地方へ迅速に運ばなければなりません。そのため、会社専用の道を作ると多くの注文にも対応できます。

ただし、以下のような条件で道を作る必要があります。

  • できるだけ運送トラックの制限速度を上げるために、道路は直線にする必要があります。
  • 立体交差をすると大幅に費用が増えるので、道と道は工場以外で交差してはいけません。
  • そのように全ての専用道路の制限速度を速くした上で、できるだけ目的の会社に速く速く運びたいので、 できるだけ道をつくります。
  • 道は工場と工場の間をつなぐものとします。

ただ、会社は最適解を導き出す方法がわかりませんでした。

そこで、優秀なプログラマーであるあなたに、最適解を探してくれと会社から頼まれました。最大で道が何本建てられるか求めてください。

ただし、問題文中の条件は厳守するものとします。

注意:問題文中の217X年は、時空を超えた世界での時間とします。ここでの時間は今現在とみなしてよいでしょう。

入力

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

N
x_1 y_1
: :
x_N y_N
  • 1 行目には, 工場の総数 N が与えられる。
  • 2 行目からN+1行目にかけて、工場iの座標(x_i,y_i)が与えられます。

出力

出力は以下の形式で標準出力に従うこと。

  • 最大で何本の道を建てられるか、1行で出力してください。

制約

  • 1≦N≦2,000
  • 0≦x_i,y_i≦1,000,000,000
  • 3工場が一直線上に並ぶことはない。

小課題

小課題 1 [ 14 点 ]

  • 1≦N≦4 を満たす。

小課題 2 [ 50 点 ]

  • 1≦N≦100を満たす。

小課題 3 [ 36 点 ]

  • 追加の制約はない。

入力例1

4
0 0
1 1
0 1
1 0

出力例1

5

点{(1,2),(1,3),(2,3),(1,4),(2,4)}を結べば5本の道を条件を満たして作ることができる。

入力例2

4
0 0
1 2
2 0
1 1

出力例2

6

この場合、全ての辺を結ぶことができます。

問題文担当者:E869120

H - Counting 1's

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

長さnの数列があります。

そして、クエリがQ個与えられます。

各クエリごとに、q_iが与えられます。

・q_iが1のとき、範囲l_i≦i＜r_iの範囲のビットを反転させます。

・q_iが2のとき、範囲l_i≦i＜r_iの範囲に1が何個存在するか出力します。

このようなクエリを処理するプログラムを書いてください。

ただし、初期値はすべての位置で0とし、一番最初を0番目とします。

たとえば、n=7,q_i,l_i,r_iが以下の表のような場合、ビットの状態は以下のようになります。

{q_i,l_i,r_i} 0 0 0 0 0 0 0 出力値
{1,2,5} 0 0 1 1 1 0 0 -
{1,4,7} 0 0 1 1 0 1 1 -
{2,1,6} 0 0 1 1 0 1 1 3
{1,0,4} 1 1 0 0 0 1 1 -
{2,3,7} 1 1 0 0 0 1 1 2
{1,2,6} 1 1 1 1 1 0 1 -
{2,0,7} 1 1 1 1 1 0 1 6

よって、出力は以下のようになります。

3
2
6

入力

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

n Q
q_1 l_1 r_1
:  : :
q_Q l_Q r_Q
  • 1 行目には, 数列の長さn とクエリの数Qが空白区切りで与えられます。
  • 2 行目からQ+1行目にかけて、q_i,l_i,r_iが空白区切りで与えられます。
  • q_iはクエリの種類、l_i,r_iはそれぞれ左端、右端の位置です。
  • ただし、求める(または反転させる)範囲は右端-1の位置までなので注意すること。

出力

出力は以下の形式で標準出力に従うこと。

  • 各出力クエリごとに、l_i≦(位置)＜r_iの範囲の1の個数を出力してください。
  • 各クエリごとに、改行を忘れないこと。

制約

  • 1≦n,Q≦100,000
  • 0≦l_i＜r_i≦n
  • 1≦q_i≦2

小課題

小課題 1 [ 4 点 ]

  • 1≦n,Q≦1,000 を満たす。

小課題 2 [ 12 点 ]

  • 出力クエリの数は1,000個以内である。

小課題 3 [ 36 点 ]

  • 出力クエリのl_i,r_iは、それぞれ0,nである。

小課題 4 [ 48 点 ]

  • 追加の制約はない。

入力例1

8 4
1 3 7
2 2 5
1 2 4
2 1 6

出力例1

2
3

数列の値は、以下のように変化します。

{q_i,l_i,r_i} 0 0 0 0 0 0 0 0 出力値
{1,3,7} 0 0 0 1 1 1 1 0 -
{2,2,5} 0 0 0 1 1 1 1 0 2
{1,2,4} 0 0 1 0 1 1 1 0 -
{2,1,6} 0 0 1 0 1 1 1 0 3

入力例2

5 3
1 0 3
1 2 5
2 1 4

出力例2

2

数列の値は以下のように変化します。

{q_i,l_i,r_i} 0 0 0 0 0 出力値
{1,0,3} 1 1 1 0 0 -
{1,2,5} 1 1 0 1 1 -
{2,1,4} 1 1 0 1 1 2

入力例3

7 7
2 3 4
1 4 6
2 1 5
1 0 7
1 2 5
2 0 7
1 2 3

出力例3

0
1
4

問題文担当者:square1001