Zenn
✨

AtCoder Beginner Contest ABC392 解法メモ

に公開
Nim
AtCoder
tech

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC392

ABC392A - Shuffled Equation

解法

Aをソートして、A[0]*A[1]=A[2]か判定すればよい

ABC392B - Who is Missing?

解法

Aをsetで持ち、1..Nでsetにないseqを生成すればよい

ABC392C - Bib

解法

答えの配列Sを用意しておき、iを0..<Nにしなから、S[Q[i]]=Q[P[i]]と置いていけばよい
最後に+1しながら出力したものが答え

メモ

人→ゼッケン、ゼッケン→人、人→見つめる人の連想配列を各々用意しても解ける

ABC392D - Doubles

解法

サイコロの組み合わせをi、jで全探索
その際、iの面の種類各々に対する
(iのその数の面の数\times jのその数の面の数)\div (iの面の数\times jの面の数)
の総和を計算するので、あらかじめ各サイコロの目とその面数の連想配列を用意する
全組み合わせの最大値が答え

メモ

連想配列を用意せず、countを使ったのでTLE

ABC392E - Cables and Servers

解法

Union-Findでsameでなければmerge、sameなら余りケーブルとしてケーブル番号とA端を保管
M本分完了後のgroupsの数-1の繋ぎ変えが必要（それを出力）
接続の組み合わせ作りを効率化するためサーバー番号0を含むgroupsから他のgroupsに接続することとし、ケーブル順に0とAがsameでなければ、そう繋ぎ変え（ケーブル番号、A、0を出力し、Aと0をmergeする）、0とAがsameなら、そこからさらに別のgroupsにつなげるべく、sameでなくなるまで探してから繋ぎ変える
具体的には、まず、j=1としておき、for i in 0..<groups.len-1として、ケーブルc[i]のAと0がsameか確認、もし、sameなら、sameでなくなるまでj+=1していく

メモ

サーバー番号0を含むgroupsから他のgroupsに接続させる、それを余りケーブルを主体にして回す、という形が思い浮かばない
groups.lenを都度呼び出すとTLE

反復学習にはmochiがおすすめ
全問入ったdeckはこちら

Discussion