A - Area Sum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 行 M 列からなる盤面があり，各マス目には row-major 順に 1 から N \times M までの整数が書かれています． つまり，上から i 行目，左から j 列目のマスに書かれている整数を A_{i,j} で表すことにすると， A_{i,j}=(i-1) \times M + j です．

この盤面の部分長方形であって，その内部に書かれた値の総和がちょうど V になるものの個数を数えてください．

より厳密に言えば，整数の 4 つ組 (a,b,c,d) (1 \leq a \leq b \leq N, 1 \leq c \leq d \leq M) であって，\sum_{a \leq i \leq b,\ c \leq j \leq d} A_{i,j}=V を満たすものの個数を数えてください．

制約

  • 1 \leq N, M \leq 5000
  • 1 \leq V \leq 10^{15}
  • 入力される値はすべて整数である

入力

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

N M V

出力

答えを出力せよ．

入力例 1

2 2 3

出力例 1

2

盤面には以下のように整数が書き込まれています．

12
34

条件を満たす部分長方形は，(a,b,c,d)=(1,1,1,2),(2,2,1,1) の 2 つです．

入力例 2

2 2 5

出力例 2

0

入力例 3

13 8 1032

出力例 3

5
B - Best Strategy

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

1 から N までの番号がついた N 問のクイズがあり，あなたはこれらを使ったゲームに参加します．

このゲームでは，あなたはクイズに 1 問ずつ回答していきます． クイズに回答する順番は自由に選ぶことができます． クイズ i に回答すると P_i % の確率で正解します． 正解した場合，あなたは S_i 点を獲得し，（まだ未回答のクイズがあるなら）次のクイズの回答へと移ります． 正解しなかった場合，即座にゲームが終了し，残りのクイズに回答することができなくなります．

あなたは，獲得する得点の合計の期待値を最大化したいです． 目的を達成するための戦略（＝クイズに回答する順番）を求めてください． なお，各クイズに正解するか否かの確率は互いにすべて独立であるものとします．

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq S_i \leq 10^9
  • 0 \leq P_i \leq 100
  • 入力される値はすべて整数である

入力

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

N
S_1 P_1
S_2 P_2
\vdots
S_N P_N

出力

答えを以下の形式で出力せよ．

x_1 x_2 \cdots x_N

ここで x_i は，最初の (i-1) 問を正解した場合に i 番目に回答するクイズの番号を表す． 解が複数存在する場合，どれを出力しても正解とみなされる．

入力例 1

2
1000 10
300 50

出力例 1

2 1

クイズ 1,2 の順で回答した場合，獲得する得点の合計の期待値は 115 になります． クイズ 2,1 の順で回答した場合，獲得する得点の合計の期待値は 200 になります． よって，クイズ 2,1 の順で回答するのが最適な戦略です．

入力例 2

6
1 0
1 20
1 40
1 60
1 80
1 100

出力例 2

6 5 4 3 2 1

入力例 3

9
88994950 78
405248480 35
561113280 28
22802150 2
946582650 25
201425280 52
669650 41
128877450 71
1396050 25

出力例 3

1 5 8 2 3 6 4 7 9
C - Count Dividing XOR

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 L,R が与えられます． 以下の条件を満たす整数の組 (A,B) の個数を数えてください．

  • L \leq A < B \leq R
  • A は A \oplus B で割り切れる．
  • B は A \oplus B で割り切れる．

ただしここで \oplus はビット単位 \mathrm{XOR} 演算を表します．

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{XOR} 、A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq L < R \leq 10^{18}
  • R-L \leq 10^6
  • 入力される値はすべて整数である

入力

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

L R

出力

答えを出力せよ．

入力例 1

3 6

出力例 1

2

(A,B)=(4,5) と (A,B)=(4,6) が条件を満たします．

入力例 2

1 100

出力例 2

124

入力例 3

999000000 1000000000

出力例 3

1726239
D - Dual Rotation

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

(0,1,\cdots,N-1) の順列 P=(P_0,P_1,\cdots,P_{N-1}) が与えられます．

整数 a,b (0 \leq a,b \leq N-1) に対して，順列 f(a,b) を次のように定義します．

  • f(a,b)=(q_0,q_1,\cdots,q_{N-1}) とおいて，q_{(i+a \pmod N)}=(P_i+b \pmod N) (0 \leq i \leq N-1) と定める．

すべての a,b に対し f(a,b) を求めると，N^2 個の順列が得られます． これらの順列を辞書順でソートすることを考えます． ソートしたあと，先頭から K 番目に位置している順列を求めてください．

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。 ここで、|S|, |T| はそれぞれ S, T の長さを表します。

  1. |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
  2. ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
    • (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
    • S_i が T_i より（数として）小さい。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N^2
  • (P_0,P_1,\cdots,P_{N-1}) は (0,1,\cdots,N-1) の順列である．
  • 入力される値はすべて整数である

入力

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

N K
P_0 P_1 \cdots P_{N-1}

出力

答えとなる順列を，要素を空白区切りで出力せよ．

入力例 1

2 2
0 1

出力例 1

0 1

f(a,b) として以下の 4 つが考えられます．

  • f(0,0)=(0,1)
  • f(0,1)=(1,0)
  • f(1,0)=(1,0)
  • f(1,1)=(0,1)

これらの順列を辞書順に並べると，(0,1),(0,1),(1,0),(1,0) となります． よって，この中で 2 番目に位置する (0,1) が答えになります．

入力例 2

4 6
0 2 1 3

出力例 2

1 2 0 3

入力例 3

10 79
6 5 9 8 7 1 3 2 0 4

出力例 3

7 9 8 2 1 0 4 6 5 3
E - East-Northeast

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

0, 1 からなる長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

今，二次元平面上の座標 (0,0) の点に駒があります． あなたはこれから，以下の操作を好きな回数繰り返します．

  • 整数 x,y (1 \leq x,y \leq N) を選び，駒の X, Y 座標をそれぞれ x, y ずつ増やす． ただしここで，以下の 2 つの条件を満たす必要がある．
    • A_x=1 が成立．
    • 操作後の駒の座標を (p,q) とおくとき，q \leq p が成立．

最終的に駒が座標 (N,N) へと至るような操作方法が何通りあるかを 998244353 で割ったあまりを求めてください．

制約

  • 1 \leq N \leq 2 \times 10^5
  • A_i \in \{0,1\}

入力

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

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

2
1 1

出力例 1

2

駒の移動方法として，以下の 2 通りが考えられます．

  • (0,0) \rightarrow (1,1) \rightarrow (2,2)
  • (0,0) \rightarrow (2,2)

入力例 2

1
0

出力例 2

0

入力例 3

4
1 1 0 1

出力例 3

10

入力例 4

25
1 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0

出力例 4

934946952
F - Forbidden Pattern

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1300 点

問題文

A, B からなる長さ N の文字列 S が与えられます．

あなたは，以下の操作を 0 回以上繰り返すことができます．

  • S 中の連続する 2 文字であって，AB でないものを選び，消す． その後，残った左右の（空かもしれない）文字列を連結し，これを新たに S とする．

操作後の S としてあり得る文字列が何通りあるかを 998244353 で割ったあまりを求めてください．

制約

  • 2 \leq N \leq 10^6
  • S は A, B からなる長さ N の文字列である

入力

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

N
S

出力

答えを出力せよ．

入力例 1

3
BBA

出力例 1

3

操作後の S としてありうる文字列は，A, B, BBA の 3 通りです．

入力例 2

5
ABABA

出力例 2

3

操作後の S としてありうる文字列は，A, ABA, ABABA の 3 通りです．

入力例 3

9
BABBAAAAB

出力例 3

14

入力例 4

48
AABABBBAABAAABAAABBBAAABBBAABAABBABAABBAAAAABBBB

出力例 4

3073910
G - Git Gud

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1300 点

問題文

プログラミング初心者のすぬけくんが，以下のようなコードを書きました．

N = read_integer()

parent = array(N, -1) //長さ N の配列 parent を作り，すべての要素を -1 で初期化

find(v):
    if parent[v] == -1:
        return v
    else:
        return find(parent[v])

union(a,b):
    parent[find(b)] = find(a)

for i = 0 to N-2:
    A_i = read_integer()
    B_i = read_integer()
    union(A_i,B_i)

これは，N 頂点の木の情報を受けとり，Union-Find で辺を結ぶだけのプログラムです．

プログラミングマスターのりんごさんは，このプログラムの欠陥に気が付きました． すなわち，Union-Find に一切の高速化が施されていないのです．

今，りんごさんは N 頂点からなる木 T を持っています． T の頂点には 0 から N-1 までの番号が，辺には 0 から N-2 までの番号がついています． 辺 i は頂点 A_i と頂点 B_i を結ぶ辺です．

りんごさんは，すぬけくんのプログラムに T を入力として与えようとしています． ただしその前に，T の辺の番号と，辺の端点の順番を自由に入れ替えることができます．

りんごさんは，すぬけくんのプログラムが非効率的であることを示すために，find 関数が呼ばれる回数を最大化したいです． find 関数が呼ばれる回数の最大値を求めてください．

制約

  • 2 \leq N \leq 2000
  • 0 \leq A_i,B_i \leq N-1
  • A_i \neq B_i
  • 入力されるグラフは木である

入力

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

N
A_0 B_0
A_1 B_1
\vdots
A_{N-2} B_{N-2}

出力

答えを出力せよ．

入力例 1

2
0 1

出力例 1

2

find 関数は必ず 2 回呼ばれます．

入力例 2

3
0 1
0 2

出力例 2

5

辺 0 の端点の順番を入れ替え，以下のような入力を作ると，find 関数が 5 回呼ばれます．

3
1 0
0 2

入力例 3

5
0 1
0 2
0 3
3 4

出力例 3

13

辺の順番と辺の端点の順番を適切に入れ替え，以下のような入力を作ると，find 関数が 13 回呼ばれます．

5
3 0
4 3
1 0
0 2

入力例 4

20
6 16
10 6
16 8
1 5
9 4
5 3
13 16
19 10
12 2
14 10
12 18
0 2
15 16
12 7
11 14
1 10
6 4
17 8
12 1

出力例 4

148