Cまで三完。
No.3436 [Cherry 8th Tune B] この夏に何が起こるかな?
一応自力AC。
二分探索し、P番目の価格の値が求まれば、復元は難しくなさそう。が、コンテスト中は二分探索の判定方法で詰まり解けなかった。
ソートして二分探索して……では、同じ色の場合の処理が難しい。
こういうときは、片側だけ色で分類すると良い。半分全列挙のときと同じ感じでやれる。
各トップスに対して、
・全体で何個が価格X以下か？
・同じ色のものについて、何個が割引せずに価格X以下で、割引した後価格X以下か？
はどちらも二分探索で求められるので、判定できる。
復元は簡単だと思ったが、復元でも詰まった。
同じ色のものが答えになるときは簡単。
そうでないときは、価格Xになるものの個数がbisect(A,X)-bisect(A,X-1)で求まることを利用した。
全体で、価格Xになる個数と、同じ色で価格Xになる個数を比較し、全体の方が多くなっていればOK。
No.3437 [Cherry 8th Tune C] Silhouette
自力AC。
三点がどこに映るかを計算し、三角形の面積を求めれば良い。
ただ、最初から割り算をmod 998244353で行うと正負が分からなくなる。なので、分数で計算し、最後にmod 998244353の形に直した。PythonのFractionをそのまま使ったらTLEだったが、入出力高速化してAC。
模範解答は、三角形の向きを行列式で求める方法らしい（よく分かっていない）。
No.3438 [Cherry 8th Tune D] 競プロは向いてない
自力AC。
実験したら、凸包内部にあるときはNoそう。具体的な（A,B）を求める方法は分からなかったが、凸包の前後の頂点だけ見て乱択したらACした。
しかし、凸包の前後の頂点だけ見れば良いという予想が正しいのなら、不等式を解くことで具体的な（A,B）を得ることはできそうですね……。後から気付きました。
乱択は嘘っぽいけど、どういうときダメなのかはよく分かっていません。
0 件のコメント:
コメントを投稿