Educational Codeforces Round 49

スポンサーリンク

A. Palindromic Twist

各対ごとに距離 $0$ または $2$

B. Numbers on the Chessboard

2 行ずつで周期がある.丁寧に計算.

C. Minimum Value Rectangle

なるべく縦横の比が $1$ に近いとき.正方形が作れるならばそれが答です.そうでないとき $2$ 回以上現れるものをソートして隣接を試します.

D. Mouse Hunt

functional graph の各サイクルから最もコストが小さいところをひとつ使います.

E. Inverse Coloring

結局,ある 01 列 $A, B$ があってマス $(i,j)$ は $A_i \oplus B_j$ であるという形になります.この $(A,B)$ を数えます.01 列の長さ・最大の成分の大きさについて dp します.

F. Session in BSU

組 $(a,b)$ をグラフの辺と思うと,グラフの辺を向き付けてすべての頂点の出次数を $1$ 以下にする問題になります.

連結成分において頂点より辺が多ければ不可能,同数ならば可能ですべての頂点を使い切ります.それ以外の場合は木で,任意の点の出次数を $0$ 他の点を $1$ にできます.

G. X-mouse in the Campus

$d\mid M$ に対して,$S = \{a\mid 0\leq a<M, \gcd(a,M)=d\}$ とすると,$x$ 倍は $S$ 内で閉じた操作になるので $d$ ごとに解けばよいです.この集合における $x$ の位数を求めると,同値類の大きさが分かり,同値類の個数が分かります.

CodeForces
スポンサーリンク
シェアする
maspyをフォローする
maspyのHP
タイトルとURLをコピーしました