ABC472参加記

問題文

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

$S$ のうち A 以外の文字をすべて . に置き換えた文字列を出力してください。

制約

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

入力

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

$S$

出力

答えを出力せよ。

問題文

棒が $1$ 本あります。この棒には切れ込みが $N-1$ 箇所入っており、切れ込みによって $N$ 個の部分に分かれています。 それぞれの部分の長さは端から順に $L_1, L_2, \dots, L_N$ です。 切れ込みを $1$ 箇所選び、そこで棒を折って $2$ 本の棒にするとき、折ってできる $2$ 本の棒の長さの差の絶対値の最小値を求めてください。 ただし切れ込みの幅は無視でき、折ってできる $2$ 本の棒の長さはそれぞれの棒に含まれる部分の長さの総和になります。

制約

• $2 \leq N \leq 100$
• $1 \leq L_i \leq 10^5$
• 入力はすべて整数

入力

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

$N$
$L_1 \ \ldots \ L_N$

出力

答えを出力せよ。

問題文

高橋君は $N$ 日間の帰省で実家に滞在しています。 実家では毎日おやつが用意されており、$i$ 日目のおやつのカロリーは $A_i$ です。 高橋君は体調管理のために、直近 $M$ 日間で食べたおやつのカロリーの合計が $K$ を超えないならばおやつを食べることを繰り返します。 具体的には $i=1,2,\dots,N$ の順に、以下のルールに従って $i$ 日目のおやつを食べるかどうかを決定します。

• $i$ 日目のおやつを食べたと仮定したときに $\max(i-M+1, 1)$ 日目から $i$ 日目までの間に食べたおやつのカロリーの合計が $K$ 以下ならば、$i$ 日目のおやつを実際に食べる。そうでないならば、$i$ 日目のおやつを食べない。

$i=1,2,\dots,N$ それぞれについて、高橋君が $i$ 日目のおやつを食べるかどうかを判定してください。

制約

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^{15}$
• $1 \leq A_i \leq 10^9$
• 入力はすべて整数

入力

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

$N \ M \ K$
$A_1 \ A_2 \ \dots \ A_N$

出力

$N$ 行出力せよ。 $i$ 行目には高橋君が $i$ 日目のおやつを食べる場合 Yes と、食べない場合 No と出力せよ。

問題文

$H$ 行 $W$ 列のグリッドがあります。各マスは、空マスまたは爆弾マスのどちらかです。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。グリッドの情報は $H$ 個の長さ $W$ の文字列 $S_1, S_2, \dots, S_H$ によって与えられ、$S_i$ の $j$ 文字目が . のとき $(i,j)$ は空マス、$S_i$ の $j$ 文字目が # のとき $(i,j)$ は爆弾マスです。 また、空マス $(i,j)$ について $i$ 行目にも $j$ 列目にも爆弾マスが存在しないとき、そのマスを 安全な空マス と呼びます。

$1$ 回の移動で今いるマスから、上下左右に隣り合う空マスに移動することができます（爆弾マスには移動できません）。以下の条件を満たす空マス $(i,j)$ の数を求めてください。

• $(i,j)$ から $K$ 回以下の移動で 安全な空マス へ到達できる。

制約

• $1 \leq H, W \leq 5 \times 10^5$
• $H \times W \leq 5 \times 10^5$
• $0 \leq K \leq H \times W - 1$
• $S_i$ は . と # からなる長さ $W$ の文字列
• $H, W, K$ は整数

入力

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

$H \ W \ K$
$S_1$
$S_2$
$\vdots$
$S_H$

出力

条件を満たす空マスの個数を出力せよ。

問題文

頂点に $1$ から $N$ の番号がついた $N$ 頂点 $M$ 辺の単純連結無向グラフが与えられます。 $i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。 奇数個の頂点からなる閉路が存在するか判定し、存在するならば $1$ つ求めてください。 厳密には、次の条件を全て満たす整数列 $(v_1, v_2, \dots, v_K)$ が存在するか判定し、存在するなら $1$ つ求めてください。

• $K$ は $3$ 以上の奇数である
• $v_1, v_2, \dots, v_K$ はすべて異なる
• $1 \leq i \leq K$ を満たす全ての整数 $i$ について、頂点 $v_i$ と頂点 $v_{i+1}$ の間に辺がある。ただし $v_{K+1}=v_1$ とする

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N, M \leq 2 \times 10^5$
• 全てのテストケースにおける $N$ の総和は $2 \times 10^5$ 以下
• 全てのテストケースにおける $M$ の総和は $2 \times 10^5$ 以下
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• 与えられるグラフは単純連結無向グラフである
• 入力される値はすべて整数である

入力

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

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

各テストケースは以下の形式で与えられる。

$N \ M$
$a_1 \ b_1$
$a_2 \ b_2$
$\vdots$
$a_M \ b_M$

出力

各テストケースについて、条件を満たす数列が存在しない場合は -1 を出力せよ。存在する場合は以下の形式で $1$ つ出力せよ。

$K$
$v_1 \ v_2 \ \dots \ v_K$

条件を満たす数列が複数存在する場合、どれを出力しても正解となる。