ABC130に参加しました
はじめに
今回は計算量改善と考え方に努めた回でした。
問題の発想自体は簡単なものばかり（僕が解ける点数の範囲では）だったのですが、D問題はそのままだとTLEがでてしまったので計算量をいかに減らすかを考えました。
最終的に４完ができたのでいいできだったと思います。
A
特にないです。
しいて言うなら「未満」とか「以上」の意味知っていますか？？
B
Di <= x を満たす分だけカウントしてください。
全てのDiがx以下だった時にループを抜け出す処理をしていなかったので1ペナくらいました。
C
実際にグラフ用紙に書いていろいろやってみたらわかると思います。
長方形の中心と、任意の点の２点を通る直線は長方形を２等分してくれて、結局この時が求めたい最大値なので、(W * H) / 2で答えが出ます。
与えられた点が中心以外の時は２点を通る直線はただ１つ存在するので0、中心の時は無限通り存在するので1を出力します。
これ高校受験を思い出しませんか？
D
見てすぐに累積和だと思って書いて出したらTLEくらったのでいろいろ考えました。
解説では累積和＋二分探索や尺取り法使っているんですが、自分は区間和の計算の始めどころを絞り、区間の片側を固定した時、ある区間の和がK以上ならそれよりも区間が大きくなれば必ずカウントされるじゃんって考えて、書いて出してみたら通ってしまいました……。
二分探索から逃げている節があるので、知らなかった尺取り法と一緒に勉強しようと思います……。
計算量改善と、あと単純にlong longにし忘れていたのもあって4ペナくらいました。
おわりに
今回もD問題を解くことが出来たのでよかったです。
昨日と相まってたくさんレートが伸びてくれました。
うれしい。
