Triplets全体感想56分5完で、11位でした。いえば、ratedコンテストでの最高順位です。橙コーダーとしての初戦。逆変色チャンスでもありましたが、上手く乗り切れました。WAはまり、バグはまりせずに無駄なくまとめあげられたのが良い出来でした。22:25頃に実装を終え、「よし!問題Fも解けた!」と思います。サンプルが合いません。あれ?問題Fは、誤読しやすい要素があって...(というか自爆?)。「軌跡上のスイッチのON・OFF」が課題となっていますが、交点をダブルカウントしてしまうとダメです...。2つの経路を分解して扱うことができません。コンテスト開始直後には全ての問題に目を通すのですが、問題Fが行けそうなら行くつもりでした。「行けそうにすら見えなかった」ことが幸いして、一命を取り留めた格好です。間違って解けそうな気分になっていれば、初手で問題Fを仕留めようとして...。Trees頂点1との距離を見まくっているので、bfs木を思い浮かべます。親を割り当てれば完成です。これ、木グラフじゃなくても数えられる出来るはずで、その場合はどこかの過去問で、見かけたような...。違いましたっけ?類題がイメージできたので楽でした。bfs木において、辺が現れる位置は、深さが同じ場所・深さが1異なる場所のどちらかであることから数えられる。自明な必要条件で、これの確認はコーナーケースとなりうるかもしれません。これも、一度過去問でやらかしたことがあったため、回避できたと思っています。回のswapを許せば任意の並べ替えができるという常識があります。したがって、「大体任意の並べ替えが作れるな」というところが考察の起点です。巡回置換」に限られることが分かります。証明に際しては、置換を巡回置換の積に分解したときの、サイクルの個数が良い特徴量を与えます。増減しないことがわかります。