実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 200 点
問題文
すぬけ君は、店を開こうとしています。N 個の商品を販売する予定です。 i 番目の商品は、p_i 円で販売されます。
すぬけ君は、それぞれの価格の末尾についた 0
をたくさん書くのが大変に感じたので、
N 個全ての商品の値札の末尾に連続する 0
を全ての商品について同じ個数だけ取り除き、
会計の時にその分の 0
を補完することにしました。
商品の値札 1 枚あたり、 0
を最大何個取り除けるかを求めてください。
制約
- 1 ≤ N ≤ 100
- 1 ≤ p_i ≤ 10^9
- p_i は整数
入力
入力は以下の形式で標準入力から与えられる。
N p_1 : p_N
出力
商品の値札 1 枚あたり、 0
を取り除ける個数の最大値を出力せよ。
入力例 1
4 300 250 6000 730
出力例 1
1
それぞれ、末尾についた 0
を 1 つだけ取り除くことができ、すると値札には 30, 25, 600, 73 と書かれることになります。
入力例 2
5 10000000 30000000 150000000 200000000 990000000
出力例 2
7
入力例 3
4 100101100 110010000 100001001 110011000
出力例 3
0
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 400 点
問題文
あなたはオンサイトコンテストの運営担当者です。 このコンテストの参加者は N 人おり、1, 2, ..., N の番号が付けられています。 参加者 i は x 軸上の座標 X_i の位置に住んでいます。
あなたはコンテストの参加者に会場までの交通費を支給することを検討しています。 参加者 i への支給額は、コンテスト会場の位置 c と基準値 d から以下のように定めることにしています。
- |X_i - c| \leq d のとき、|X_i - c| 円
- そうでないとき、d 円
会場の位置 c と基準値 d を定めるにあたって、Q 種類のこれらの値の候補に対して、参加者に支給する交通費の合計を計算することにしました。
整数 C_1, C_2, ..., C_Q および D_1, D_2, ..., D_Q が与えられます。 i = 1, 2, ..., Q に対して、c = C_i, d = D_i としたときの参加者に支給する交通費の合計を求めてください。
制約
- 1 \leq N \leq 10^5
- 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
- X_i < X_{i + 1} (1 \leq i < N)
- 1 \leq Q \leq 10^5
- 0 \leq C_i, D_i \leq 10^9 (1 \leq i \leq Q)
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N Q X_1 X_2 ... X_N C_1 D_1 C_2 D_2 : C_Q D_Q
出力
Q 行出力せよ。 このうち i 行目 (1 \leq i \leq Q) には、c = C_i, d = D_i のときの答えを出力せよ。
入力例 1
5 3 1 5 10 20 30 7 3 10 20 100 10
出力例 1
14 44 50
たとえば、c の値を C_1 = 7 に、d の値を D_1 = 3 にした場合、 各参加者に交通費としてそれぞれ 3 円、2 円、3 円、3 円、3 円を支給することになります。 よって 1 行目には 3 + 2 + 3 + 3 + 3 =14 を出力します。
入力例 2
6 3 0 1 2 999999998 999999999 1000000000 0 0 100 99 1000000000 1000000000
出力例 2
0 593 3000000000
入力例 3
7 5 590 593 633 642 743 859 872 642 850108511 743 153 633 20 642 0 842 60895346
出力例 3
658 759 109 0 1056
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 500 点
問題文
(
と )
からなる文字列 S が与えられます。次の条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組はいくつあるでしょうか。
条件: - S の i 文字目から j 文字目まで (両端を含む) を取り出した時、その文字列は括弧の対応が取れている。
括弧の対応が取れている文字列とは、次のうちいずれかの条件を満たす文字列です。
- 空文字列
- ある括弧の対応が取れている文字列 A, B が存在し、 A, B をこの順に連結した文字列
- ある括弧の対応が取れている文字列 A が存在し、
(
, A,)
をこの順に連結した文字列
制約
- 1 ≤ |S| ≤ 10^5
- S は
(
,)
のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
条件を満たす整数 (i,j) (1 ≤ i ≤ j ≤ |S|) の組の個数を出力せよ。
入力例 1
((())
出力例 1
2
- S の 2 文字目から 5 文字目までを取り出すと、
(())
です。これは括弧の対応が取れています。 - S の 3 文字目から 4 文字目までを取り出すと、
()
です。これは括弧の対応が取れています。
よって、 (2, 5) および (3, 4) が条件を満たします。
入力例 2
(()()(())(
出力例 2
7
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 600 点
問題文
長さ N の 2 つの整数列 (A_1, A_2, ..., A_N), (B_1, B_2, ..., B_N) があります. あなたは,数列 A に対して次の操作を繰り返し行うことができます:
- 整数 i (1 \leq i \leq N-1) を選ぶ.そして,A_i を A_i xor A_{i+1} に置き換えるか,A_{i+1} を A_i xor A_{i+1} に置き換えるかのいずれかを行う.
ただし,xor はビットごとの排他的論理和を表します.
この操作を繰り返すことで,A と B を一致させることができるかを判定してください.
制約
- 1 \leq N \leq 100000
- A_i, B_i は整数
- 0 \leq A_i \leq 2^{60} - 1
- 0 \leq B_i \leq 2^{60} - 1
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N B_1 B_2 ... B_N
出力
問題文中の操作の繰り返しで,A と B を一致させることができるなら Yes
を,できないなら No
を出力せよ.
入力例 1
4 4 6 1 2 4 0 3 2
出力例 1
Yes
はじめ,A は (4, 6, 1, 2) です.
- i=2 を選んで,A_2 を A_2 xor A_3 で置き換えると,A は (4, 7, 1, 2) になります.
- i=1 を選んで,A_2 を A_1 xor A_2 で置き換えると,A は (4, 3, 1, 2) になります.
- i=3 を選んで,A_3 を A_3 xor A_4 で置き換えると,A は (4, 3, 3, 2) になります.
- i=2 を選んで,A_2 を A_2 xor A_3 で置き換えると,A は (4, 0, 3, 2) になります.
よって,A と B を一致させることができます.
入力例 2
5 1 1 1 1 1 2 2 2 2 2
出力例 2
No
どのように操作をしても,A と B を一致させることはできません.
入力例 3
10 9078757738433288 290842434722050 159090006056 289488767243292968 141906289967362 3848861155586 19265097448903424 5761445266577952 616899717105952 343731622434 546704308666859716 487893585065153542 489415167130509384 152982254363317262 324189516636095686 286066742397022348 90758284568626244 239298268501286990 196514071259067468 466853324654813188
出力例 3
No
入力例 4
12 377856130335197936 431521378213127644 96779183645318069 27884533191077098 175463727782485301 417798313887768470 882780118961099438 695638305642195413 844098458810131862 714758857685818365 982440320392901313 58851425009165345 200247916520409945 1079265167001944511 228890967431065270 594413217207808713 799020374004987514 1064838643421037658 816982417931746301 59262707979926837 802875123164857614 244683246935893681 50108983568402635 248665965512365971
出力例 4
Yes
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 700 点
問題文
(
, )
, +
, -
, *
, a
のみからなる数式 S が与えられます(詳細は問題文の後半を参照してください)。S に含まれる a
の個数を N とします。
N 個の整数 a_1, ..., a_N と 2 個の整数 (b_i, x_i) からなる Q 個のクエリが与えられるので、これらのクエリを処理してください。
クエリ: 与えられた数式中の左から b_i 番目の a
を x_i に、左から 1, ..., b_i-1, b_i+1, ..., N 番目の a
をそれぞれ a_1, ..., a_{b_i-1}, a_{b_i+1}, ..., a_N に置き換えた数式の値と 10^9+7 を法として合同な 0 以上 10^9+6 以下の整数を出力する。
この問題で与えられる数式 S は、以下のような BNF 表記の <expr>
シンボルで表されます。
<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term> <term> ::= <value> | <term> '*' <value> <value> ::= 'a' | '(' <expr> ')'
制約
与えられる数式に含まれる a
の個数を N とします。
- S の長さは 200\,000 以下
- S は問題文中の BNF 表記の
<expr>
シンボルとして表せる - 0 ≤ a_i < 10^9+7
- 1 ≤ Q ≤ 10^5
- 1 ≤ b_i ≤ N
- 0 ≤ x_i < 10^9+7
- x_i は整数
入力
入力は以下の形式で標準入力から与えられる。
S Q a_1 ... a_N b_1 x_1 : b_Q x_Q
出力
Q 行出力せよ。 i 行目 (1 ≤ i ≤ Q) には、i 番目のクエリの答えを出力せよ。
入力例 1
(a-(a))*a 4 0 1 2 1 1 1 2 2 1 1 4
出力例 1
0 2 1000000005 6
例えば最初のクエリでは、左から 1 番目の a
には x_1 = 1 が、左から 2 番目の a
には a_2 = 1 が、左から 3 番目の a
には a_3 = 2 を代入し、計算すると、 (1-(1))*2 = 0 となり、0 が答えです。
3 番目ののクエリでは、左から 1 番目の a
には a_1 = 0 が、左から 2 番目の a
には x_3 = 1 が、左から 3 番目の a
には a_3 = 2 を代入し、計算すると、 (0-(1))*2 = -2 となり、10^9+7 を法として -2 と合同な 0 以上 10^9+6 以下の整数である、10^9+5 が答えです。
入力例 2
(a)*a+((a+(a*(a))-(a)*a+a*a))*a 10 8 6 6 4 8 1 4 3 8 9 3 4 3 9 8 4 3 7 4 0 8 9 3 6 9 0 6 8 9 4
出力例 2
552 597 642 579 282 1002 570 354 318 462
実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 800 点
問題文
すぬけ君は、Q 日間にわたって、毎日次のようなパズルを解こうとしています。
- すぬけ君の持っている端末に、縦 H 行、横 W 列からなる格子状の盤面が毎日配信されてくる。それぞれのマスは白または黒で塗られている。ただし、i+1 日目 (1 ≤ i ≤ Q-1) に配信されてくる盤面は、i 日目に配信される盤面の上から r_i 行目で左から c_i 列目のマスの白黒が反転したものである。
- 配信されてきた盤面に対し、すぬけ君ははじめに最大 1 回、盤面の中の長方形領域を指定し、領域中の全てのマスの白黒を反転させる。
- その後、すぬけ君は 1 つの行または列を選び、その中の全てのマスの白黒を反転させるという操作を好きな回数だけ行える。
- 盤面の全てのマスを同じ色にすることが目的である。
すぬけ君は賢いので、配信されてくる盤面の中には絶対に解けないものが存在することに勘付いています。そこで、すぬけ君の代わりに、それぞれの日の盤面について、盤面の全てのマスを同じ色にする方法が存在するかどうかを判定してください。
ただし、1 日目に配信される盤面は、上から i 行目 (1 ≤ i ≤ H) で左から j 列目 (1 ≤ j ≤ W) のマスは、s_{ij} が .
のとき白に、 #
のとき黒に塗られています。
制約
- 1 ≤ H ≤ 2\,000
- 1 ≤ W ≤ 2\,000
- 1 ≤ Q ≤ 300\,000
- s_{ij} は
.
または#
- 1 ≤ r_i ≤ H (1 ≤ i ≤ Q-1)
- 1 ≤ c_i ≤ W (1 ≤ i ≤ Q-1)
入力
入力は以下の形式で標準入力から与えられる。
H W Q s_{11}s_{12}...s_{1W} : s_{H1}s_{H2}...s_{HW} r_1 c_1 : r_{Q-1} c_{Q-1}
出力
Q 行出力せよ。
i 行目 (1 ≤ i ≤ Q) には、i 日目の盤面の全てのマスを同じ色にする方法が存在する場合 Yes
を、そうでない場合 No
を出力せよ。
入力例 1
3 4 4 ...# .### .#.# 3 1 2 4 2 2
出力例 1
No No No Yes
4 日目の盤面が、全てのマスを同じ色にする方法が存在する盤面です。
...# ..#. ##.#
この盤面からは、以下のようにして全てのマスを白にできます。
- 盤面の右下端の 2 行 2 列の長方形領域を反転させる。
- 上から 3 行目の全てのマスを反転させる。
- 左から 4 列目の全てのマスを反転させる。
入力例 2
4 4 5 #### #### .... #### 2 2 3 2 2 3 3 3
出力例 2
Yes Yes Yes No Yes
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1100 点
問題文
整数 N および M 個の整数の 3 つ組 (A_i, B_i, C_i) (1 \leq i \leq M) が与えられます。 1, 2, ..., N の置換 p であって、すべての i (1 \leq i \leq M) に対して以下の条件を満たすものの個数を 10^9 + 7 で割ったあまりを求めてください。
- 長さ N の置換をすべて辞書順に並べたとき p の A_i 個あとにあたる置換 q = [q_1, q_2, ..., q_N] が存在し、q_{B_i} = C_i である。
なお、上の条件において、A_i = 0 のとき q は p 自身であるとします。
制約
- 1 \leq N \leq 50
- 0 \leq M \leq 50
- 0 \leq A_i \leq 50 (1 \leq i \leq M)
- A_i \leq N! - 1 (1 \leq i \leq M)
- 1 \leq B_i, C_i \leq N (1 \leq i \leq M)
- i \neq j のとき、A_i \neq A_j または B_i \neq B_j または C_i \neq C_j
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 C_1 A_2 B_2 C_2 : A_M B_M C_M
出力
答えを出力せよ。
入力例 1
3 1 1 2 2
出力例 1
1
1, 2, 3 の置換をすべて辞書順に並べると [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] となります。 このうち条件を満たす置換は [3, 1, 2] だけです。
入力例 2
10 2 10 10 10 11 10 10
出力例 2
0
入力例 3
20 2 0 1 1 50 1 2
出力例 3
50
入力例 4
50 0
出力例 4
318608048
入力例 5
30 5 27 18 22 43 19 26 27 26 13 22 9 27 31 20 12
出力例 5
440732388
実行時間制限: 4 sec / メモリ制限: 256 MB
配点 : 1400 点
問題文
xy 平面上の点 P が格子点であるとは、点 P の x 座標および y 座標がともに整数であることをいいます。
xy 平面上の三角形 ABC について、関数 f(ABC) を三角形 ABC の内部 (周上は含まない) に存在する格子点の個数とします。
8 個の整数 X_1, Y_1, X_2, Y_2, X_3, Y_3 および W, H が与えられます。
以下の条件を満たす三角形 ABC すべてについての f(ABC) の値の和を 10^9 + 7 で割ったあまりを求めてください。
- 頂点 A の x 座標は X_1 以上 X_1 + W 未満の整数であり、y 座標は Y_1 以上 Y_1 + H 未満の整数である。
- 頂点 B の x 座標は X_2 以上 X_2 + W 未満の整数であり、y 座標は Y_2 以上 Y_2 + H 未満の整数である。
- 頂点 C の x 座標は X_3 以上 X_3 + W 未満の整数であり、y 座標は Y_3 以上 Y_3 + H 未満の整数である。
制約
- 0 \leq X_i, Y_i \leq 10^{12} (1 \leq i \leq 3)
- 1 \leq W, H \leq 40\,000
- X_1 + W \leq X_3
- X_3 + W \leq X_2
- Y_1 + H \leq Y_2
- Y_2 + H \leq Y_3
入力
入力は以下の形式で標準入力から与えられる。
X_1 Y_1 X_2 Y_2 X_3 Y_3 W H
出力
答えを出力せよ。
入力例 1
0 0 4 1 2 3 2 1
出力例 1
32
下の図における f(A_iB_jC_k) (i, j, k \in \{1, 2\}) の和を 10^9 + 7 で割ったあまりを求めれば良いことになります。
- f(A_1B_1C_1) = 4
- f(A_1B_1C_2) = 3
- f(A_1B_2C_1) = 6
- f(A_1B_2C_2) = 4
- f(A_2B_1C_1) = 3
- f(A_2B_1C_2) = 3
- f(A_2B_2C_1) = 5
- f(A_2B_2C_2) = 4
より、答えはこれらの和を 10^9 + 7 で割ったあまりである 32 となります。
入力例 2
1 2 100 50 50 100 10 10
出力例 2
669378679
入力例 3
100 100 10000 1000 1000 10000 99 101
出力例 3
69068642
入力例 4
0 0 1000000000000 100000000000 100000000000 1000000000000 1 1
出力例 4
24258851
入力例 5
83014267509 107013567012 918384543326 586909285896 391608717054 614178832969 40000 40000
出力例 5
569338479