jコンテストページ

問題概要

問題 A: A Hero Named Magnus

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ ( $n$ は奇数) 回試合を行うことを考える。 $1$ 試合目から $x-1$ 試合目までは $50 \%$ の確率で試合に勝ち、 $x$ 試合目以降は必ず試合に勝てるとき、 $n$ 回試合を行ったあと勝った試合が負けた試合より必ず多くなるようにするとき、 $n$ の最小値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq T \leq 10 ^ 5$
$1 \leq x \leq 2 \times 10 ^ 9$

問題 B: A Plus B Problem

実行時間制限: 3 秒 / メモリ制限: 512 Mb

縦 $3$ 行、横 $n$ 列に数字を表示する機械がある。 $1$ 行目と $2$ 行目の数字は自由に変更することができるが、 $3$ 行目の数字は常に $1$ 行目と $2$ 行目に表示された数字をそれぞれ $n$ 桁の整数として見たときのそれらの和の下 $n$ 桁を表示する。

$q$ 個のクエリが与えられる。 $i$ 番目のクエリでは、整数 $r _ i, c _ i, d _ i$ が与えられるので、 $r _ i$ 行目 $c _ i$ 列目の数字を $d _ i$ に変更した後、 $3$ 行目 $c _ i$ 列目に表示されている数字と表示される数字が変化した箇所の個数を出力せよ。

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

$1 \leq n, q \leq 10 ^ 6$
$1 \leq r _ i \leq 2$
$1 \leq c _ i \leq n$
$0 \leq d _ i \leq 9$

問題 C: AC Automaton

実行時間制限: 13 秒 / メモリ制限: 512 Mb

頂点 $1$ を根とする $n$ 頂点の根付き木が与えられる。頂点 $i$ の親は $p _ i$ である。また、各頂点には文字 $s _ i$ が書かれている。ただし、 $s _ i$ は A, C, ? のいずれかである。

$q$ 個のクエリが与えられる。各クエリでは整数 $x$ と文字 $y$ が与えられるので、頂点 $x$ に書かれた文字を $y$ に変更せよ。次に、? が書かれた各頂点に書かれた文字を A または C に変更したとき、頂点 $x$ が頂点 $y$ の先祖で頂点 $x, y$ にそれぞれ A, C が書かれているような頂点の組 $(x, y)$ の個数の最大値を求めよ。ただし、この変更は実際は行わないものとする。

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

$1 \leq n, q \leq 300000$
$1 \leq p _ i \lt i$
$1 \leq x \leq n$
$y$ は A, C, ? のいずれかである。

問題 D: Assumption is All You Need

実行時間制限: 1 秒 / メモリ制限: 512 Mb

長さ $n$ の順列 $A, B$ が与えられる。 $A$ に以下の操作を繰り返して $B$ に変換する手順を示すか、そのような手順が存在しないことを報告せよ。

$1 \leq x \lt y \leq n, A _ x > A _ y$ なる整数 $x, y$ を選び、 $A _ x$ と $A _ y$ を交換する。

ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

すべてのテストケースに対する $n$ の和は $2021$ 以下である。

問題 E: Buy and Delete

実行時間制限: 2 秒 / メモリ制限: 512 Mb

$n$ 頂点の有向グラフ $G$ がある。最初、 $G$ に辺はない。

アリスとボブがゲームを行う。アリスは $c$ ドルを持っていて、 $m$ 種類の辺を買うことができる。 $i$ 番目の辺は $p _ i$ ドルであり、買うと $G$ の頂点 $u _ i$ から頂点 $v _ i$ に有向辺が張られる。その後、ボブは以下の操作を繰り返し $G$ を辺がない状態にする。

$G$ の辺の部分集合 $S$ であって閉路を含まないものを選び、 $S$ に属する辺をすべて削除する。

ボブは操作の回数を最大化しようとし、アリスは操作の回数を最小化しようとするとき、ボブが操作を行う回数を求めよ。

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

$2 \leq n \leq 2000$
$1 \leq m \leq 5000$
$1 \leq c \leq 10 ^ 9$
$1 \leq u _ i, v _ i \leq n$
$u _ i \neq v _ i$
$1 \leq p _ i \leq 100000$

問題 F: Illuminations II

実行時間制限: 2 秒 / メモリ制限: 512 Mb

二つの凸多角形があり、一方はもう一方の内部に完全に含まれている。外側の凸多角形は $n$ 角形、内側の凸多角形は $m$ 角形である。

外側の凸多角形の辺上のランダムな点にライトを設置するとき、内側の凸多角形の辺のうちライトで照らされる部分の長さの期待値を求めよ。

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

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

$3 \leq n, m \leq 2 \times 10 ^ 5$
頂点の座標は整数で絶対値が $10 ^ 9$ 以下である。

問題 G: Occupy The Cities

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ 個の都市が一直線上に順番に並んでいて、そのうち $1$ 個以上は占領されている。長さ $n$ の文字列 $s$ が与えられ、 $s$ の $i$ 文字目が 1 のときは都市 $i$ が最初に占領されていること、`0 のときは都市 $i$ が最初に占領されていないことを示す。

以下の操作を繰り返し、すべての都市を占領された状態にしたい。

占領されているそれぞれの都市が、隣接する占領されていない都市を $1$ つまで選び、その都市を占領された状態にする。

操作の最小回数を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

すべてのテストケースに対する $n$ の和は $10 ^ 6$ 以下である。
$s$ は 0 と 1 のみからなる長さ $n$ の文字列である。
$s$ には 1 が $1$ つ以上含まれる。

問題 H: Popcount Words

実行時間制限: 1 秒 / メモリ制限: 512 Mb

区間 $[l, r ]$ に対し、文字列 $w(l, r)$ を以下のように定義する。

$w(l, r) = s _ l s _ {l + 1} \cdots s _ r$ である。ただし、 $s _ i$ は $i$ を $2$ 進数で表したときの $1$ の個数が偶数ならば 0、奇数ならば 1 である。

$n$ 個の区間 $[l _ 1, r _ 1 ], [l _ 2, r _ 2 ], \cdots, [l _ n, r _ n ]$ が与えられる。 $S = w(l _ 1, r _ 1) + w(l _ 2, r _ 2) + \cdots + w(l _ n, r _ n)$ とする。ただし、 $+$ は文字列の連結を表す。

$q$ 個のクエリが与えられる。各クエリでは文字列 $p$ が与えられるので、 $S$ のうち $p$ が部分文字列として出現する回数を出力せよ。

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

$1 \leq n, q \leq 100000$
$1 \leq l _ i \leq r _ i \leq 10 ^ 9$
$p$ は 0 と 1 のみからなる。
すべてのクエリに対する $p$ の長さの和は $500000$ 以下である。

問題 I: PTSD

実行時間制限: 1 秒 / メモリ制限: 512 Mb

$n$ 人の人 $1,2, \cdots, n$ がいる。 $n$ 文字の 0 または 1 からなる文字列 $s$ が与えられ、 $s$ の $i$ 文字目が 1 のときは人 $i$ が PTSD を持っていること、0 のときは持っていないことを示す。

$n$ 人を何個かのグループに分けるとき、各グループのうち $2$ 番目に番号が大きい人で PTSD を持っている人の番号の総和としてありうる最大値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

すべてのテストケースに対する $n$ の和は $10 ^ 6$ 以下である。
$s$ は 0 と 1 のみからなる長さ $n$ の文字列である。
$s$ には 1 が $1$ つ以上含まれる。

問題 J: Suffix Automaton

実行時間制限: 6 秒 / メモリ制限: 512 Mb

文字列 $S$ のすべての異なる部分文字列を長さの昇順にソートし、同じ長さのものは辞書順に並べた列を $A$ とする。

$Q$ 個のクエリが与えられる。各クエリでは整数 $k$ が与えられるので、 $A$ の $k$ 番目の文字列が $S$ に現れる最も左側の区間の左端と右端の位置を求めよ。ただし、 $k$ が $A$ の長さより大きい場合は、-1 -1 と出力せよ。

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

$1 \leq |S| \leq 10 ^ 6$
$1 \leq Q \leq 10 ^ 6$
$1 \leq k \leq 10 ^ {12}$

問題 K: Tax

実行時間制限: 2 秒 / メモリ制限: 512 Mb

$n$ 個の都市があり、 $m$ 本の道路で結ばれている。道路を用いてどの $2$ つの都市の間も行き来することができる。 $i$ 番目の道路は都市 $u _ i$ と都市 $v _ i$ を結び、会社 $c _ i$ によって管理されている。また、長さ $m$ の整数の列 $m$ が与えられ、会社 $t$ が管理している道路を $k$ 回目に通るときは $k \times w _ t$ ドルを支払う必要がある。 $k = 2, 3, \cdots, n$ のそれぞれに対し、都市 $1$ から都市 $k$ へ行くときに最小で何ドル必要か求めよ。

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

$2 \leq n \leq 50$
$n - 1 \leq m \leq \displaystyle{\frac{n(n-1)}{2}}$
$1 \leq w _ i \leq 1000$
$1 \leq u _ i, v _ i \leq n$
$u _ i \neq v _ i$
$1 \leq c _ i \leq m$
どの $2$ つの都市も $1$ 本以下の道路で結ばれている。
道路を用いてどの $2$ つの都市の間も行き来することができる。

問題 L: Wiring Engineering

実行時間制限: 8 秒 / メモリ制限: 512 Mb

$n$ 個のビルがあり、 $i$ 番目のビルは座標 $(i, 1)$ にある。また、 $n$ 個の通信塔があり、 $i$ 番目の通信塔は座標 $(i, -1)$ にある。

$q$ 個のクエリが与えられる。 $i$ 番目のクエリでは、整数 $a _ i, b _ i, c _ i, d _ i$ が与えられるとき、区間 $[ a _ i, b _ i ]$ のビルと $[ c _ i, d _ i ]$ の通信塔の間に以下の条件を満たすように何本かの電線を張ったとき、最大何ドル得られるか求めよ。