ABDE の 4 完、2WA
各問題
A - Christmas Present
比較してください
B - Christmas Trees
超難問。（うそ
左側の人がツリー上に立っている場合と立ってない場合で場合分けしました。
立っている場合は (R - L) / M + 1 でよく、立っていない場合は左側の人の左に立っているツリー上（L' とする）にいるとみなして (R - L') / M でよいです。
算数で苦しみ、剰余の計算で苦しみ、単純な実装ミスで苦しみ、最終的に解けた問題の中では一番時間をかけた挙句 2WA。
C - Socks 2
一枚しかない靴下どおしをペアにすればよく、二枚揃っているものはそのままでよいです。例えば 1 と 4 が一枚しかないときに、(1,2), (2,3), (3,4) とするのも (1,4), (2,2), (3,3) とするのもともに 3 で変わらないです。
で、わざわざ遠いものをペアにしても得しないので、隣り合うものがペアになると考えてよいです。
偶数の時は一通りなのでいいとして、奇数の時はどれか一つ余りますが、両側から距離の累積和をとって余らせるやつの左右の分を合算するとよいです。
B 通した時点で15分弱しか残っておらず、解法に気づいたときには5分を切っていて、結局間に合わず。
D - Reindeer and Sleigh
R はソートして累積和を作り二分探索するだけです。
C より簡単にみえる...。
E - Christmas Color Grid 1
dsu で初期状態の連結成分を管理します。赤のマスを緑に変えたとき、連結成分の個数は「隣り合う連結成分の数 - 1」だけ減ります。
その連結成分の個数はleader をチェックすればすぐわかるので、各赤マスごとに全体の連結成分数がいくつになるかも簡単に求められます。
まとめ
B, C でハマるのを本当に何とかしたい...。
