AtCoder Regular Contest 076

参加しました

C問題 Reconciled?

区別可能なN匹の犬とM匹の猿がいるので犬と猿が隣り合わないように直線に並べる方法は何通り(%1000000007)あるかという問題。

NとMの差の絶対値が2以上のときは不可能。

NとMの差の絶対値が1のときは多い方から交互に並べる場合のみ。

N=Mのときは、犬から始めても猿から始めても良い。

あとはN!とM!を求めましょう。おわり。

D問題 Built?

N個の街があって、街の座標(a,b)と(c,d)の間に道を作るには、

min(|a-c|,|b-d|)円がかかります。街同士を繋げて全ての街を行き来できるようにするには最低何円必要かという問題。

x座標とy座標でソートしたものを各々作り、隣り合う点同士に枝を貼って最小全域木を求めればよいです。

実装下手くそすぎて泣きかけた。

E問題 Connected?

長方形の内部（境界含む）に数字が1~Nが2つずつ含まれているとき、長方形の外部に出ずかつ曲線が交わらないように同じ数字を結ぶことができるかという問題。

数字つなぎとかそんな感じのパズルに近いが、適当に曲線を書いていいので本質的にはかなり違いそう。

境界上になければ、空間を歪める感じで、同じ数字を重ねあわせることができるので、数字がともに境界上にあるときだけを考えれば良い。

辺に沿うように、座標軸をとって、辺上で現れる順番に数字の列を作りました。

後は交わらないようになっているかを考えれば良い。

盲目的に再帰をやったけど、stackを使えばいいというのはそれはそうなので非常に悲しい。

終了1分半前にギリギリ通して一安心。

順位 159位 パフォーマンス 2138 レート1993(+18)

地道に黄色に戻していこう！（溶ける時は一瞬）