ABC476参加記

問題文

英小文字からなる文字列 $S$ が与えられます。

以下のようにして決まる文字列 $T$ を出力してください。

• $S$ の末尾の文字が e である場合、 $T$ は $S$ の末尾に r を付け加えた文字列である。
• $S$ の末尾の文字が e でない場合、 $T$ は $S$ の末尾に er を付け加えた文字列である。

制約

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

入力

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

$S$

出力

答えを出力せよ。

問題文

$S$ は英小文字からなる長さ $N$ の文字列です。

$T$ は英小文字および * からなる長さ $N$ の文字列です。

$S$ が $T$ にマッチするとは、$T$ に含まれる * をそれぞれ好きな英小文字で置き換えることで $T$ を $S$ に一致させられることをいいます。

$S$ が $T$ にマッチするかどうかを判定してください。

制約

• $1 \leq N \leq 100$
• $S$ は英小文字からなる長さ $N$ の文字列
• $T$ は英小文字および * からなる長さ $N$ の文字列

入力

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

$N$
$S$
$T$

出力

$S$ が $T$ にマッチするならば Yes を、マッチしないならば No を $1$ 行で出力せよ。

問題文

$3$ 以上の整数 $N$ と長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。

$k=3,4,\dots,N$ それぞれに対し以下の問題を解いてください：

$A_1,A_2,\dots,A_k$ を降順に並べたとき、前から $3$ 番目にくる値を求めてください。

制約

• $3 \leq N \leq 5 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 入力される値は全て整数

入力

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

$N$
$A_1$ $A_2$ $\dots$ $A_N$

出力

$N-2$ 行出力せよ。

$i$ 行目 $(1 \leq i \leq N-2)$ には $k=i+2$ とした時の答えを出力せよ。

問題文

AtCoder 王国では、$1$ ドル紙幣と $K$ ドル紙幣の $2$ 種類の紙幣が流通しています。

AtCoder 王国にある J 社の全自動食堂では、デザートやドリンクが商品として売られています。

J 社の全自動食堂には、$N$ 個のデザートを売るデザート販売機と、$M$ 個のドリンクを売るドリンク販売機があります。 デザートには $1$ から $N$ までの、ドリンクには $1$ から $M$ までの番号が付けられています。

デザート $i$ の価格は $A_i$ ドル、ドリンク $j$ の価格は $B_j$ ドルです。

支払いに使う紙幣として、デザート販売機は $1$ ドル紙幣と $K$ ドル紙幣の両方を受け入れますが、ドリンク販売機は $K$ ドル紙幣しか受け入れません。 どちらの販売機も、お釣りはすべて $1$ ドル紙幣のみを使って返します。 同じ商品を $2$ 個以上買うことはできません。

高橋君は $1$ ドル紙幣 $X$ 枚と $K$ ドル紙幣 $Y$ 枚を持って J 社の全自動食堂にやってきました。

高橋君が手持ちの紙幣で買える商品の組合せにおいて、購入できる商品数の最大値を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $2 \leq K \leq 10^9$
• $0 \leq X \leq 10^{15}$
• $0 \leq Y \leq 10^9$
• $1 \leq A_i \leq 10^9$ $(1 \leq i \leq N)$
• $1 \leq B_j \leq 10^9$ $(1 \leq j \leq M)$
• 入力される値はすべて整数

入力

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

$N$ $M$ $K$
$X$ $Y$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_M$

出力

答えを出力せよ。

問題文

$(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ と長さ $M$ の整数列 $L=(L_1,L_2,\dots,L_M)$, $R=(R_1,R_2,\dots,R_M)$ が与えられます。

この順列 $P$ に対し、$i=1,2,\dots,M$ の順に以下の操作を行います：

$P_{L_i},P_{L_i+1},\dots,P_{R_i}$ のうち、最小の値をもつ要素と最大の値をもつ要素の位置を入れ替える。

$M$ 回の操作が終わった後の $P$ の各要素を求めてください。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列
• $1 \leq L_i < R_i \leq N$
• 入力される値は全て整数

入力

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

$N$ $M$
$P_1$ $P_2$ $\dots$ $P_N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_M$ $R_M$

出力

$M$ 回の操作が終わった後の $P$ の各要素を先頭から順に空白区切りで出力せよ。