ABC462参加記

問題文
英小文字と数字のみからなる文字列 $S$ が与えられます。
$S$ から数字である文字だけを取り出し、元の順序のまま並べた文字列を求めてください。

制約

• $S$ は英小文字と数字のみからなる長さ $1$ 以上 $50$ 以下の文字列

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

出力
答えを出力せよ。

問題文
人 $1$ から人 $N$ の $N$ 人がギフトを送り合いました。
人 $i$ は人 $A_{i,1},A_{i,2},\ldots,A_{i,K_i}$ の $K_i$ 人にギフトを送りました。
$i=1,2,\ldots,N$ に対し、人 $i$ にギフトを送った人を全て求めてください。

制約

• $2 \le N \le 100$
• $1 \le K_i \le N-1$
• $1 \le A_{i,1} \lt A_{i,2} \lt \cdots \lt A_{i,K_i}\le N$
• $A_{i,j} \neq i$
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。
$N$
$K_1$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,K_1}$
$K_2$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,K_2}$
$\vdots$
$K_N$ $A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,K_N}$

出力
$N$ 行出力せよ。
$i$ 行目には、人 $i$ にギフトを送った人の番号を昇順に $B_1,B_2,\ldots,B_{X}$ （ただし $X$ は人 $i$ にギフトを送った人数）としたとき、以下の形式で出力せよ。
$X$ $B_1$ $B_2$ $\ldots$ $B_X$

問題文
$2$ 次元平面上に点 $1$ から点 $N$ までの $N$ 個の点があります。点 $i$ $(1\le i\le N)$ の座標は $(X_i,Y_i)$ です。ここで、$X,Y$ はそれぞれ $(1,2,\ldots,N)$ の順列であることが保証されます。
左下の頂点を $(0,0)$ 、右上の頂点を $(X_i,Y_i)$ とする $x$ 軸に平行な辺と $y$ 軸に平行な辺のみからなる長方形の内部（辺上を含まない）に点 $1$ から点 $N$ までの $N$ 個の点をどれも含まないような $i$ の個数を求めてください。

制約

• $1\le N\le 3\times 10^5$
• $1\le X_i,Y_i\le N$
• $X,Y$ はそれぞれ $(1,2,\ldots,N)$ の順列
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。
$N$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

出力
答えを出力せよ。

問題文
とある館で殺人事件が起きました。犯人の候補は $N$ 人おり、彼らを人 $1$、人 $2$、$\dots$、人 $N$ と呼びます。
人 $i$ は時刻 $S_i$ に館に入り、時刻 $T_i$ に館を出て、ほかの時刻には出入りしませんでした。
犯行について以下のことが分かっています。

• 犯人はちょうど $2$ 人いる。
• 犯行はある整数時刻 $x$ に開始し、$D$ 単位時間かけて行われ、時刻 $x + D$ に完了した。
• 犯人は $2$ 人とも犯行開始から犯行完了まで常に館にいた。（犯行開始と同時に館に入ったり、犯行完了と同時に館を出たりしたかもしれない。）

$N$ 人の犯人候補の中に犯人が $2$ 人ともいると仮定したとき、$2$ 人の犯人と犯行開始時刻の組としてありうるものは何通りあるでしょうか。ここで、$2$ 人の犯人には順番を付けません。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq S_i \leq T_i \leq 10^6$
• $1 \leq D \leq 10^6$
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。
$N$ $D$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_N$ $T_N$

出力
$2$ 人の犯人と犯行開始時刻の組としてありうるものの個数を出力せよ。

問題文
整数 $A,B,X,Y$ が与えられます。
二次元平面上にコマが置かれています。はじめコマは座標 $(0,0)$ にあります。
あなたは以下の操作を $0$ 回以上何回でも行うことができます：

• 今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y),(x,y-1),(x,y+1)$ のいずれかにコマを移動させる。

$k$ 回目 $(k \geq 1)$ に行う操作にかかるコストは $k$ の偶奇によって異なり、それぞれ以下の通りです：

• $k$ が奇数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y)$ に移動させる場合のコストは $A$、座標 $(x,y-1),(x,y+1)$ に移動させる場合のコストは $B$ である。
• $k$ が偶数のとき：今コマがある座標を $(x,y)$ として、座標 $(x-1,y),(x+1,y)$ に移動させる場合のコストは $B$、座標 $(x,y-1),(x,y+1)$ に移動させる場合のコストは $A$ である。

コマを座標 $(X,Y)$ に移動させるために必要なコストの総和の最小値を求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1\le T\le 2\times 10^5$
• $1\le A,B\le 10^9$
• $-10^9\le X,Y\le 10^9$
• 入力される値は全て整数

入力
入力は以下の形式で標準入力から与えられる。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$
$i$ 番目 $(1\le i\le T)$ のテストケース $case_i$ は以下の形式で与えられる。
$A$ $B$ $X$ $Y$

出力
各テストケースに対する答えを順に改行区切りで出力せよ。

問題文
英大文字のみからなる文字列 $S$ が与えられます。
高橋君の目標は、$S$ の文字のうちいくつかを置換することによって、$S$ が ABC を部分文字列として含む個数をちょうど $K$ 個 増やす ことです。
このようなことが可能か判定し、可能な場合は目標を達成するために高橋君が最低何文字置換する必要があるか求めてください。
$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

置換とは
$S$ の文字のうちの $1$ つを置換するとは、$1\leq i\leq \lvert S\rvert$ をみたす整数 $i$ を $1$ つ選び、$S$ の $i$ 文字目を任意の英大文字 $1$ 字 で置き換えることを指します。
ただし、$\lvert S\rvert$ で $S$ の長さを表すものとします。

部分文字列とは
$S$ の部分文字列とは、$S$ の先頭および末尾からそれぞれ $0$ 文字以上削除して得られる文字列のことを指します。
$2$ つの部分文字列は、$S$ から取り出した場所が異なれば、文字列として等しくとも区別して数えられます。

制約

• $1\leq T\leq 10^5$
• $S$ は英大文字のみからなる長さ $3$ 以上 $3\times 10^5$ 以下の文字列
• $1\leq K \leq 10$
• それぞれの入力において、各テストケースの $S$ の長さの総和は $3\times 10^5$ 以下である。
• $T,K$ は整数

入力
入力は以下の形式で標準入力から与えられる。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$
$case_i$ は $i$ 番目のテストケースを表す。
各テストケースは以下の形式で与えられる。
$S$
$K$

出力
$T$ 行出力せよ。
$i$ 行目 $(1\leq i\leq T)$ には、$i$ 個目のテストケースに対する答えを出力せよ。
ここで、各テストケースに対する答えとして、高橋君が目標を達成することが不可能な場合は $-1$ を、そうでない場合は目標を達成するために置換する必要のある文字の個数の最小値を出力せよ。