WK Works

競技プログラミング（競プロ）に興味が湧き、過去問をつらつらチャレンジしてみています。

難易度順にA〜Gに分かれていて、A、Bくらいの難易度だと特に苦労はない感じだなぁと解けるのですが、C、Dを試すと不正解（WA）や処理時間超過（TLE）が出てきて解説を見てなんとかなるといった具合です。以降の難易度は恐ろしくて見てません。

解説は、こうしたら解けるよねって解説とC++で書かれたプログラムを見られるので、なるほど勉強になるなぁと。ただ、C++は全く使った事ないのでなにやっているんだこれはとよくなります。

で、表題の「lower_bound」C++の関数です。

Perlには標準では無いみたいです。

「イテレータ範囲[first, last)のうち、指定された要素以上の値が現れる最初の位置のイテレータを取得する。」

https://cpprefjp.github.io/reference/algorithm/lower_bound.html

なんのこっちゃですが、二分探索で上記の探索をやってくれる関数みたいです。
そもそも二分探索ってなんやねん！って、ちょっとおバカをさらしておきます。

Perlで実装

Perlでどうやるんだ？と無い頭捻って作って、「俺天才か？」と自画自賛して、意気揚々とソースコードを提出してTLEを喰らった二分探索サブルーチンのソースがこれだ↓

sub Binary_Search {
  my $A      = shift;
  my $array  = shift;
  my $center = int( @$array / 2 + 0.6 ) - 1;
  my $rtn    = $array->[$center];

  if ( @$array == 1 ) {
    if ( $array->[0] <= $A ) {
      $rtn = $array->[0];
    }
    else {
      $rtn = undef;
    }
  }
  elsif ( @$array == 2 ) {
    if ( $array->[1] <= $A ) {
      $rtn = $array->[1];
    }
    elsif ( $array->[0] <= $A ) {
      $rtn = $array->[0];
    }
    else {
      $rtn = undef;
    }
  }
  elsif ( $array->[$center] < $A ) {
    my @next = splice( @$array, $center, @$array - $center );
    $rtn = Binary_Search( $A, \@next );
  }
  elsif ( $array->[$center] > $A ) {
    my @next = splice( @$array, 0, $center );
    $rtn = Binary_Search( $A, \@next );
  }
  return $rtn;
}

サブルーチンに配列を渡して、中央で配列を分割して、条件にあったのを再度サブルーチンに渡すっていう再起処理で実装してます。問題についてくるサンプルでは正解出たんですけど……
時間超過って評価だったけど、もしかしたら条件のつけ方を間違えていてループに陥ったのかも。

それで、どうすればいいか検索して見つけたサイトからヒントを得て、正解に行けたのがこれだ↓

sub lower_bound {
  my ( $array, $cond ) = @_;
  my $h     = @$array;
  my $l     = 0 - 1;
  my $index = 0;
  while ( $h > $l ) {
    my $m = int( ( $h - $l ) / 2 ) + $l;
    if ( $cond > $array->[$m] ) {
      if ( $l == $m ) {
        $index = $m + 1;
        last;
      }
      $l = $m;
    }
    else {
      if ( $h == 0 ) {
        $index = 0;
        last;
      }
      elsif ( $h == $m ) {
        $index = $m - 1;
        last;
      }
      $h = $m;
    }
    $index = $m;
  }
  return $index;
}

使い方は下記、サブルーチンに配列（昇順にソート済み）のリファレンスと検索する値を渡す

my @array = (1, 3, 5, 7, 9, 11);
my $rtn = &lower_bound(\@array, 6);
print $rtn;

# 3

lower_boundの「指定された要素以上の値が現れる最初の位置のイテレータを取得」と似た事が出来ていると思う。
上記の例だと、６以上の要素が現れる最初の位置（７の位置）を返す。

最初に提出したソースだと、配列を破壊するから複製を作って渡すとかいう無駄をしていたことを考えるとすごくスッキリしたなと思う。

おわりに

競プロ、解説見ずに難易度が高い問題を解ける日がくるのだろうか。
解説にΣとか出てくるのだが、問題を見てそういう解法に自力で辿り着ける気がしない……