コンテストページ

問題概要

A 問題: Away from College

(問題文を読んでいません　原文を読んでください)

B 問題: Boxes

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$n$ 個の箱があり、それぞれの箱には黒いボールまたは白いボールがそれぞれ $\displaystyle{\frac{1}{2}}$ の確率で入っている。箱は閉じられていて、中のボールを見ることはできない。

以下の操作 1 または操作 2 を繰り返すことにより、すべての箱に入っている玉の色を当てたい。

操作 1: 整数 $i \ (1 \leq i \leq n)$ を選ぶ。コスト $w_i$ を支払い、箱 $i$ を開けて入っているボールの色を知る。
操作 2: コスト $C$ を支払い、まだ開けられていない箱に入っている黒いボールの個数を教えてもらう。

すべての箱に入っている玉の色を当てるのに必要なコストの期待値の最小値を求めよ。

想定解答との絶対誤差または相対誤差が $10 ^ {-6}$ 以下であれば正解として扱われる。

入力は以下の制約を満たす。 - $1 \leq n \leq 10 ^ 5$ - $0 \lt C \leq 10 ^ 9$ - $0 \lt w _ i \leq 10 ^ 9$

C 問題: Cheating and Stealing

実行時間制限: 2 秒 / メモリ制限: 262144 KB

W と L のみからなる長さ $n$ の文字列 $S$ が与えられる。 $i = 1, 2, \cdots, |S|$ に対し、 $f _ i(S)$ を以下の操作で定義する。

文字列 $S$ の接頭辞であって、接頭辞に含まれる W, L の個数をそれぞれ $cnt _ W, cnt _ L$ とおくと、 $\max(cnt _ W, cnt _ L) \geq i$ かつ $|cnt _ W - cnt _ L| \geq 2$ が成立するもののうち最も短いものを取る。
条件を満たす接頭辞が存在しない場合、操作を終了する。得た得点が $f _ i(S)$ の値である。
条件を満たす接頭辞が存在する場合、その接頭辞に含まれる W の個数が L の個数より多いならば 1 点の得点を得る。その後、その接頭辞を削除し、1. に戻る。

$\displaystyle{\sum _ {i=1} ^ {|S|} f _ i(S) \times (|S| + 1) ^ {i-1}}$ を $998244353$ で割った余りを求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 10 ^ 6$

D 問題: Double Strings

実行時間制限: 2 秒 / メモリ制限: 262144 KB

文字列 $A, B$ が与えられる。 $A$ の部分列 $A'$ と $B$ の部分列 $B'$ の組であって、 $A' \lt B'$ を満たすものの個数を $998244353$ で割った余りを求めよ。ただし、同じ部分文字列であっても $A$ や $B$ の異なる位置から取ったものは区別する。

入力は以下の制約を満たす。

$1 \leq |A|, |B| \leq 5000$
$A, B$ は小文字のアルファベットからなる。

E 問題: Eert Esiwtib

実行時間制限: 3 秒 / メモリ制限: 262144 KB

長さ $n$ の数列 $a _ 1, a _ 2, \cdots, a _ n$ と頂点 $1$ を根とする $n$ 頂点の木が与えられる。木の各辺には OR, AND, XOR のうち 1 つの演算子が書かれている。また、木の頂点 $i$ には整数 $a _ i$ が書かれている。

$u, v$ を木の異なる 2 頂点とし、それらの間のパスの頂点を $p _ 0 = u, p _ 1, p _ 2, \cdots, p _ {s-1}, p _ s = v$ とおく。また、頂点 $p _ {i-1}, p _ i$ を結ぶ辺に書かれている演算子を $opt _ i$ とおく。このとき、このパスの重みを $(a _ {p _ 0} opt _ 1 (a _ {p _ 1} opt _ 2 ( \cdots (a _ {p _ {s - 1}} opt _ {s - 1} a _ {p _ s}))))$ と定義する。

$q$ 個のクエリが与えられる。各クエリでは、整数 $d$ と木の頂点 $u$ が与えられる。ただし、 $u$ は葉ではないことが保証される。頂点 $i$ に書かれた整数が $a_ i + i \times d$ に変化したとき、 $u$ が $v$ の先祖であるような頂点 $v$ すべて (ただし頂点 $u$ 自身は除く) について、 $(u,v)$ パスの重みを求め、それらの OR, AND, XOR をそれぞれ求めよ。

入力は以下の制約を満たす。

$2 \leq n \leq 10 ^ 5$
$1 \leq q \leq 10 ^ 5$
$1 \leq a _ i \leq 10 ^ {18} \ (1 \leq i \leq n)$
$0 \leq d \leq 100$

F 問題: Finding Points

実行時間制限: 1 秒 / メモリ制限: 262144 KB

凸多角形 $A _ 1A _ 2 \cdots A _ n$ が与えられる。ただし、点 $A _ 1A _ 2 \cdots A _ n$ は反時計回りに並んでいる。 $A _ i$ の座標は $(x _ i, y _ i)$ である。この多角形の内部の点 $P$ に対する $\angle A _ 1PA _2, \angle A _ 2PA _ 3, \cdots, \angle A _ NPA _ 1$ の最小値としてありうる値の最大値を求めよ。

想定解答との絶対誤差または相対誤差が $10 ^ {-6}$ 以下であれば正解として扱われる。

入力は以下の制約を満たす。

$4 \leq n \leq 100$
$|x _ i|, |y _ i| \leq 10000 \ (1 \leq i \leq n)$

G 問題: Greater Integer, Better LCM

実行時間制限: 2 秒 / メモリ制限: 262144 KB

正の整数 $a, b, c \ (a, b \lt c)$ が与えられる。ただし $c$ は素因数分解した形で与えられ、 $c = \displaystyle{\prod _ {i = 1} ^ n p _ i ^ {q _ i}}$ である。非負整数 $x, y$ であって $\text{lcm}(a+x,b+y)=c$ を満たすものに対する $x+y$ の最小値を求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 18$
$2 \leq p _ i \leq 100, 1 \leq q _ i \leq 18 \ (1 \leq i \leq n)$
$p _ i$ は素数 $(1 \leq i \leq n)$
$1 \leq a, b \leq c \leq 10 ^ {32}$
$\displaystyle{\sum _ {i=1} ^ n q _ i} \leq 18$

H 問題: Holding Two

実行時間制限: 1 秒 / メモリ制限: 262144 KB

正の整数 $n, m$ が与えられる。以下の条件を満たす各要素が 0 または 1 である $n \times m$ の行列を構築せよ。条件を満たす行列が存在しない場合、-1 と出力せよ。

行列の異なる $3$ つの要素 $A _ {i _ 1 j _ 1}, A _ {i _ 2 j _ 2}, A _ {i _ 3 j _ 3}$ であって、 $A _ {i _ 1 j _ 1} = A _ {i _ 2 j _ 2} = A _ {i _ 3 j _ 3}, -1 \leq i _ 1 - i _ 2 = i _ 2 - i _ 3 \leq 1, -1 \leq j _ 1 - j _ 2 = j _ 2 - j _ 3 \leq 1$ を満たすものが存在しない。

入力は以下の制約を満たす。

$1 \leq n, m \leq 1000$

I 問題: Interval Queries

実行時間制限: 4 秒 / メモリ制限: 262144 KB

長さ $n$ の数列 $A _ 1, A _ 2, \cdots, A _ n$ が与えられる。

集合 $S$ に対し、 $f(S)$ を $x, x+1, \cdots, x+len-1$ がすべて $S$ の要素であるような $x$ が存在する最大の $len$ の値とする。

$q$ 個のクエリが与えられる。各クエリでは、整数 $l, r, k$ が与えられるので、 $\displaystyle{\sum _ {i=0} ^ {k-1} f(\lbrace A _ {l-i}, \cdots, A _ l, A _ {l+1}, \cdots, A _ r, \cdots, A _ {r + i} \rbrace) (n+1) ^ i}$ を $998244353$ で割った余りを求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 100000$
$1 \leq q \leq 100000$
$1 \leq A _ i \leq N \ (1 \leq i \leq N)$
$1 \leq l - k + 1 \leq l \leq r \leq r + k - 1 \leq n$
$\displaystyle{\sum _ {i=0} ^ q k _ i} \leq 10 ^ 7$

J 問題: Jewels

実行時間制限: 1 秒 / メモリ制限: 262144 KB

$n$ 個の宝石があり、宝石 $i$ は時刻 $t$ 秒において $(x _ i, y _ i, z _ i + t \times v _ i)$ にある。 $1$ 秒につき $1$ 個の宝石を原点とその宝石の距離の二乗のコストで得ることができる。 $n$ 個の宝石をすべて得るのに必要なコストの最小値を求めよ。

入力は以下の制約を満たす。

$1 \leq n \leq 300$
$0 \leq |x _ i|, |y _ i| \leq 1000$
$0 \leq z _ i, v _ i \leq 1000$

K 問題: King of Range

実行時間制限: 1 秒 / メモリ制限: 262144 KB

長さ $n$ の数列 $a _ 1, a _ 2, \cdots, a _ n$ が与えられる。

$m$ 個のクエリが与えられる。各クエリでは整数 $k$ が与えられるので、 $1 \leq l \leq r \leq n$ なる $(l, r)$ の組であって、 $\max(a _ l, a _ {l+1}, \cdots, a _ r) - \min(a _ l, a _ {l+1}, \cdots, a _ r) \gt k$ を満たすものの個数を求めよ。