3完。惨敗。
各問題
A - Shampoo
愚直にシミュレートします。一昔前ならB問題でもおかしくないレベルだと思うんですが...。
B - Hit and Blow
Nが1000までなので、全探索できます。恥ずかしながらそれに気づくのに遅れてもたつきました。
C - Collision 2
まず、y座標が同じ点同士しか衝突の可能性はありません。で、各y座標について、「Lの点のx座標が最も大きいもの」＞「Rの点のx座標が最も小さいもの」を満たせば衝突することになります。
D - Moves on Binary Tree
計算過程をうまく持たないと数値が爆発してしまう可能性がありますが、最後までわからず...。
E - Edge Deletion
ワーシャルフロイドする前とした後の行列を比較して、変わった辺は削除可能、みたいにしてやってみたのですが、数割がWA。連結していないといけないことに終了5分前に気づき、dsuを使った実装を気合で書きましたが間に合わず。
まとめ
Dを諦めるのが遅かったかなー、すぐに見切ってたらE間に合ったかもなー、という感じでした。
今年初の3桁パフォとなってしまいました。まあたまにはこういうこともあります。いやでもレート-40は厳しい...。
