Algorithmコンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。24]を列挙することです。この小問題、自分にはなかなか難しいものでした。初めの区間のように、単調に減少しないものを処理しなければならない場合は無駄に複雑な実装をして時間を浪費することが多かったように思います(この問題を見るたびに「隣り合う値から微分を検出すれば書けるのでは?」と考えてしまうのが敗因です)。今日参加したコンテストでも同じように迷い、しゃくとりを使えば簡潔に書けることにやっと気づきました。区間はinclusive。しゃくとり以外に工夫していることといえば、処理を簡潔にするために最初と最後に番兵を入れていることでしょうか(実際には先頭の番兵を\(-\infty\)、最後の番兵は\(\infty\)としています)。隣り合う値から微分を検出しようとしてうまく行かなかったのですが、番兵のアイデアはそのときに微分を確実に取れるように、と思いついたものです(この問題設定だと先頭はなくてもよい)。これからは迷うことなく書くことができそうです。Search先日参加したコンテストで以下のような問題が出題されました1。Prime素数を扱う簡単なアルゴリズムはO(√n)で行えます。