Unratedだと（時々Ratedでも）、詰まったときに寝てしまうことがあるのは良くないですね。そもそもこのEは詰まらずに解けておくべき問題でした。
コンテストへのリンク
E. Tree Queries
なんか、クエリごとに木を探索してもOKな気がして、計算時間が間に合っていないものを間に合っていると勘違いしてコードを投げてしまった……。コンテスト後で気楽に考えられるはずなのに、こういう間違いをしてしまうのはちょっとまずい。
解法としては、深さと各ノードの親ノードを求めておき、一番深さの大きい点Mと、それ以外の点xについて、LCA(M,P[x])=MとなればOK。
Senさんの解説記事には、オイラーツアーだけでやる方法も書いてあります。
F. Make k Equal
実装はやや面倒くさいですが、こっちの方がEより簡単ですね。「ある数字まで左から最小値を押し上げていったときのコスト」、「ある数字まで右から最大値を下げていったときのコスト」を計算できるので、「最終的にk個にする数字」を全探索すればOK。
……で済まそうと思ったら9WAもしてしまった。
自分が間違えていたのは、たとえば、「2,2,2,5」の2を二個5にしたい、というとき、(5-2)*3で計算してしまったことでした。これは間違いで、全ての2を4にしてから二個5にしなくてはダメ。
これで42caseまで通ってしまった（！）ので、くだらないミスかと思い添え字を変えたりとか迷走してしまいましたが、根本的に間違っていました……。
0 件のコメント:
コメントを投稿