問題 atcoder.jp 解法 生徒の合流をUnionFind木で管理する。 各生徒の集合状態をmapで管理し、生徒たちが合流したときにmapをマージする。 このとき、mapの小さいほうから大きいほうへマージすることで、マージに必要な計算量を抑えることができる。 「デー…

問題 atcoder.jp 解法 メモ化しながら再帰的に解く。 s="RPS", k=4の例。 トーナメント参加者の出す手は文字列sを周回して決まっていくため、同じパターンが出現する。 テーブルを以下のように定義し、一度計算した値を格納していく。 dp[k][i] = f(dp[k-1][…