ABC470参加記

はじめに

こんにちは。Akagi_shrineです。

なぜか本番ではうまいこといかないのに、練習で調子がいいときとかありますよね。

今回unratedで遅刻で参加しましたが、4冠できました。やっぱり遅延すると速くなるのは競プロの常識なんですかね。

結果サマリ

ABC470
WCPC参加人数: 6人
各問題の最速解答者(ペナルティ無し):

問題	参加者名	タイム	言語
A	nsubaru	0:48	Java
B	Caffeineholic	2:27	Python
C	nsubaru	14:11	Java
D	Caffeineholic	32:45	Python
E	-	-	-
F	-	-	-
G	-	-	-

今週の出題

ABC470-A

問題ページ: A問題

問題文を表示

問題文

正整数 $N$ が与えられます。

$N$ 行出力してください。

$i$ 行目 ( $1 \le i \le N$ ) には、 $i$ が $3$ の倍数ならば Fizz を、 $3$ の倍数でないならば $i$ を出力してください。

制約

$N$ は $1$ 以上 $100$ 以下の整数

入力

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

$N$

出力

答えを出力せよ。

いわゆる FizzBuzz の簡易版です。 $1$ から $N$ までループを回し、 $i \pmod 3 == 0$ の判定を行うだけです。

ABC470-B

問題ページ: B問題

問題文を表示

問題文

$N$ 個のボールがあります。各ボールは色 $1$ から色 $N$ までの $N$ 色のいずれかで塗られており、 $i$ 個目 ( $1 \le i \le N$ ) のボールの色は $C_i$ です。

あなたは $1$ 回の操作で好きなボール $1$ つを好きな $N$ 色のいずれかに変更することができます。

全てのボールが同じ色になるようにするためには、最小で何回の操作が必要か求めてください。

制約

$1 \le N \le 100$
$1 \le C_i \le N$
入力される値は全て整数

入力

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

$N$
$C_1$ $C_2$ $\ldots$ $C_N$

出力

答えを出力せよ。

一番多く出現している色の個数を数え、全ボール数 $N$ からその一番多く出現している色の個数を引くことで最小操作回数が求まります。配列などで出現回数をカウントすれば簡単に解けます。

ABC470-C

問題ページ: C問題

問題文を表示

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ があります。はじめ、 $A$ の要素は全て $0$ です。

$Q$ 個のクエリが与えられるので、順に処理してください。クエリは $2$ 種類あり、以下のいずれかの形式で与えられます。

1 x : $A_x$ の値を $1$ 増やす。
2 : $i=1,2,\ldots,N$ に対し、 $A_i \ge 1$ ならば $A_i$ の値を $1$ 減らす。

各クエリを処理した直後の $A_1,A_2,\ldots,A_N$ のビット単位 XOR を求めてください。

制約

$1 \le N \le 5\times 10^5$
$1 \le Q \le 5\times 10^5$
$1 \le x \le N$
入力される値は全て整数

入力

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

$N$ $Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

出力

$Q$ 行出力せよ。 $i$ 行目 ( $1 \le i \le Q$ ) には、 $i$ 番目のクエリを処理した直後の $A$ に対する $A_1,A_2,\ldots,N$ のビット単位 XOR を出力せよ。

操作（クエリ1）は XOR の性質を利用すれば簡単です。全体の減算操作（クエリ2）を高速に処理する設計が問われます。要素ごとの値を愚直に更新すると TLE になるため、1以上の値があるかを保持するかを運用して効率的に XOR 和を更新することで計算量マジックで解けます。

ABC470-D

問題ページ: D問題

問題文を表示

問題文

$(1,\ldots,N)$ の順列 $P=(P_1,\ldots,P_N)$ が与えられます。

$Q$ 個のクエリを順に処理してください。クエリは以下の $2$ 種類です。

1 x y : $P_x$ と $P_y$ の値を入れ替える。
2 : 以下の条件を満たす $(1,\ldots,N)$ $(1, \dots, N)$ の順列 $P'=(P_1',\ldots,P_N')$ $P^{'} = (P_{1}^{'}, \dots, P_{N}^{'})$ を作り、 $P_1,\ldots,P_N$ $P_{1}, \dots, P_{N}$ の値をそれぞれ $P_1',\ldots,P_N'$ $P_{1}^{'}, \dots, P_{N}^{'}$ で置き換える。
- $1 \le i \le N$ を満たすどの整数 $i$ についても、 $P_{P_i'}=i$ を満たす。

すべてのクエリを処理したあとの $P_1,\ldots,P_N$ の値を出力してください。

制約

$2 \le N \le 5\times 10^5$
$1 \le Q \le 5\times 10^5$
$(P_1,\ldots,P_N)$ は $(1,\ldots,N)$ の順列
種類 $1$ のクエリにおいて、 $1 \le x < y \le N$
入力される値はすべて整数

入力

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

$N$ $Q$
$P_1$ $P_2$ $\ldots$ $P_N$
$\text{query}_1$
$\vdots$
$\text{query}_Q$

出力

すべてのクエリを処理したあとの $P_1,\ldots,P_N$ の値を、空白区切りで $1$ 行に出力せよ。

クエリ2で行う操作はインデックスソートなどと同じで「順列 $P$ の逆順列をとる」操作です。 $N, Q \le 5\times 10^5$ であるため、クエリ2のたびに配列全体をソートしていると間に合いません。通常状態と反転状態のフラグを保持し、通常状態と反転状態のどちらにいるかを管理しながらスワップ操作の対象を読み替えることで、各クエリを $\mathcal{O}(1)$ で処理できます。

ABC470-E

問題ページ: E問題

問題文を表示

問題文

高橋君は神経衰弱のような $1$ 人ゲームで遊んでいます。

$2N$ 枚のカードがあります。カードの表には数が $1$ つ書かれており、カードの裏には何も書かれていません。

$1 \le i \le N$ を満たす各 $i$ について、 $A_i$ が書かれたカードはちょうど $2$ 枚あります。（ $A_i$ は相異なります）

高橋君はこれらのカードを使って次の手順でゲームを行います。

$2N$ 枚のカードを裏向きの状態でシャッフルし、場に並べる。
ライフを $L$ 、スコアを $0$ とする。
ライフが $0$ $0$ になるか、場のカードがなくなるまで以下を繰り返す。
- 場の裏向きのカードを $1$ 枚選び表にし、書かれている数 $X$ を確認する。
- 場の裏向きのカードを $1$ 枚選び表にし、書かれている数 $Y$ を確認する。
- $X=Y$ のとき、その $2$ 枚を場から取り除き、スコアを $X$ 増やす。
- $X \ne Y$ のとき、 $2$ 枚のカードを再び裏向きに戻し、ライフを $1$ 減らす。

高橋君がゲーム時のスコアを最大化するように最適に行動したときの、ゲーム終了時のスコアの期待値を求めてください。

制約

$1 \le N \le 200$
$1 \le L \le 200$
$1 \le A_1 < A_2 < \ldots < A_N \le 10^5$
入力される値は全て整数

入力

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

$N$ $L$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。真の解との絶対誤差または相対誤差が $10^{-5}$ 以下であれば正解として扱われる。

問題の文からDPの香りと、期待値とあることから神経衰弱の期待値DP問題であると推測できます。期待値DPは解いたことがないので、解説を見てもいまいちわからなかったです。

最後に

今回は比較的得意な部類だと思います。

最近しょうもないミスをしている気がするので、精進していきたいと思います。