コンテストページ

問題概要

A 問題: Automatic Sprayer 2

実行時間制限: 2 秒 / メモリ制限: 1 GB

$n \times n$ の各成分が非負整数の行列 $A$ がある。 $A$ から、 $n \times n$ の行列 $E$ を以下のように作った。

$E _ {ij} = \displaystyle{\sum _ {x=1}^n \sum_{y=1}^n (|x-i|+|y-j|)A _ {xy}} \ (1 \leq i \leq n, 1 \leq j \leq n)$

$E$ が与えられるので、 $A$ としてありうるものを $1$ つ出力せよ。

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

$2 \leq n \leq 1000$
$0 \leq E _ {ij} \leq 10^{16} \ (1 \leq i \leq n, 1 \leq j \leq n)$
条件を満たす行列 $A$ で各成分の和が $10^{12}$ 以下であるものが存在する。

B 問題: Cilantro

実行時間制限: 0.5 秒 / メモリ制限: 1 GB

Y と N のみからなる長さ $n$ の文字列 $S, T$ が与えられる。

スタック $s$ を用意し、 $i=1,2,\cdots,n$ の各文字について以下の操作を順に行う。

$S$ の先頭の文字を削除しそれを $s$ に push する。
$s$ を pop する。ただしこのとき取り出す文字は $T _ i$ に一致しなければならない。

操作 $1$ で取り出した文字が $S _ i$ に対応することがありうるような整数 $i$ をすべて列挙し、それらの和を答えよ。ただし、操作を行うことができない場合は $0$ と出力せよ。

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

$1 \leq n \leq 5000000$
$S, T$ の長さは $n$ で Y と N のみからなる。

C 問題: Equivalent Pipelines

実行時間制限: 3 秒 / メモリ制限: 1 GB

$n$ 頂点の辺に重みが付いた木 $T _ 1, T _ 2, \cdots, T _ d$ が与えられる。

木 $T$ の異なる頂点 $i, j$ について、 $v _ T(i,j)$ を、頂点 $i, j$ を結ぶパス内の辺の重みの最小値とする。また、 $2$ つの木 $T _ 1, T _ 2$ が $v _ {T _ 1}(i,j) = v _ {T _ 2}(i,j) \ (1 \leq i \gt j \leq n)$ を満たすとき、木 $T _ 1, T _ 2$ は同等であるという。

各 $i \ (1 \leq i \leq d)$ について、木 $T _ i$ が木 $T _ j$ と同等であるような最小の $j$ を出力せよ。

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

$d \geq 1$
$n \geq 2$
$dn \leq 500000$
辺の重みは $1$ 以上 $10 ^ 9$ 以下

D 問題: Flowerbed Redecoration

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

$n$ 行 $m$ 列のグリッドがあり、各マスには大文字のアルファベットが書かれている。

$i = 1, 1 + y, 1 + 2y, \cdots, n - d + 1, j = 1, 1+x, 1+2x, \cdots, m-d+1$ について、以下の操作を行う。

マス $(i,j)$ を左上とする正方形の各マスの文字を、正方形を時計回りに $90$ 度回転させた位置に移動させる。

操作を行った後のグリッドの各マスの文字を出力せよ。

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

$1 \leq n \times m \leq 10 ^ 6$
$1 \leq y \leq n$
$1 \leq x \leq m$
$1 \leq d \leq \min(n, m)$
$n \equiv d \ \pmod y$
$m \equiv d \ \pmod x$

E 問題: Goose Coins

実行時間制限: 3 秒 / メモリ制限: 1 GB

$n$ 種類のコインがあり、 $i \ (1 \leq i \leq n)$ 番目のコインの価値は $c _ i$ 円、重さは $w _ i$ である。 $i \ (1 \leq i \leq n - 1)$ に対し、 $c _ {i + 1}$ は $c _ i$ の倍数である。各コインは無限に存在する。

ちょうど $k$ 枚のコインを使ってちょうど $p$ 円を払うとき、コインの重さの合計の最小値と最大値を出力せよ。ただし、ちょうど $p$ 円を払うことができないとき、 $-1$ と出力せよ。

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

$1 \leq n \leq 60$
$1 \leq n \leq 10 ^ 3$
$1 \leq p \leq 10 ^ {18}$
$1 \leq c _ i \leq 10 ^ {18}, 1 \leq w _ i \leq 10 ^ {15} \ (1 \leq i \leq n)$
$i \ (1 \leq i \leq n - 1)$ に対し、 $c _ {i + 1}$ は $i$ の倍数である。

F 問題: Hedgehog Graph

実行時間制限: 5 秒 / メモリ制限: 1 GB

$10 ^ 6$ の頂点の有向グラフ $G$ がある。 $G$ の各頂点の出次数は $1$ であり、 $G$ は閉路を $1$ つだけ持ちその頂点数は $3$ 以上である。また、 $G$ の各辺 $u \rightarrow v$ に対し、 $v$ はこの閉路に含まれる。

以下のクエリを $900$ 回まで投げることができる。

$G$ の頂点 $v$ と $1$ 以上 $5 \times 10 ^ {18}$ 以下の整数 x を出力する。頂点 $v$ から辺に沿って $x$ 回移動した後の頂点が与えられる。

$G$ の閉路の頂点数を求めよ。ただし、 $n \ (1 \leq n \leq 10)$ 個のテストケースが与えられるので、すべて答えよ。

G 問題: Lamb's Respite

実行時間制限: 3 秒 / メモリ制限: 1 GB

体力が整数 $h$ で表されるキャラクターがいる。キャラクターは正の整数で表される最大体力 $H$ を持つ。体力が変化し $H$ より大きくなった場合体力は $H$ となり、 $0$ より小さくなった場合は $0$ となってキャラクターは死亡する。

体力が変化する行動を $n$ 回行う。 $i \ (1 \leq i \leq n)$ 回目の行動ではキャラクターの体力が $a _ i$ だけ変化する。

キャラクターは魔法を使うことができる。魔法を使うと、魔法が持続している間、体力が $\lceil \frac{H}{10} \rceil$ 以下であるか、体力の変化により体力が $\lceil \frac{H}{10} \rceil$ 以下になる (死亡する場合を含む) 場合、体力が $\lceil \frac{H}{10} \rceil$ となり、魔法が切れるまで体力が変化しなくなる。

以下の $2$ 種類のクエリを $q$ 個処理せよ。

クエリ $1$ : 整数 $l, r, x$ が与えられる。キャラクターの開始時の体力と最大体力が $x$ であり、 $l$ 回目の行動の前から $r$ 回目の行動の後まで魔法を使ったとき、 $n$ 回目の行動の後のキャラクターの体力を出力する。ただし、キャラクターが途中で死亡する場合、 $0$ を出力する。
クエリ $2$ : 整数 $i, x$ が与えられる。 $a _ i$ を $x$ に更新する。

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

$1 \leq n, q \leq 300000$
$|a _ i| \leq 10 ^ 9 \ (1 \leq i \leq n)$
クエリ $1$ について、 $1 \leq l \leq r \leq n, 1 \leq x \leq 10 ^ 9$
クエリ $2$ について、 $1 \leq i \leq n, -10 ^ 9 \leq x \leq 10 ^ 9$
クエリ $1$ は $1$ つ以上存在する。

H 問題: Or Machine

実行時間制限: 4 秒 / メモリ制限: 1 GB

$n$ 個の整数 $x _ 1, x _ 2, \cdots, x _ n$ が与えられる。

$l$ 種類の操作がある。 $i \ (1 \leq i \leq n)$ 番目の操作は以下のような操作である。

整数 $a, b$ が与えられる。 $x _ a$ を $x _ a$ と $x _ b$ のビットごとの論理和に置き換える。

操作を $1, 2, \cdots, n$ の順に行い、操作 $n$ を行った後再び操作 $1$ に戻り繰り返す。合計で $t$ 回の操作を行ったとき、 $x _ 1, x _ 2, \cdots, x _ n$ の値を出力せよ。

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

$1 \leq n, l \leq 2^{18}$
$1 \leq t \leq 10^{18}$
$1 \leq a, b \leq n$
$0 \leq x _ i \lt 2 ^ 8$

I 問題: Organizing Colored Sheets

実行時間制限: 3 秒 / メモリ制限: 1 GB

$n \times m$ のグリッドがあり、各マスは色で塗られているか塗られていないかのどちらかである。

$1 \leq w \leq m, 1 \leq h \leq n$ を満たす整数 $w, h$ を選び、 $w \times h$ の色紙のみを以下の条件を満たすようにグリッド上に何枚か配置したい。

色紙がグリッドの外部にはみ出ることはない。
色紙を回転してはならない。
各マスが $2$ 枚以上の色紙で覆われてもよい。
色で塗られていない各マスは $1$ 枚以上の色紙で覆われている。
色で塗られている各マスは色紙で覆われていない。

条件を満たすようにグリッド上に色紙を配置できるような整数 $w, h$ の組の個数を求めよ。

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

$1 \leq n, m \leq 3000$
色で塗られていないマスが $1$ つ以上存在する。

J 問題: Periodic Ruler

実行時間制限: 2 秒 / メモリ制限: 1 GB

無限に長い数直線の整数の位置にそれぞれ印が付いている。色は $1$ 以上 $100$ 以下の整数で表され、 $i$ の位置の印の色は $c _ i$ である。

付けられた印の色は周期 $t$ を持っている。ただし、周期とは、すべでの整数 $i$ に対し $c _ i = c _ {i + t}$ であるような最小の正の整数 $t$ である。

印の色について $n$ 個の情報が与えられる。 $i \ (1 \leq i \leq n)$ 番目の情報は整数 $x _ i$ と色 $a _ i$ からなり、 $x _ i$ の位置の印の色が $a _ i$ であることを示す。

周期 $t$ としてありえない整数を列挙し、その個数とそれらの和を出力せよ。

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

$1 \leq n \leq 50$
$|x _ i| \leq 10 ^ 9 \ (1 \leq i \leq n)$
$1 \leq a _ i \leq 100 \ (1 \leq i \leq n)$
$1 \leq i, j \leq n, i \neq j$ ならば $x _ i \neq x _ j$ である。

K 問題: Three Competitions

実行時間制限: 5 秒 / メモリ制限: 1 GB

$n$ 人の人が $3$ 回の大会に参加した。それぞれの大会で、 $n$ 人の人はそれぞれ異なる順位を得た。

$3$ 回中 $2$ 回以上の大会で人 $a$ の順位が人 $b$ の順位より小さかったとき、人 $a$ が人 $b$ に勝ったという。また、人の列 $p _ 1, p _ 2, \cdots, p _ k \ (k \geq 2)$ であって、 $1 \leq i \leq k - 1$ に対して人 $p _ i$ が人 $p _ {i + 1}$ に勝ち、また $p _ 1=a, p _ k=b$ であるとき、人 $a$ は人 $b$ に間接的に勝ったという。

$q$ 個のクエリが与えられる。各クエリでは、異なる人 $a, b$ が与えられるので、人 $a$ が人 $b$ に間接的に勝ったかどうか答えよ。

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

$2 \leq n \leq 10 ^ 5$
$1 \leq q \leq 2 \times 10 ^ 5$
$1 \leq a, b \leq n, a \neq b$

L 問題: Utilitarianism 2

実行時間制限: 7 秒 / メモリ制限: 1 GB

$n$ 人のワクチン生産者、 $m$ 個の病院と $k$ 人の人がいる。人 $i$ は生産者 $a _ i$ から病院 $b _ i$ へ $c _ i$ 個のワクチンを届けることができる。異なる人が同じ生産者と病院の組み合わせを持つことはない。また、それぞれのワクチン生産者と病院は $1$ 人の人しか利用してはならない。

それぞれの人に対し、その人がいない場合、 $m$ 個の病院に届くワクチンの総数が何個減少するか求めよ。

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

$1 \leq n, m \leq 2000$
$1 \leq k \leq \min(8000, n \times n)$
$1 \leq a _ i \leq n \ (1 \leq i \leq k)$
$1 \leq b _ i \leq m \ (1 \leq i \leq k)$
$1 \leq c _ i \leq 10^{12} \ (1 \leq i \leq k)$
$1 \leq i, j \leq n, i \neq j$ ならば $(a _ i, b _ i) \neq (a _ j, b _ j)$ である。

M 問題: Yet Another Range Query Problem

実行時間制限: 3 秒 / メモリ制限: 1 GB

$1$ 以上 $n$ 以下の整数からなる長さ $n$ の数列 $A$ が与えられる。

$n \times n$ の行列 $B$ がある。 $1 \leq i \leq j \leq n$ のとき、 $B _ {ij} = \min(A _ i, A _ {i + 1}, \cdots, A _ j) \times \max(A _ i, A _ {i + 1}, \cdots, A _ j)$ である。そうでないとき、 $B _ {ij} = 0$ である。