問題 atcoder.jp 解法 Union Findで友達グループの木構造を作成。 この友達グループを完全に解体したグループを作れば良い。 これには友達グループから一人ずつ割り振っていけば良い。 ゆえに友達グループの最大人数が、「元の友達グループを解体したグルー…

問題 atcoder.jp 解法 制約が N ≤ 2×105なので、普通にシミュレーションするとO(108)超えるのは目に見えてる。 なので、計算量を減らす工夫をする必要があるんだけど、これは解法みないとわからなかったー。 数列A = { 3, 1, 4 } とする。 答えは 3 x 1 + 3 …

問題 atcoder.jp 2つの文字列 S, T が与えられます。 T が S の部分文字列となるように、S のいくつかの文字を書き換えます。 少なくとも何文字書き換える必要がありますか？ 実装 SよりTの方が長さが短いので、Sの何文字目から比較するかを決めて総当たりを…