ABC130（しゃくとり法） - 等身大から1割増し

直近のABC131には不参加でしたが、その前のABC130に参加したので振り返りです。

AとBは省略します。

C問題

「長方形を半分に分割する直線は、すべて対角線の交点を通る」ということを知っていたので、楽に実装できました。

単純にループを回していると、O(N²)になって間に合わなさそうだと分かりました。

Kが大きい場合と小さい場合について、どちらも計算量が減るように実装してみました。

具体的には、Kが大きい場合には左端はそこまで大きくできないので、それに備えて限界値を算出しました。

さらに、ある範囲でKを上回れば、それより右端が右に行っても条件を満たすので、その時点でループを打ち切って該当個数を算出するようにしました。

以下が実装です。地味にDはコンテストで初ACです*1。

自分は1.9秒というギリギリでクリアしましたが、他の人は0.5秒くらいでクリアしています。

解説等を見ると、しゃくとり法という方法を使うといいことが分かりました。

自分が考えた不完全なアルゴリズムを蹴散らす華麗な手法でした。

しゃくとり法を用いて書き直したのが以下になります。

無事、所要時間が0.5秒になりました。

Dが解けたのでうれしかったです。

またがんばります。あと、もう少し早く振り返りを書きます。

*1:コンテスト以外では解説読みながら2，3問しか解いたことがない