ABC464参加記

問題文 ある都にて、東軍と西軍が戦っています。

高橋君は戦っている軍勢の情報を文字列 $S$ として記録しました。

$S$ には文字 E と W のみが含まれており、$S$ に含まれる文字 E の数と東軍の人数、W の数と西軍の人数がそれぞれ一致します。

高橋君が記録した $S$ が与えられるので、東軍の人数が西軍の人数より多いなら East 、西軍の人数が東軍の人数より多いなら West と出力してください。

なお、$S$ の長さは奇数であることが保証されます。そのため、東軍と西軍のどちらか一方がもう一方に比べて真に人数が多い（つまり、両方の軍勢の人数が同じであることはない）ことが証明できます。

制約 - $S$ は長さ $1$ 以上 $99$ 以下の E と W からなる文字列

• $S$ の長さは奇数

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

$S$

出力 答えを出力せよ。

問題文 高さ $H$ ピクセル、幅 $W$ ピクセルの白黒画像があります。 上から $i$ 行目、左から $j$ 列目のピクセルの色は文字 $C_{i,j}$ として与えられ、. は白、# は黒を表します。

この画像の上下左右の端から、すべてのピクセルが白であるような行や列を削除します。 具体的には、次の処理を順に行います。

• 画像の最上行がすべて白である限り、最上行を削除することを繰り返す。
• 画像の最下行がすべて白である限り、最下行を削除することを繰り返す。
• 画像の最左列がすべて白である限り、最左列を削除することを繰り返す。
• 画像の最右列がすべて白である限り、最右列を削除することを繰り返す。

処理後の画像を出力してください。 なお、与えられる画像には黒いピクセルが少なくとも $1$ つ存在します。

制約 - $1 \le H, W \le 50$

• $C_{i,j}$ は . または # である
• 黒いピクセルが少なくとも $1$ つ存在する

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

$H$ $W$

$C_{1,1} C_{1,2} \dots C_{1,W}$

$C_{2,1} C_{2,2} \dots C_{2,W}$

$\vdots$

$C_{H,1} C_{H,2} \dots C_{H,W}$

出力 処理後の画像を、以下の形式で出力せよ。 ここで、$h, w$ は処理後の画像の高さと幅（ピクセル単位）である。 また、$c_{i,j}$ は処理後の画像の上から $i$ 行目、左から $j$ 列目のピクセルの色を表す文字であり、白のときは . 、黒のときは # とする。

$c_{1,1} c_{1,2} \dots c_{1,w}$

$c_{2,1} c_{2,2} \dots c_{2,w}$

$\vdots$

$c_{h,1} c_{h,2} \dots c_{h,w}$

問題文 高橋君は鳥 $1,2,\dots,N$ の $N$ 羽の鳥を $M$ 日間観察しました。

高橋君が観察した鳥には色 $1,2,\dots,N$ の $N$ 色のうちいずれか $1$ 色がついていますが、これらの鳥には観察期間中に色が変化するという興味深い特徴があります。

鳥 $i$ は $D_i-1$ 日目以前の観察では色 $A_i$ であり、$D_i$ 日目以降の観察では色 $B_i$ になりました。 ただし、$D_i=1$ である場合はその鳥の色は $1$ 日目の観察から $B_i$ であり、$A_i=B_i$ である場合はその鳥の色は観察期間中に変化しませんでした。

$j=1,2,\dots,M$ について、$j$ 日目の観察で鳥の色が何種類あったかを求めてください。

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

• $1 \le M \le 3 \times 10^5$
• $1 \le A_i, B_i \le N$
• $1 \le D_i \le M$
• 入力はすべて整数

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

$N$ $M$

$A_1$ $D_1$ $B_1$

$A_2$ $D_2$ $B_2$

$\vdots$

$A_N$ $D_N$ $B_N$

出力 $M$ 行出力せよ。 そのうち $j$ 行目には、$j$ 日目に鳥の色が何種類あったかを出力せよ。

問題文 これから $N$ 日間の天気が文字列 $S$ として与えられます。

$S$ の $i$ 文字目が S であるとき $i$ 日目の天気は晴れ、R であるとき $i$ 日目の天気は雨です。 また、現時点では嬉しさは $0$ です。

あなたは、以下の操作を $0$ 回以上何回でも行えます。

• $1$ 以上 $N$ 以下の整数 $i$ を選ぶ。
• $i$ 日目の天気が晴れであれば雨、雨であれば晴れに変更する。ただし、$i$ 日目の天気を変更した場合、嬉しさが $X_i$ 減少する。

操作を行った後の最終的な天気に対して、以下の条件で嬉しさが増加します。

• $1 \le i \le N-1$ を満たす各整数 $i$ について、変更後の $i$ 日目の天気が雨、かつ $i+1$ 日目の天気が晴れであるとき、嬉しさが $Y_i$ 増加する。

操作を行った結果として、達成可能な嬉しさの最大値を求めてください。

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

制約 - $1 \le T \le 10^4$

• $N$ は $2$ 以上 $2 \times 10^5$ 以下の整数
• $S$ は長さ $N$ の S と R からなる文字列
• $X_i$ は $1$ 以上 $10^9$ 以下の整数
• $Y_i$ は $1$ 以上 $10^9$ 以下の整数
• ひとつの入力における $N$ の総和は $2 \times 10^5$ 以下

入力 入力は以下の形式で標準入力から与えられる。ここで $\text{case}_i$ は $i$ 個目のテストケースを意味する。

$T$

$\text{case}_1$

$\text{case}_2$

$\vdots$

$\text{case}_T$

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

$N$

$S$

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

$Y_1$ $Y_2$ $\dots$ $Y_{N-1}$

出力 $T$ 行出力せよ。 $i$ 行目には $i$ 個目のテストケースの答えを出力せよ。

問題文 $H \times W$ のグリッドがあります。はじめ、すべてのマスに A が書かれています。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ で表します。

これから $Q$ 回の操作を順に行います。 $i$ 回目の操作では、左上のマスを $(1,1)$、 右下のマスを $(R_i, C_i)$ とする長方形に含まれるすべてのマスを、英大文字 $X_i$ で上書きします。

すべての操作を行った後のグリッドを出力してください。

制約 - $1 \le H, W$

• $H \times W \le 10^6$
• $1 \le Q \le 2 \times 10^5$
• $1 \le R_i \le H$
• $1 \le C_i \le W$
• $X_i$ は英大文字
• 入力される数値はすべて整数

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

$H$ $W$ $Q$

$R_1$ $C_1$ $X_1$

$R_2$ $C_2$ $X_2$

$\vdots$

$R_Q$ $C_Q$ $X_Q$

出力 $H$ 行出力せよ。 $i$ 行目には長さ $W$ の文字列であって、$j$ 文字目が操作後のグリッドにおいて $(i,j)$ に書かれている英大文字であるものを出力せよ。