AtCoder ABC126 参戦記
AtCoder の ABC 126
結果 5 完で可もなく不可もなく...といった感じでしたが、途中で遭遇したジャッジの不具合 (ジャッジが途中でリスタート or 最後まで終わらない) に引きずられて undated になりました。
全体的な感想としては各問題 100 点ずつ高くない?というものでした。
感想
A 問題, B 問題
瞬殺
C 問題
double で計算したら誤差が範囲外だったのであわてて有理数 (しかも分母で固定のなんちゃって有理数) で実装した。
後で聞いたら double で十分精度が出るらしい。誤差が範囲外だったのは相対誤差だけだったからね...
D 問題
最初のノードを 0 にして、枝をたどって枝の重さが奇数なら 0 ⇔ 1 と変化させればよい。あとは適当なノードから探索。
E 問題
と についてはどちらかがわかれば確定する。つまり、必要な手数は独立したグラフの数。
Union-Find してグラフの数 (= で見つかる値の個数) を数えればよい。
F 問題
を回転すればよい!! と考察したが外れ。
これでは n のペアに対して値が n になってしまう。