順位的にはひどいのですが、
Eが多く解かれているのには気付いていたけどDの解法は分かっていたので実装したかった、かつ、Dは若干Pythonに不利な問題だった、という事情があるので、まあ。
コンテストへのリンク
D - Pairs
・二分探索を使って、答えの数より大きい数がK個以上あるかを調べる
という方針はOK。
あとは、Aをソートしてあれば、N*Nのマス（の半分）のうちで、Kより大きいものが何個か？ を各行について二分探索で求めればOK。（ただし、負の数に注意）
……なのですが、Python/PyPyだと実行時間的にこれを通すのは厳しい。（numpyを上手く使えば通るのかな）
よく考えると、これは尺取り法を使って実装することもでき、これならPython/PyPyでも通せます。
いやでも、二分探索→二分探索の方が実装が楽だと思うので、これで通すのが厳しいのはちょっと辛い気がしてしまう。
E - Payment
コンテスト中に問題文は読みましたが、解法がすぐ思いつかず、思いついているDに専念しました。
DPだと言われれば解けますが、ちょっと気付きにくい。言われてみれば。
F - Perils in Parallel
・区間の操作を考えるのは大変→階差を取ることで、二ヶ所切り替える操作になる
ということを思いついた上で、
・グラフへ帰着
すればOK。
どちらも重要そうだけど、どちらも全く気付けなかった。頭に入れておきたい。
二つ目に関しては、以前書いた通り、Codeforces Round #616のC. Prefix Enlightenmentと似た発想だと思う。短期間に二回同じ手法が出題されているので、身に着いていて欲しいなぁ。
この問題は、グラフに帰着した後の実装は難しくないので、ちゃんと解法が身に着いているかが問われている印象。
0 件のコメント:
コメントを投稿