ABC463参加記

問題文 横 $X$ ピクセル、縦 $Y$ ピクセルの画像があります。

横の長さと縦の長さの比が $16$ 対 $9$ であるか、すなわち $X:Y=16:9$ であるかを判定してください。

制約 - $1 \le X \le 1000$

• $1 \le Y \le 1000$
• 入力はすべて整数

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

$X$

$Y$

出力 横の長さと縦の長さの比が $16$ 対 $9$ ならば Yes を、そうでないならば No を出力せよ。

問題文 高橋君は列車の座席を予約しようとしています。

高橋君が予約する候補としている列車は $N$ 本あり、列車 $1, 2, \dots, N$ と番号が付けられています。いずれの列車も座席は $5$ 列からなり、それぞれ A 列、B 列、C 列、D 列、E 列と呼ばれています。

各列車の現在の空席情報が文字列 $S_1, S_2, \dots, S_N$ として与えられます。ここで $S_1, S_2, \dots, S_N$ はすべて長さ $5$ で、列車 $i$ の A 列から E 列までがそれぞれ $S_i$ の $1$ 文字目から $5$ 文字目と対応しており、その文字が o ならば対応する列に空席があることを、x ならば対応する列に空席がないことを意味します。

高橋君は $X$ 列の席を予約したいです。ここで $X$ は A、B、C、D、E のいずれかです。$1$ 本以上の列車において $X$ 列に空席があるか判定してください。

制約 - $N$ は $1$ 以上 $100$ 以下の整数

• $X$ は A、B、C、D、E のいずれか
• $S_i$ は o、x からなる長さ $5$ の文字列

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

$N$ $X$

$S_1$

$S_2$

$\vdots$

$S_N$

出力 $1$ 本以上の列車において $X$ 列に空席があるならば Yes を、そうでないならば No を出力せよ。

問題文 現在、会議室に $N$ 人の高橋くんがいます。 $i$ 番目 $(1 \le i \le N)$ の高橋くんの身長は $H_i$ であり、今から $L_i$ 分後に会議室を去ります。 一度会議室を去った高橋くんはそれ以降会議室に戻ることはありません。

$Q$ 個のクエリが与えられるので、順に答えてください。

$i$ 番目 $(1 \le i \le Q)$ のクエリでは整数 $T_i$ が与えられるので、今から $T_i

• 0.5$分後に会議室にいる高橋くんの身長の最大値を答えてください。 この問題の制約のもとで、今から$T_i + 0.5$分後には会議室に$1$ 人以上の高橋くんがいることが保証されます。

制約 - $1 \le N \le 3 \times 10^5$

• $1 \le H_i \le 10^9 \ (1 \le i \le N)$
• $1 \le L_1 \le L_2 \le \dots \le L_N \le 10^9$
• $1 \le Q \le 3 \times 10^5$
• $0 \le T_i < L_N \ (1 \le i \le Q)$
• 入力はすべて整数

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

$N$

$H_1$ $L_1$

$H_2$ $L_2$

$\vdots$

$H_N$ $L_N$

$Q$

$T_1$ $T_2$ $\dots$ $T_Q$

出力 $Q$ 行にわたって出力せよ。 $i$ 行目 $(1 \le i \le Q)$ には、$i$ 番目のクエリに対する答えを出力せよ。

問題文 数直線上に $N$ 枚の布があります。 $i$ 枚目 $(1 \le i \le N)$ の布は数直線上の区間 $[L_i, R_i]$ を覆っています。 数直線上の点は $2$ 枚以上の布で覆われていることも、どの布にも覆われていないこともあります。

$2$ 枚の布が重なっているとは、数直線上のある点がその $2$ 枚の布どちらにも覆われていることをいいます。

重なっていない $2$ 枚の布について、それらの距離を以下のように定めます。

一方の布に覆われている点 $p$ ともう一方の布に覆われている点 $q$ に対する $|p-q|$ の最小値

どの $2$ 枚も重なっていない $K$ 枚の布に対して、そのスコアを布どうしの距離の最小値と定めます。 $N$ 枚の布からどの $2$ 枚も重なっていないように $K$ 枚を選ぶときのスコアの最大値を求めてください。

ただし、そのように $K$ 枚の布を選ぶことができない場合、-1 を出力してください。

制約 - $2 \le K \le N \le 2 \times 10^5$

• $0 \le L_i < R_i \le 10^9 \ (1 \le i \le N)$
• 入力はすべて整数

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

$N$ $K$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_N$ $R_N$

出力 答えを出力せよ。

入力例 1 6 3

1 12

2 7

5 9

9 13

10 18

15 20

出力例 1 2

$2$ 枚目、$4$ 枚目、$6$ 枚目の布を選ぶと、これらはどの $2$ 枚も重なっていません。 $2$ 枚目の布と $4$ 枚目の布の距離は $2$ 、$2$ 枚目の布と $6$ 枚目の布の距離は $8$ 、$4$ 枚目の布と $6$ 枚目の布の距離は $2$ なので、この選び方のスコアは $2$ です。

スコアが $3$ 以上になるように $3$ 枚の布を選ぶことはできないため、$2$ を出力してください。

問題文 AtCoder 国には $N$ 個の都市と $M$ 本の道路があります。 $i$ 本目の道路 $(1 \le i \le M)$ は都市 $u_i$ と都市 $v_i$ を双方向に繋いでおり、一方からもう一方へ $T_i$ 分かけて移動することができます。

また、それぞれの都市にはワープゲートが設置されており、都市 $i \ (1 \le i \le N)$ から都市 $j \ (1 \le i \le N)$ へワープゲートを使って $X_i + X_j + Y$ 分かけて移動することができます。

これ以外の方法で AtCoder 国の都市の間を移動することはできません。

$k=2,3,\dots,N$ について、次の問題を解いてください。

都市 $1$ から都市 $k$ へ移動するのにかかる時間の最小値を求めよ。

ただし、道路やワープゲートから同じ都市の別の道路やワープゲートへ移動するのにかかる時間は無視できるものとします。

制約 - $2 \le N \le 2 \times 10^5$

• $0 \le M \le 2 \times 10^5$

• $1 \le u_i < v_i \le N \ (1 \le i \le M)$

• $1 \le T_i \le 10^9 \ (1 \le i \le M)$

• $1 \le X_i \le 10^9 \ (1 \le i \le N)$

• $1 \le Y \le 10^9$

• 入力はすべて整数 入力 入力は以下の形式で標準入力から与えられる。

  $N$ $M$ $Y$

  $u_1$ $v_1$ $T_1$

  $u_2$ $v_2$ $T_2$

  $\vdots$

  $u_M$ $v_M$ $T_M$

  $X_1$ $X_2$ $\dots$ $X_N$

出力 $k=2,3,\dots,N$ に対する問題の答えを、この順に空白を区切りとして出力せよ。