ごりちゃんがゆく

競プロをするゴリラの精進記録

「配列のすべての要素が条件を満たすならtrueを返す」関数に空の配列を渡したら？

アルゴリズム

今日のお話

こんなツイートが話題になっていましたね！

まあ～こうすべきだああすべきだといろんな議論がされていましたが、trueを返すのが正解 だよ、というのと、それについて自分なりの解釈を書こうと思います
ゴリゴリの論理よりは感覚的に理解できる記事を目指します

言い換えてみる

国語の問題っぽく考えてみます。

「配列のすべての要素が条件を満たすならtrueを返す」関数

とあるが、まず暗黙的になっている部分を補完すると

「配列を引数として受け取り、配列のすべての要素が条件を満たすならtrueを返し、それ以外の場合はfalseを返す」関数

と解釈します (これは異論ないよね) 1

で、「それ以外の場合」のところを言語化すると、「すべての要素が条件を満たす」の否定なので、「どれか1つでも条件を満たさない」となります。

どれか1つでも条件を満たさないならば false。

いうなれば 「条件を満たさないもの検出器」 2 を作りましょうというわけです。

真偽値が逆なのでちょっとややこしいですが、条件を満たさないものがあれば false、なければ true を返したいです。

で、この、「条件を満たさないもの検出器」に、空配列を与えたらどうでしょうか？
条件を満たさないもなにも、要素自体がないので、条件を満たさないものは当然ありません。
つまり、上の太字の部分に当てはめると trueが妥当 となります。

DPで考える (DPの超入門)

ちょっと別の解釈です。

たぶんこの記事を読んでいる方の多くは、これくらいの関数なら見た瞬間実装できる方だと思うので、わざわざDPを？と思ったかもしれません

が、これを実装するときに書くロジックはDPの考え方とほぼ変わりないはずなので、あえてDPとして解釈してみます。3

dp 配列を以下のように定義します

dp[i] := 配列の先頭i個までを見たときの途中経過 (true / false)

dp

たとえば、dp[2] は、引数配列 (Aとします) の先頭2個、つまり A[0]とA[1] まで見た時の途中経過です
最終的に求めたい答えは dp[N] です。(N は配列の長さ)

すると、以下のように遷移するはずです
※ f(A[i]) では、A[i] が条件を満たせばtrue、満たさなければfalseが返るとします

&&

dp[i+1] には、dp[i] と f(A[i]) の論理積 (&&) を入れれば良いとわかります 4

なぜ論理積 (&&) で良いかというと、先頭 i+1個までみた途中経過 dp[i+1] の求め方を真理値表にまとめると、下記のようになるからです。

dp[i] f(A[i]) dp[i+1]
true true true
true false false
false true false
false false false

途中経過 dp[i] も trueで、f(A[i]) も true のときに限って、dp[i+1] もtrueにしたいわけで、これは論理積がちょうど使えます。

さて、DPを解くのには、遷移だけでなく初期値を与える必要があるのでした。
このとき、dp[0] はどうあるべき？
と考えると、falseでは正しく動きません。
なぜなら、xとyの論理積 x && y を考えると、xか yどちらかが falseなら 結果もfalseとなってしまうからです。
つまり、 dp[0] が false だと仮定すると、dp[1] は A[0] の値に関係なく falseとなってしまいます。
これだとどんな配列が来ても結果がfalseになってしまい、まずいです。
ところが dp[0] が true だと、このDPのロジックはうまく動作します。
dp[0] とは、「配列の先頭0個までを見たときの途中経過」であったので、これは空配列を与えたときの結果といえます。
やはり、空配列を与えたときの結果は true が妥当だと確かめられました。

単位元

ある演算に適当にまぜたときに、計算結果に影響を与えない値のことをその演算の単位元と呼んだりします。5
今回の、論理積という演算における単位元は true です。
他にも、論理和では false、足し算は0、掛け算は1、minはINF、GCDは0、... など、いろいろあります。
x + 0 = x
で、xに0を足しても確実にxだよね、みたいなイメージです。
結合法則が成り立ってて単位元がある演算 (=モノイド) は、セグ木に乗ることでおなじみです！

おわり

読んでくれてありがとうございます！
ではまた！

  1. 配列じゃなくてiterableでいいじゃん、とかそういうのはぬきで　(もとの問題設定が配列って言ってるので)↩
  2. 575↩
  3. DP配列を陽に持つ必要がない、などの違いがありますね↩
  4. 実用的には、f(A[i]) の falseを検出した時点で falseを返すのが良いです　無理やりDPにしているのでこうなっています↩
  5. このへん感覚で理解しており、詳しくないので石を投げないで～↩