Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392） - 参加記 | 緑コーダーが解くAtCoder

AtCoder コンテストまとめ ABC 競技プログラミング

コンテスト時間: 2025-02-08(土) 21:00 ~ 2025-02-08(土) 22:40 (100分)

A - Shuffled Equation

Difficulty: 11

解答時間: 2:25

長さ3の整数列 $A$ が与えられる。 $A$ の要素を自由に並べ替えた列を $B=(B_1,B_2,B_3)$ とするとき、 $B_1 \times B_2 = B_3$ を満たすことは可能か判定せよ。

のパターンは全部で6通り考えられるが、とを入れ替えてもの値は変わらない。よって、以下の3つのパターンのうちどれか一つでも成り立てば答えはYes。逆にすべて成り立たなければ答えはNo。
- $A_1 \times A_2 = A_3$
- $A_1 \times A_3 = A_2$
- $A_2 \times A_3 = A_1$

B - Who is Missing?

Difficulty: 29

解答時間: 2:57

長さ $M$ の整数列 $A$ が与えられる。 $A$ の各要素は互いに相異なり、 $1$ 以上 $N$ 以下であるという。 $A$ の要素として含まれない $1$ 以上 $N$ 以下の整数を、昇順に全て列挙せよ。

各要素がfalseで初期化された長さ $N$ のbool配列を用意し、 $i = 1, 2, \cdots, M$ について $A_i$ 番目の要素をtrueにする。
その後先頭から走査して、falseであるインデックスを答えの配列に追加していけばよい。

C - Bib

Difficulty: 132

解答時間: 8:12

$1$ から $N$ の番号がついた $N$ 人の人がおり、人 $i$ は数 $Q_i$ が書かれたゼッケンを着けていて、人 $P_i$ を見つめている。「 $i$ が書かれたゼッケンを着けている人」が見つめている人の着けているゼッケンにかかれている数を、 $i=1,2,\cdots,N$ のそれぞれについて求めよ。

$R_i :=$ 数 $i$ のゼッケンを着けている人の番号
上記のような配列を用意すれば、答えは $Q_{P_{R_i}}$ である。
求めるものがややこしいね。

D - Doubles

Difficulty: 579

解答時間 : 19:03 + WA x3

$N$ 個のサイコロがあり、 $i$ 番目のサイコロは $K_i$ 個の面をもち、各面にはそれぞれ $A_{i,1},A_{i,2},\cdots,A_{i,K_i}$ が書かれている。このサイコロを振ると、各面がそれぞれ $\frac{1}{K_i}$ の確率で出る。 $N$ 個のサイコロから2個を選んで振るとき、2つのサイコロの出目が等しくなる確率の最大値を求めよ。

まず、各サイコロの出目とその個数をmapで管理しておく。
2つのサイコロの選び方を二重ループで全探索する中で、
- サイコロ $i$ の出目それぞれに対して、その出目がサイコロ $j$ に含まれるならば、 $(サイコロ i の出目の個数) \times (サイコロ j の出目の個数)$ を計算する。
- この積の総和を $K_i \times K_j$ で割った値がサイコロ $i, j$ の出目が等しくなる確率であるから、これを最大化すればよい。
オーバーフローやら小数演算の精度やらで3ペナ。これはもったいない...

E - Cables and Servers

Difficulty: 1218

からの番号がついた台のサーバーとからの番号がついた本のケーブルがある。ケーブルはサーバーとサーバーを双方向に結んでいる。以下の操作を0回以上行うことで、全てのサーバー同士がケーブルを介して繋がっているようにするとき、操作の最小回数と最小回数となる操作列を求めよ。
- 操作：ケーブルを1つ選び、その片方の端を別のサーバーに繋ぎ変える。

グラフ問題として考える。
連結成分の中でループを構成している辺のいずれかを、別の連結成分に属する頂点と接続させることで、連結成分の個数は減少する。これを繰り返して全体を連結グラフにしたい。
ループを構成する辺は Union-Find を用いて求められたのだが、そこから辺をつなぎかえる処理がうまく実装できなかった。

結果

Performance: 916

Rating: 936 → 934 (-2)

Dの3ペナが痛かった。