コンテストページ

問題概要

問題 1: Polesov and Work

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

整数 $a, b$ と正の整数 $R$ が与えられる。円 $x ^ 2+y ^ 2 \leq R ^ 2$ 内の格子点 $(x, y)$ に対し、 $ax+by$ の最大値を求めよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq T \leq 1000$
$- 10 ^ 9 \leq a, b \leq 10 ^ 9$
$1 \leq R \leq 10 ^ 9$

問題 2: Orienteering

実行時間制限: 5 秒 / メモリ制限: 256 Mb

座標平面上に $N$ 個のチェックポイントがあり、 $i \ (1 \leq i \leq N)$ 番目のチェックポイントは点 $(x _ i, y _ i)$ にある。それぞれのチェックポイントは、その位置から距離 $R$ 以内の点を訪れたとき、通過したとみなす。

座標平面上の任意の点から開始し、 $N$ 個のチェックポイントを順に通過したい。ただし、途中で他のチェックポイントを通過してもよいが、それらは通過したとみなさない。このとき、移動距離の最小値を求めよ。

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

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

$1 \leq N \leq 100$
$1 \leq R \leq 10 ^ 9$
$- 10 ^ 9 \leq x _i, y _ i \leq 10 ^ 9 \ (1 \leq i \leq N)$

問題 3: Dice

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

それぞれの面に $1, 2, \ldots, f$ と書かれた $f$ 個の面があるサイコロが $n$ 個ある。これらのサイコロを振り、出た目の数の合計を計算し、さらに $m$ を加算した。結果が $S$ となることがあか判定せよ。ただし、 $B$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq B \leq 10 ^ 5$
$1 \leq S \leq 300$
$1 \leq n \leq 10$
$2 \leq f \leq 20$
$0 \leq m \leq 10$

問題 4: Numeral Systems

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

先頭が $0$ でない数字のみからなる $K$ 文字の文字列であって、 $10$ 進数として見たときの値を $X$ 、 $16$ 進数として見たときの値を $Y$ としたとき、 $X \gt D$ であり $Y$ が $X-D$ で割り切れるようなものを、昇順にすべて列挙せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq T \leq 100$
$2 \leq K \leq 15$
$0 \leq D \leq 10 ^ 6$

問題 5: Hockey

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

ゴールキーパーを除き各チーム $5$ 人で $60$ 分間ホッケーの試合をする。

試合を行っているそれぞれの選手は、ペナルティを受けることがある。ペナルティにはマイナーペナルティとメジャーペナルティの $2$ 種類があり、ペナルティを受けた選手はそれぞれ $2, 5$ 分間試合から外れる。また、一方のチームが相手のチームより試合を行っている人数が少なく、相手のチームがゴールをした場合、そのチームにマイナーペナルティにより試合から外れている選手がいれば、それらのうち最も早くにペナルティを受けた選手 $1$ 人が試合に戻る。

$60$ 分間の間に発生したゴールとペナルティの情報が時間の順に $0.1$ 秒の位まで $N$ 個与えられる。ただし、ゴールが発生した時刻の $0.1$ 秒の位は必ず $0$ 以外であり、ペナルティが発生した時刻の $0.1$ 秒の位は必ず $0$ であることが保証される。

試合中のある時点について、二つのチームで試合を行っている選手の人数がそれぞれ $a$ 人、 $b$ 人であるとき、試合の形式が $a$ 対 $b$ であるという。 $60$ 分間でそれぞれの試合形式が発生していた期間の長さを、一度以上発生した試合形式それぞれについて出力せよ。出力の順番は問わない。ただし、少なくとも一方のチームで試合を行っている選手の人数が $5$ 人未満だった期間が必ず存在することが保証される。

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

$0 \leq N \leq 1000$

問題 6: Days of The Week

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

$M$ 個の宇宙があり、それぞれの宇宙には $1$ つの曜日 (月曜日、火曜日、水曜日、木曜日、金曜日、土曜日、日曜日のうちの $1$ つ) が定められている。それぞれの宇宙の現在の曜日が与えられる。

$N$ 個のスイッチがある。それぞれのスイッチにはある宇宙の集合が対応しており、そのスイッチを押すとそれらの宇宙の曜日がそれぞれ $1$ 日分進む。スイッチは任意の順番で何度でも押すことができる。各宇宙の曜日の組み合わせ $7 ^ M$ 個のうち、スイッチを何度か押すことで作ることのできないものが存在するか判定せよ。存在しない場合は NO と出力し、存在する場合は YES と出力した後そのような組み合わせを $1$ つ出力せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq T \leq 500$
$1 \leq N \leq 500$
$1 \leq M \leq 500$

問題 7: Balls

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

青玉と赤玉をそれぞれ何個か用意し、アリスとボブがゲームを行う。

アリスから始めて、 $2$ 人が交互に玉を $1$ つ取る。ただし、アリスは残っている玉すべてを等確率で取り、ボブは必ず赤玉 $1$ つを取る。また、どちらの手番であるかに関わらず、残っている青玉が $0$ 個になったらアリスが勝ち、残っている青玉の個数が赤玉の個数より多くなったらボブが勝つ。

ゲームを $G$ 回行う。それぞれのゲームでは、青玉と赤玉の合計個数 $C$ が指定されるので、アリスが勝つ確率と $0.5$ の差の絶対値がなるべく小さくなるように青玉と赤玉を用意したい。このとき、用意すべき青玉の個数を出力せよ。

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

$1 \leq G \leq 10 ^ 5$
$2 \leq C \leq 2 \times 10 ^ 5$

問題 8: Romualdych and Remainders

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

整数 $a, b, r$ が与えられる。 $a \leq x \leq b, x \bmod y = r$ を満たす整数の組 $(x, y)$ が存在するか判定せよ。存在しない場合は -1 -1 と出力し、存在する場合はそのような組み合わせのうち $x$ が最も小さいものを $1$ つ出力せよ。ただし、 $T$ 個のテストケースが与えられるので、すべて答えよ。

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

$1 \leq T \leq 200000$
$0 \leq a \leq b \leq 10 ^ {18}$
$0 \leq r \leq 10 ^ {18}$

問題 9: Polynomials

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

黒板の左側に $N$ 個の多項式が、右側に $M$ 個の多項式が書かれている。各多項式の次数 $K$ と係数 $a _ 0, a _ 1, \ldots, a _ K$ が与えられる。

黒板の右側に書かれているそれぞれの多項式について、黒板の左側に書かれている多項式を $1$ つ選び、以下の $2$ 種類の操作を繰り返し適用してその多項式と一致するようにするときの、操作回数の最小値を求めよ。

選んだ多項式をそれを微分したものに置き換える。
選んだ多項式をそれを積分に任意の実数を積分定数として加えたものに置き換える。

ただし、操作は黒板の右側に書かれているそれぞれの多項式について独立して考えるものとする。

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

$1 \leq N, M \leq 10 ^ 5$
$-10 ^ 9 \leq a _ i \leq 10 ^ 9$
黒板の左側に書かれている多項式の次数の合計は $10 ^ 5$ 以下である。
黒板の右側に書かれている多項式の次数の合計は $10 ^ 5$ 以下である。

問題 10: Find The Vault

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

$R \times C$ の #, ., _ からなるグリッド ( $X$ とする) と $A \times B$ の #, ., _ からなるグリッド ( $Y$ とする) が与えられる。 $X$ の $A \times B$ の部分長方形であって、その各マスが以下の条件を満たすものを全て列挙し、それぞれの左上のマスの位置を出力せよ。