けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

順列を巡回群の直積と見る

AtCoder ABC 180 F - Unbranched (黄色, 600 点)

結構いろんな考え方のできる問題! 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフであって、次の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 自己ループを持たない すべての頂点の次数が 2 以下である 各連結成分のサイズを並べた…

AOJ 2955 Two Colors Sort (HUPC 2019 day2-D)

これ好き!!! 問題へのリンク editorial 問題概要 の順列が与えられる。これらの順列のうち、 個を赤く塗り、 個を青く塗る方法であって、次の条件を満たすようにするものは存在するか、判定せよ。 赤い要素同士を swap することを好きな順序で好きな回数…

AtCoder ABC 175 D - Moving Piece (水色, 400 点)

異様に難しかった!! 問題へのリンク 問題概要 の順列が与えられる。 順列の中の i から P[ i ] へ移動するとき、C[ P[ i ] ] だけスコアが加算される。 出発点を自由に選んで 回以上 回以下の移動を行うとき、得られるスコアの最大値を求めよ。 制約 考え…

第5回 ドワンゴからの挑戦状 予選 2018 E - Cyclic GCDs (赤色, 1000 点)

バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…

AOJ 2378 SolveMe (JAG冬合宿 2010 day3-J)

伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…