いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Regular Contest 076(ARC076)

AtCoder Regular Contest 076 - AtCoder Regular Contest 076 | AtCoder
出てました
そっちかよって感じですが今日のも後で書きます

C.Reconciled?
犬と猿の数が与えられるから、交互に並べる通りを数えてください
犬猿は区別します
犬と猿の数の差が2以上だと並べられない(犬か猿が隣り合ってしまう)のでそれを場合分けで跳ねて、さらに差が0か1かで場合分けをした
それぞれ計算して終わり

D.Built?
これにとても苦戦して5時間かかりました、最近のARCは長いなあ(?)
街の座標がx,yで与えられる、これらの街に道をひいてすべての街を行き来できるようにしたい
この時道のコストがa,bとc,dの街の間でmin(|a−c|,|b−d|) 円かかる
最低で何円必要か

最初に問題を見て最小全域木だと思った
最近Y氏が教えてくれた奴だ、やったぜ
しかし制約を見て無理だと分かった
しかし色々考えた結果最小全域木が蟻本に載ってるってことはそれ以上のアルゴリズムはないってことだ(?????)
まあほかにいい方法が思いつかなかったので図をいっぱい書いて考察を練ってた
x,yそれぞれソートしてみたら引くべき道が絞れてきて、(n-1)*2本でいいことが分かった
これに対して最小全域木を作れば行けると確信し始めて実装を書き始めたらタイムアップになった
TLを眺めてるとどうも正解っぽくて悔しいやらうれしいやら

という事で実装していたら5時間かかってしまった
Submission #1379815 - AtCoder Regular Contest 076 | AtCoder
忘備録だから書いたつもりだけどうまく書けないし多分忘れることもない問題になってしまった