Idiom: Enumerate ranges that decrease(but not strictly)

コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。

この小問題、自分にはなかなか難しいものでした。特に初めの区間のように、単調に減少しないものを処理しなければならない場合は無駄に複雑な実装をして時間を浪費することが多かったように思います(この問題を見るたびに「隣り合う値から微分を検出すれば書けるのでは?」と考えてしまうのが敗因です)。

今日参加したコンテストでも同じように迷い、しゃくとりを使えば簡潔に書けることにやっと気づきました。

for (int i = 1; i <= N; )
  if (a[i] <= a[i + 1]) {
    i ++;
  }
  else {
    for ( ; i <= N && a[i] >= a[i + 1]; i ++)
      ;

    ranges.emplace_back(i, j);  // 区間はinclusive。[i, j]
  } 

しゃくとり以外に工夫していることといえば、処理を簡潔にするために最初と最後に番兵を入れていることでしょうか(実際には先頭の番兵を\(-\infty\)、最後の番兵は\(\infty\)としています)。

隣り合う値から微分を検出しようとしてうまく行かなかったのですが、番兵のアイデアはそのときに微分を確実に取れるように、と思いついたものです(この問題設定だと先頭はなくてもよい)。面白いですね。

これからは迷うことなく書くことができそうです。