えびちゃんの日記

えびちゃん（競プロ）の日記です。

「任意の」を「全ての」と読み替えさせる風潮に対するお気持ち表明

「任意の」の気持ちがわかっていないまま、そういう文を読まされるのもつらいと思うので書きます。

言葉の意味に関して

「任意の \(x\in S\) に対して \(P(x)\) が成り立つ」と言ったとき、これを「全ての \(x\in S\) に対して \(P(x)\) が成り立つ」と読み替えないとちゃんと解釈できない人がいるようです。「数学における「任意の」は「全ての」という意味」などと教えるのはよくないような気がしています。

「\(S\) から任意に選ぶ」と言ったとき、「\(P(x)\) を成り立たせるように自由に選ぶ」という意味合いはないです。 どちらかというと、「\(P(x)\) が成り立ってほしくない人が \(S\) から自由に選んでも、\(P(x)\) が成り立ってしまう」という方が近いかもしれません。

「全ての」と読み替えたとしても、証明の段階になると「\(x\in S\) を固定する」などといったことをする必要があり、それなら最初から「任意の」の気持ちでいた方が自然なのでは？と思ってしまいます。

また、「任意の \(x\in S\) を選ぶ」などの文脈では「全ての \(x\in S\) を選ぶ」とはできず、うまくいかない気もします。

空の場合に関して

たとえば、「任意の \(x\in S\) について \(x\) が偶数であるとき、\(S\) を偶数集合と呼ぶ*1」としてみます。

\(\{2, 6, 12\}\) を見た初心者は「\(2\) も \(6\) も \(12\) も偶数なので、それは偶数集合であるなあ」となるし、\(\{4, 3\}\) を見た初心者は「\(4\) は偶数だけど \(3\) は偶数ではないからこれは偶数集合ではないなあ」となるでしょう。

このとき、\(\{2, 6, 12\}\) に関しては “偶数集合っぽい根拠” として \(2\) などがあるので安心感がありそうですが、空集合 \(\emptyset = \{\}\) ではそうした根拠っぽい要素がないため、不安になる人もいるような気がします*2。

実際には、「任意の \(x\in S\) に対して \(P(x)\) が成り立つ」と言ったとき、「実際に何らかの \(x\in S\) が存在して \(P(x)\) を満たす」という必要はないため、そうした根拠を探す必要はありません。

擬似コードで言えば、次のようなイメージです。

fn for_any(s: Set, p: Predicate) -> bool {
    for x in s {
        if p(x) {
            continue; // ok, do nothing
        }
        return false; // bad element found
    }
    true // no element is bad
}

s が空のときは true になりますね。

あるいは、「任意の \(x\in S\) について \(P(x)\) が成り立つ」の否定は「ある \(x\in S\) が存在して \(P(x)\) が成り立たない（\(\neg P(x)\) が成り立つ*3）」となりますが、空のときは \(\neg P(x)\) が成り立つような要素が（\(S\) が空なので）存在せず、これは偽となります。 否定した命題が偽だったので、元の命題は真であるとわかります。

先の初心者の気持ちに基づく「\(S\) の中にそれっぽい要素がないから、「任意の〜」は偽？」だと辻褄が合わないことがわかりますね。

ところで、vacuous truth という用語があるようです。

別の例

配列 \(a = (a_0, a_1, \dots, a_{n-1})\) に対し、任意の \(1\le i \lt n\) について \(a_{i-1}\lt a_i\) が成り立つなら \(a\) は単調増加であると言う。

このとき、要素が 1 つしかない配列 \(a = (a_0)\) は単調増加と言えるでしょうか？

\(n = 1\) なので、任意の \(1\le i\lt 1\) について \(a_{i-1}\lt a_i\) が成り立つ必要がありますが、そのような \(i\) は存在しない（\(\{i\mid 1\le i\lt 1\} = \emptyset\)）ので、これは自明に*4真であり、\(a\) は単調増加と言えます。

\(n = 0\) である空の配列 \( ()\) についても同様です。

英語に関して

「任意の \(x\) に対して〜」の文脈で、英語だと “For any \(x\in S\), \(P(x)\) holds.” とか言ったりします。「どう選んでも満たす」感がある気がします。

一方で、“If any element satisfies the predicate, ...” と言ったとき、「何らかの要素がその述語を満たすなら、」となり、「ある○○が存在して」の意味で any が使われているので注意が必要かもしれません。「どれかしらが満たすなら」感がありそうです。

If の文脈で「任意の要素が」と言いたいときは “If every element satisfies the predicate, ...” とか言える気がします。

イテレータや配列の全ての値が条件を満たす・条件を満たす要素があるか判定する関数が慣例的に all any と命名されがちですが、混乱する人もいそうです。 JavaScript では every some と命名されており、曖昧じゃなさそう感があります。

「every や each などは個々を意識しており、all は全体として指している」のような話があった気もします。証明の際にも個々を意識して（要素を固定して）いますね。any も前者側だと思います。

関連？

よく「\(0.999\ldots = 1\)」というのが直感に沿わない（\(0.999\ldots \lt 1\) な気がするもん）という話がありますが、これと同様、記法や言葉の定義を知らないまま「任意と言いつつ自由に選べないのは変な気がするもん」と言って「全ての」と言い換えようとするのはよくなさそうな気がします。

定義を知った上でも自分の直感に沿わない場合は、その表現を常用している人がどういう直感を持っているか考えてみるとよいかもしれません。

おまけ

おわり

にゃんい

*1:適当に命名しました。

*2:空集合を \(\phi\) と呼ぶ人に対するお気持ち表明。\(\phi\) と \(\emptyset\) は別の記号です。たとえば「シ」と「ツ」が別の文字なのと同様ですね。

*3:\(\neg P\) は \(P\) の否定を表す。

*4:ここでの「自明」とは「定義から直接的に導かれる」くらいの意味合いであり、「初心者にとっても直感的にわかる」のような意味合いではないので、注意が必要かもしれません。

初心者が陥りがちな嘘貪欲やコーナーケースやその他諸々に関して

「初心者が貪欲法を覚えて、全てそれで解こうとしている」のかな？と思い込んでいたのですが、そうではないような気がしてきました。 諸々のコーナーケース（off-by-one 系の境界条件とか）についても同じような背景がある気がするので書きます。

やや厳しい話に受け取られそうな内容ですが、「理想的には、」のような前置きがあるものとして、そうでない人も深刻に受け止めず「のびしろだな〜」くらいに思ってもらえばいい気がします。

思ったこと

貪欲法に限らず一般に、「こうだったらうれしいな」という思い込みに基づいて実装した後、「なんで WA になるんですか？」と言う人がたくさんいる気がするんですが、順番が正しくないと思います。 「こうだったらうれしいな」の部分を証明するか、せめて「こういう根拠で正しいと思う」というのを用意するのが先な気がします。

たとえば、「\(16/64 = 1/4\) なのだから数字ごとに約分できて \(17/73 = 1/3\) だろう」とか「\(\log(1+2+3) = \log(1)+\log(2)+\log(3)\) なのだから一般に \(\log(x+y+z) = \log(x)+\log(y)+\log(z)\) だろう」とか、そうしたものと同種の思い込みが背景にあるような気がします。

「\(\log(2)+\log(3)+\log(4) = \log(9)\) としたがなんでだめなんですか？」ではなく、どうしてそのような式変形が妥当と思ったかを示してほしいです。なんというか、これは反語で皮肉を言いたいわけではなくて、根拠を持った上で考察を進めるべきというスタンスが理想的だという主張です。

ABC の序盤〜中盤で出てくる最適化問題の多くで、「こうだったらうれしいな」に基づいたアルゴリズムがたまたま貪欲法と一致しているだけで、必ずしも貪欲法として実装したがっているわけではなさそうな気がしました。実際には、貪欲法を覚えたあたりで「これは貪欲でいいのでは？」とか考えがちになりますが、貪欲法を知らなければそれを防げるわけではなさそうですね。

補足

もちろん、「こうだったらうれしいな」というのを考えることは大事です。 そのとき、たとえば考察用紙に「こうだったらうれしい ※未証明」とかメモしておき、うまくいかないときはそこを疑う（+ 反例を考える）とかをしやすいようにしておくとよさそうです。証明済みのこととそうでないことを混ぜておくとめちゃくちゃになりがちです。

自分で証明したと思い込んだことの中にミスがあったりしてめちゃくちゃになることもありますが、それはそれでなんとかしましょう。

ある程度慣れてくると「証明する」のような言い回しが、（コンテスト中で忙しい場合は特に）厳密な証明ではなく、「「こういう方針で証明できると思う」くらいのものを用意する」を指したりしますが、最初のうちはその方針が間違っていることも多いので、ある程度ちゃんと行うべきな気もします。わかるようになって思考をスキップするのと、わからないまま思考停止して祈るのは違います。

よくある嘘の例

「制約が \(n \le 10^5\) で、愚直だと \(\Omega(n^2)\) になってしまうから、なんとかして探索範囲を狭めて TLE を避けよう」というのはよくあります。そのとき、証明をせず「ここは探索しなくていいだろう」とした範囲に最適解があるみたいなことはありがちです。

たとえば、「\(1\) 以上 \(n\) 以下の整数の総和を求めてね」について「\(30\) 以下の整数は無視していいか」となる人は少ないと思いますが、多少複雑な関数に対して「その最大値を求めてね」のような状況だと、「この範囲は探さなくていいかも」と勝手に思ってしまいそうです。

その結果、たまたま俗に言う貪欲法と一致することが多く、「初心者は貪欲法しがち」みたいに思ってしまいがちだったかもしれません。

区間和の最大値

配列 \(a = (a_0, a_1, \dots, a_{n-1})\) があり、ある区間の和 \(a_l + a_{l+1} + \dots + a_{r-1}\) (\(0\le l\le r\le n\)) の最大値を求めてね。

  • \(1\le n\le 10^5\)
  • \(|a_i| \le 10^9\) for \(0\le i\lt n\)

入出力例

8
1 2 3 -1000 4 5 -1000 6

9

こうしたサンプルを見ると、「負の値を足しちゃうとうれしくないから、負の値が出現するごとに区切って 1 2 3 4 5 6 のようにして、各部分の和の最大値を求めればいいのでは？」と思ってしまう人もいそうです。たぶん。

実際は、1 2 3 -1 4 5 -1 6 のようなケースでは、全部足して 19 になるのが最大です。 「こういう風に絞っていいのでは？」と思ったときは、そう絞ることで見落としてしまうケースを作ってみようとするとよいかもしれません。 嘘予想の多くの場合は、誤りのケースの方がたくさんあるので、適当なケースを作って愚直解と比較してもよさそうです。

また、\(a\) の最大値が必ず含まれるとは限らないですが、うまく誘導されると引っかかってしまうかもしれません。最初のサンプルでは 6 が使われないのでバレてしまいそうです。

物足りない人向けの課題

  • 正しい解法を作り、証明してみましょう。
  • クエリ形式で解いてみましょう。
    • \(a_i\) の更新クエリと、\(x, y\) に対して \(x\le l\le r\le y\) での \(a_l + \dots + a_{r-1}\) の最大値クエリ

解法メモ

Kadane’s algorithm というのが知られている。

クエリ形式の方は、ABC 175 D の解説 に関連する話題を書いた。

（メモおわり）

比の最大化

\(a = (a_0, a_1, \dots, a_{n-1})\) と \(b = (b_0, b_1, \dots, b_{n-1})\) と \(k\) が与えられる。\(|I|=k\) なる \(I \subseteq \{0, 1, \dots, n-1\}\) を選び、 \[ \frac{\sum_{i\in I} a_i}{\sum_{i\in I} b_i} \] を最大化してね。誤差は \(10^{-6}\) くらいまで許容するよ。

  • \(1\le k \le n\le 10^4\)
  • \(a_i, b_i \in [1, 10^7]\cap\Z\)

入出力例

3 2
3 4 3
4 1 2

2.333333

\(I = \{1, 2\}\) で \(\frac{4+3}{1+2}\) です。

「\(a_i/b_i\) が大きいものから順に選んでいくか？」とか「その時点の \(\frac{x}{y}\) から \(\frac{x+a_i}{y+b_i}\) が最大になるものを選ぶか？」とかを考えがちな気がします。

4 3
1 5 4 4
2 5 1 4
1.3

その時点から最もよくなるものを選ぶ貪欲法だと、\(\frac{4}{1}\) → \(\frac{4+1}{1+2}\) → \(\frac{4+1+4}{1+2+4}\) となって \(1.285714\dots\) となってしまいそうです。 実際には \(\frac{5+4+4}{5+1+4} = 1.3\) を達成できて、これが最適です。

課題

  • \(a_i/b_i\) の値に基づく方の貪欲法で WA になるケースを探してみましょう。
  • 正しいアルゴリズムを作ってみましょう。

解法メモ

答えを決め打ちして二分探索。\(\frac{\sum_i a_i}{\sum_i b_i} \ge x\) を満たすかを判定。\(\sum_i (a_i-b_i x) \ge 0\) と変形できて貪欲に選べる。

Dinkelbach’s algorithm というのもあるらしい。

（メモおわり）

数え上げ

ぱっと出なかったのでそのうち例を考える。 → 思いついたので追記です。

配列 \(a = (a_0, a_1, \dots, a_{n-1})\) と整数 \(x\) が与えられる。 空でもよい区間 \([l, r)\) (\(0\le l\le r\le n\)) であって、和 \(\sum_{i=l}^{r-1} a_i\) が \(x\) 以下であるものの個数を求めてね。

  • \(1\le n \le 10^5\)
  • \(|x|, |a_i| \le 10^9\)

入出力例 1

4 5
6 8 -2 3 

8

\([0, 0)\), \([1, 1)\), \([2, 2)\), \([2, 3)\), \([2, 4)\), \([3, 3)\), \([3, 4)\), \([4, 4)\) の 8 個。

入出力例 2

4 7
6 8 -2 3

10

上記に \([0, 1)\) と \([1, 3)\) を加えた 10 個。

「区間を伸ばしていって、和が \(x\) を超える or \(x\) より十分大きくなったら打ち切る」とか二分探索をしようとする人がいるかもしれません？

\(a_{n-1}\) がとても絶対値の大きい負の値*1だった場合などは、和が \(x\) よりある程度大きくなっても無視できないのでだめそうです。

課題

解法メモ

各 \(r\) (\(1\le r\le n\)) に対して \(\sum_{i=0}^{r-1} a_i\) の値をカウントしておく。 各 \(l\) (\(0\le l\lt n\)) に対して順に、\(x+\sum_{i=0}^{l-1} a_i\) 以下の個数を数え、上記のカウントから \(\sum_{i=0}^{l-1} a_i\) の個数を 1 引く。

座圧したりセグ木に乗せたりすれば \(O(n\log(n))\) time でできる。空区間は適当に別で処理する。

ちゃんと考えればセグ木とか使わずにできるかも？ ちゃんと考えなくてもセグ木とか使ってできればいいでしょうという見方もある。

（メモおわり）

\(x \lt 0\) のケースだと空区間が許されないから、「\(n+1\) 個の空区間を最後にまとめてどうの〜」をするときに考慮が漏れるとこわれるかも。

データ構造の知識に乏しいためか、「全ケースを考慮した上で高速化する」ではなく「特定のケースを考えないことにする」で高速化を図ろうとする人が多いのではないかと思ったりしました。そんなことない？

お釣りの枚数の最小化

思い出したので追記です。

配列 \(a = (a_0, a_1, \dots, a_{n-1})\) が与えられる。 \(a_i\) 円の硬貨の組み合わせで \(k\) 円のお釣りを払うとき、使う枚数を最小化してね。

  • \(1\le n\le 100\)
  • \(1\le k\le 10^5\)
  • \(1 = a_0 \lt a_1 \lt \dots \lt a_{n-1} \le 10^5\)

入出力例 1

6 89
1 5 10 50 100 500

9

\(50 + 10 + 10 + 10 + 5 + 1 + 1 + 1 + 1\) と払うのが最適です。

単に「\(n\) 円払うときの」という言い方でないのは、「お釣りが生じたら？ ちょうど払わなかったら？」のような曖昧さを無くすためな気がしています。

日本の通貨においては、額面の大きい方から払えるだけ貪欲に払うのが最適になります。 そうした体系に慣れていると、常に貪欲に処理していいという誤解が身についてしまうかもしれません。

\(a = (1, 3, 4)\) と \(k = 6\) のとき、貪欲に使うと \(4+1+1\) ですが、最適な払い方は \(3+3\) です。

調べてみたら記事がありました。

qiita.com

この問題が貪欲に解けないこと（と簡単な反例）を知っていると、似た問題が出たときに「これは貪欲で解けるわけなくない？」といった気持ちになりやすそうです。実力が上がるにつれて変な貪欲法に引っかかりにくくなるのも、こうした背景があるかもしれません。

その他

メモ程度に。

グラフで二部マッチングかなんかが想定なときによくある嘘みたいなのがあった気がする。

初心者が安直に考えるとこういう単純化がされがちみたいなパターンはありそう。

コーナーケースの話

何らかの処理を行う際に、その処理が仮定している条件を勝手に無視して進めてしまい、後からコーナーケースに気づき「非本質だこんなの！」と怒ったりする人は多い気がします。「多くのケースでそれっぽいから 9 割の点数をくれ」などができる競技ではないので、大枠だけ考えて満足してはいけません*2。

えびちゃん的には、さっきのケースと似た短絡的思考が背景にあるのでは？と思っています。 「（考えつく）多くのケースでそれっぽいからいけそう！」というのは正当性の根拠にはなりません。

具体的なケースを考えるのも重要ではありますが、それよりも「自分の行いたい処理が常に許されるか？」というのを考えるのが重要です*3。具体例を出そうとすると、自分に都合のいいケースを考えがちです。

たとえば、単純なものとしては次のようなものです。

  • 配列に添字でアクセスするとき、配列外参照にはならないか？
    • 配列サイズ以上になることはないか？
    • 添字が負になることはないか？
      • 負の添字で逆からアクセスする言語だとエラーにならず気づきにくいかも。
  • 除算を行うとき、ゼロ除算にはならないか？
    • 二次元平面上の直線を扱う際に y 軸と平行なケースは？とか、そういう感じで生じがち。
    • 実装段階というよりは考察段階で気をつけるべきかも。
  • 四則演算を行うとき、オーバーフローは起きないか？
    • 重箱の隅をつついている感はありますが、除算でもオーバーフローは起きえます。
  • __builtin_clz で最下位ビットを得ようとするとき、引数は 0 ではないか？
  • sqrt の引数が負にならないか？
    • 誤差で \(-\varepsilon\) になったりしないか？
  • double の誤差は大丈夫か？
    • 整数を扱いたいなら \(2^{53}\) を超えないか？
    • 詳しくは こっち。
  • lower_bound で得たイテレータにアクセスするとき、.end() が返ってきていないか・返ってくることはないか？
    • lower_bound には限らないですが、よくありそうなので。

実装面でなく考察においても、たとえば、「要素を二つ選んで何々をする」といった状況においては、「要素が一つ以下しかない場合は？」というのは気をつけるべきです。 あるいは、法 \(m\) で除算したい際に \(m\) と互いに素であるかを確認する（特に \(m\) の倍数の場合に注意が必要かも）とか、いろいろあります。なんでもかんでも無条件でできる操作ばかりではありません。

こうした場合分けが生じる状況では、それらを先に処理するか、最低限メモしておくのがよい気がします。

関数呼び出し一つ一つ、演算子一つ一つについて「これは（問題の制約下で）大丈夫か？」を常に意識して考える訓練をしてもいいかもしれません。 慣れてくれば無意識に一瞬でできるようになるでしょうが、それまではちゃんと訓練するのが大事だと思います。

｢ドアが開いているのを確認せずに部屋に入ろうとして、実はドアが開いていなくてぶつかったことにキレる人」はやばいと思っているのですが、この手のコーナーケースも似ている気がします。

えびちゃんは、ワンランク下くらいの問題を丁寧に（雰囲気で自明にわかっても、ちゃんと言語化して考察して）解く訓練を一時期していました。 適正くらいの難易度帯の問題に対して雰囲気で解こうとしてうまくいかないことが多かったので、地に足をつけてちゃんと考察をする癖をつけたかったです。 それをいきなり適正難易度でやるのは大変だったので下の難易度帯で、ということです。

他にも、制約や TL を指差し + 声出しで確認したりもしていたかも。「\(n\) は \(3\) 以上、ヨシ！」「境界含む、ヨシ！」など*4。

TLE 関連の話

TLE の際に「こうすれば高速化できそう〜」と期待して実装したものの、最悪ケースでは改善されていないということもよくあります。 最悪ケースがなにで、自分はどう改善したいのかとかを意識したらいいのではないでしょうか。

言語仕様に詳しくないせいで、計算量が悪い処理を書いて「なんで TLE なのですか？」となるのも多いです。以下は Python の例です。

  • xs = xs + x
    • xs + x をするために xs の無駄なコピーが作られるため
    • xs += x や xs.append(x) などがよい
  • xs.pop(0)
    • xs の [1:] の要素を一つずつ前に詰めるため
    • list ではなく deque を使うのがよい
  • x in range(n) (Python 2)
    • [0, 1, ..., n - 1] が作られるため
    • 0 <= x < n などがよい
    • Python 3 では大丈夫

Python は（定数倍が）重いと思われていがちなので、こうした処理をしても「定数倍が重いせいだ」と勘違いされがちかもしれません。

実装方針の話

最初のチャレンジでコードが汚くなってしまうのはよくあることですが、綺麗に書き直す練習をしてみるといいかもしれません。 似たような問題が出たときに、簡潔に書けるようになる気がします。 「単純なはずのことに無駄に煩雑なコードを書いてバグらせる」というのを減らすのが重要です。

たとえば、ランレングス圧縮 (run-length encoding; RLE) というのがあります。 与えられた配列に対して、連続する値を「値と連続回数のペア」にするものです。

例：[1, 1, 1, 5, 3, 3, 5, 1] → [(1, 3), (5, 1), (3, 2), (5, 1), (1, 1)]

慣れていないと、これを煩雑に書いてしまいがちな気がします。

初心者がやりがちな（気がする）煩雑になりがちなパターンの例です（RLE に限った話ではないです）：

  • 広めの範囲で使い回すフラグ変数を作り、がんばって更新する
    • 更新漏れが生じがち
    • tmp f flg flag のような命名をして、自分でも true/false で混乱しがち
  • 一旦「条件を満たさない状態」を不必要に作ってから 1 を引いたりして辻褄を合わせる
    • 辻褄を合わせるのを忘れる
    • 辻褄を合わせる処理でバグらせる
    • 辻褄が合わないケースを見落とす
  • 必要以上に場合分けを作る
    • 足りないよりはいいが、考察が不十分なせいで生じているのではないか？
    • 「生じうるコーナーケースのために念のため場合分けをしておく」が有用な場合はある

「この時点でこの変数はこういう条件を満たす」というの（不変条件 (invariant condition) とか呼ばれます）を意識してみるといいかもしれません。

\(n\) 個の要素に対して、行いたい処理は何回なのかを意識してみるといい場合もあるかもしれません。以下は例です。

  • \(n\) 回：各要素について処理する
  • \(n-1\) 回：各要素の境界について処理する
  • \(n+1\) 回：先頭からいくつ選ぶか（空も許可）について処理する

rsk0315.hatenablog.com

関連するかも。

解いた後の話

「たまたまうまくいった」では成長しないので、「なんでこれでいいか？」「どういうケースで落ちていたか？」を考えるのが重要です。

「添字の +1/-1 を繰り返してたまたまうまくいったからおっけー」みたいなのを勧めない理由もこれです。 慣れてくると、「これらのケースを試してうまくいく添字の組はちょうど一つなので、それらを試して決める」などをすることもありますが、最初は素直に考える方がよさそうです。

例題

いくつか例題を挙げます。丁寧に解いてみるとよいでしょう。

注意

WA になって「なんとなくここの処理が怪しそう！」と直して再提出するのではなく、「こういうケースで正しい答えが出るようになる」というのを作ってみるのがよいでしょう。 それを試した上で WA の個数が減らなくても、別のバグも一緒に含むケースで WA のままだったということはありえるので、変に早とちりして「無関係だったのか」とならない方がよさそうです。

あと、「こういうケースが入っていたらまずそうだが...」と思ったときは、そういうケースが入っているものとして考えるのがよさそうです*5。

きもち

とにかく、「十分慣れた（同じことを丁寧に考えたことがある）ので、もう考えずに正しくできる」に至ったわけではないのに「思考停止したい！」となるのはよくないと思います。ちゃんと丁寧に考える癖をつけるのがよいと思っています。

これは口を酸っぱくして言っている気がします。

おすすめ

「どこにバグがあるかわからない」とならないように丁寧に考えてから実装するのが理想的ですが、どうしてもそうなることはあります。

そうしたとき、そのコードは嫌いな人が書いたものだという気持ちで読むと、「なんとしても WA になるケースを探してやる」となり、「こういうケースの考慮が漏れているだろう」というのが見つけやすくなる気がしています。

「嫌いな奴が書いたコードなんて消してやる」となって一から書き直すという手もあります*6。

勉強に関して

ぬるっと追記です。

「問題にこういう性質があるから○○の方針を考える」ではなく、「D 問題で 998244353 だから DP」「E 問題で区間クエリだからセグ木」のような、本質を見ないパターンマッチをする人もよく見る気がします。

アルゴリズムの勉強をする際、「こういう状況で使うことができる」だけではなく「こういう状況では使えない」というのを意識しておくことが重要そうな気がします。前提条件を押さえておくのに似ていそうです。

そうしたことをちゃんと意識しておくことで、変なパターンマッチで沼にはまることが減らせるような気もします。 力不足のせいで勝手に使えないと思い込んでしまう場合もありますが、勘で使えると思い込むよりは慎重でよい気がします。 「実はこの状況でもこのアルゴリズムで解けるのか〜〜」のような体験をすると、そうしたアルゴリズム・そうした問題がお気に入りになりそうです。

なんかめっちゃふわふわした主張になってしまいました。

読むといいかも

inzkyk.xyz

貪欲法関連です。

おわり

rsk0315.hatenablog.com

本当はお盆の間に書く予定だったのですが、間に合いませんでした。

これを書き切る前にまた別のお気持ち表明テーマが出てきてしまったので、また書くと思います。

*1:「とても小さい」だと \(0.0001\) のような値と紛らわしいため、こうした言い回しをする傾向がある気がします。

*2:初心者に限らないですが、主観で本質・非本質を決めつけたがる人はたくさんいる気がします。コーナーケースとか定数倍とか。冗談半分で言っているかも。

*3:さっきの例では、「探索範囲を狭めてよいのか？」「捨てた範囲以外に最適解が常にあるか？」というのを考えるのに相当します。

*4:現場猫のせいでネタにしか見えない。実際ネタだと思ってやっていた感はありますが。

*5:ジャッジがお粗末なサイトだとその限りではないでしょうが。

*6:かわいそう。

lower_bound で混乱している人かわいそう

言語さんサイドにも問題があるというのはそうかも。

とはいえ、理解が足りないまま「わかりにくい」と言っている人はかわいそうなので、解説をします。

名前について

なんで「x 以上の最小値を得る関数」が lower_bound と呼ばれているのかわからん*1

まず、それを得る関数ではないです。イディオムとしてそう覚えてしまっているような人が多いため、こうなってしまう人が多い気はします。

実際には値ではなくイテレータを返すもので、「x と等価 (equivalent) な値がある区間の下限の位置」が返ってきます。ここでの equivalent というのは == とは違う概念なのですが、とりあえず（int のような型では）== と同一視してよいので、詳細は後述とします。

また、upper_bound についても同様で、「x より大きい最小値を得る関数」ではなく、「x と等価な値がある区間の上限の位置を返す関数」です。区間は半開区間の形で表されることに注意します。

5 と等価である区間の例の図です：

[1, 3, 5, 5, 6, 7]
       [----)
       L    U

つまり、[lower_bound, upper_bound) の区間が、x と等価な区間ということになります。lower_bound と upper_bound のペアを返す、equal_range という関数もあります。

等価な値がないケースに関して補足

より厳密には「x 未満の区間と x 以上の区間の境界」「x 以下の区間と x より大きい区間の境界」として定義されているので、たとえば先の例での “4 と等価である区間” は次のような空区間になります。

[1, 3, 5, 5, 6, 7]
     [)
     LU

そうした境界がない列（[1, 8, 5, 5, 3, 6, 5] で x = 5 など）については未定義動作なので、C++ 側はそういう入力がないと仮定して問題ありません*2。 ここで境界と言っているのは、「その境界で以って配列を二分割できる」というものであり、そうした境界が存在しないからだめということです。

なお、そうした境界さえあれば、ソート済みである必要はありません。たとえば [1, 4, 2, 5, 5, 8, 5, 6] で x = 5 は、lower_bound であれば問題ありません（upper_bound はだめ）。 [1, 4, 5, 5, 7, 6, 8] で x = 5 は、lower_bound も upper_bound も問題ありません。

よくあるイディオムについて

*std::lower_bound(_, _, _) で一つのイディオムとして覚えていると、こうした「境界」を意識しないようになってしまう気がします。わかった上で思考をスキップしているのであれば問題ないとは思いますが、知らずにやっていると混乱の元になりそうです*3。

[1, 3, 5, 5, 6, 7]
       [----)
       L    U

ここで、*L や *U としてアクセスすると 5 と 6 が返ってくるので、結果的にはよくある「5 以上の最小値」「5 より大きい最小値」のようになります。

当然、L U が配列の末尾を指していた場合（全部の要素が 5 未満・以下の場合）は配列外参照で未定義動作なので注意が必要です。 「値が返ってくる」という認識だと、こういうケースでバグらせて逆ギレしそうです。

equivalence について

x == y のとき x is equal to y と言い、y <= x && x <= y（より言語仕様っぽく言えば !(x < y) && !(y < x)）のとき x is equivalent to y と言います。前者における “等しさ” を equality と言い、後者における “等しさ” を equivalence と言います。 x <= y は x < y || x == y ではなく !(y < x) として（< の形で）扱われることに注意や慣れが必要です。

< は strict weak ordering と呼ばれる順序を成している必要があります。これは、次の 4 つの条件で表されます。

  • !(x < x)
    • 「自身が自身より大きい」ということにはならない
  • x < y ならば !(y < x)
    • 「相手が自分より大きいのに、自分も相手より大きい」ということにはならない
  • x < y && y < z ならば x < z
    • 「自分より大きい相手よりさらに大きい（別の）相手は、自分より大きい」
  • equiv(x, y) を !(x < y) && !(y < x) で定義するとき、equiv(x, y) && equiv(y, z) ならば equiv(x, z)
    • 「x と比較不能である」ということを「x と “等価” である」ということにできる
      • !(x < y) && !(y < x) を「x と y は比較不能である」と言う
      • 「equiv(x, y) && equiv(y, z) ならば equiv(x, z)」などの性質から equiv は同値関係を成している

「x と比較不能である」を「x と等価である」と言えない状況の例を考えてみます。x < y を x.first < y.first && x.second < y.second で定義しようとしてみます。 このとき、x = {2, 2}, y = {3, 0}, z = {1, 1} のようにすると、equiv(x, y) && equiv(y, z) ですが z < x なので equiv(x, z) ではありません。 C++/STL の関数の順序を扱う関数（std::sort など）の多くは strict weak ordering を仮定しているため、そうでない順序を与えようとすると、やはり未定義動作となります*4。ソートしようとして、無限ループになったり配列外参照が起きたりすることもあります。

そこで、例えば「10 で割った値での比較による順序」を考えます。std::sort など同様に比較関数を渡せます。

int main() {
    std::vector a{12, 10, 13, 21, 20, 25, 31, 32};
    auto div10 = [](auto x, auto y) { return x / 10 < y / 10; };
    auto [lb, ub] = std::equal_range(a.begin(), a.end(), 24, div10);
    // [12, 10, 13, 21, 20, 25, 31, 32]
    //              [----------) <- この区間となる
    //              L          U
}

ここでは 21 と 24、20 と 25 などが equivalent であることに注意しましょう。他にも、「（pair の）first だけの比較による順序」なども定義できそうです。

クイズ：先の例 x.first < y.first && x.second < y.second と逆に、x.first < y.first || x.second < y.second とした場合の順序ではどうでしょうか？

こたえ

x = {0, 1}, y = {1, 0} とすると、x < y && y < x となり、ふたつめの条件に反してしまうのでだめ。

二分探索について

名前が二分探索っぽくない

それはそうかも。

ところで、名前が二分探索っぽい bsearch は二分探索であることが特に規定されていません。std::binary_search はさすがに規定されていそう。

さておき、この手のものを求める関数で線形探索をされたらさすがに困るので、二分探索であってほしいという思いはある程度自然だと思います。 「境界が存在する」という仮定*5があるので、線形探索をしたいとはならないでしょう。

ここで、「set のイテレータに対してこれを行うと線形時間かかるから、set の場合は線形探索をしている」と思い込む人もよくいるようです。そうではなくて、（set というかランダムアクセス可能でないイテレータ一般に）イテレータの移動に関してその時間がかかるだけで、比較回数は \(\log_2(n)+O(1)\) 回であり、二分探索をしています。

比較のコストがとても高いクラスを入れたデータ構造で二分探索をしたくて、かつそのデータ構造ではランダムアクセスが高速にできない状況とかを考えると、うれしいかもしれません？ とはいえ、ランダムアクセスイテレータのみに対して提供する関数だった方が、幸福度が高かったような気もします。

set の場合でも対数時間だと思っている人もいますが、そうできない理由と解決策に関しては こちらの記事 で書いています。ざっくり言うと、イテレータだけ渡された関数にとっては、元のコンテナが二分木ベースであることを活かした探索をできないためです。

別の言語の例

C++ では、set から「x 以上の最小値」「x 以下の最大値」を得たいときに

auto it = set.lower_bound(x);
if (it != set.end()) {
    auto ge = *it;
}

とか

auto it = set.upper_bound(x);
if (it != set.begin()) {
    --it;
    auto le = *it;
}

などと書く必要があり、煩雑かつバグらせやすいです。あるいは「x 未満の最大値」などはどうでしょうか？

やりたいことは「x 以下の最大値を得る」などであって、「x と等価な区間の上限が先頭でなければその区間の一つ前にある値を得る」などではないはずです。これは、「0 から n-1 までの値を順に得たい」をしたいのに「i を 0 で初期化して i が n 未満である限り i の値を得て処理してから i をインクリメントする」などをする必要があるのと似ています。

Rust では、以下のように書けます。

if let Some(ge) = set.range(x..).next() {
    // ge は x 以上の最小値
}

if let Some(le) = set.range(..=x).next_back() {
    // le は x 以下の最大値
}

if let Some(lt) = set.range(..x).next_back() {
    // lt は x 未満の最大値
}

「x 以上の区間の最初の値」や「x 以下・未満の区間の最後の値」などという意味合いとして書け、直感的なのではないでしょうか。

if let Some(lt) = set.range(..x).next() と書いてバグらせる人*6もいますが、それは仕方ないですね。

他の言語や他のデータ構造の文脈に関して

Python で「x より大きい・小さい、最小・最大の値は？」のような形式のクエリ（特に学術界隈*7では successor query や predecessor query などと呼ばれることが多い気がします）に答えるデータ構造を実装する際、わざわざ lower_bound などと命名する人がそこそこいる印象がありますが、多くの場合は位置ではなく値を返しているでしょうから、そうした命名がうれしいとは思いにくいです。

シンプルに max_less とか min_greater_equal とか名づける方がわかりやすいのではないでしょうか。

その他の命名例

  • max_less
    • max_lt less lt strict_predecessor predecessor pred pred_exclusive
    • strict の代わりに proper とかもあるかも
    • t は (less) than の t
  • max_less_equal
    • max_le less_equal le predecessor pred_inclusive pred
  • min_greater
    • min_gt greater gt strict_successor successor succ succ_exclusive
  • min_greater_equal
    • min_ge greater_equal ge successor succ_inclusive succ

狭義（= 含まない）と広義（= 含む）のどちらを単に predecessor と呼んで他方を **clusive などと呼ぶかは人によりそうです。

これは横道ですが、x <= y は x is less than or equal to y です。x is less than or equal y と言ってしまう人がそこそこいる印象があります。x is less than or equals y なら valid な感もありそうですが、あまり一般的ではないような気がします。

C++ で何らかの別のデータ構造を実装するときも、競プロ文脈ではイテレータを返したいことは稀でしょうから、わざわざ bound 系の命名に固執する必要はない気がします。

んーでも suffix array に処理させるクエリとかだと区間を返してほしくなることもありそうだから、そういうときは bound なり range なりの名前がうれしいかも？と思いました。

おわり

にゃんにゃこにゃ

すみません、このテーマ以外にも表明したいお気持ちがあるので、たぶん近いうちにまだ書きます。

*1:こういった旨のことを言っている人はたくさん見た気がしていて、特定の人を揶揄する意図はありません。

*2:そういう入力を与えた場合はユーザに責任があるのであって、C++ 側は悪くないという感じ。

*3:競プロ、強い人の真似をしようとしてそういうタイプの混乱をするのがよくありそう。

*4:ユーザに責任があって C++ 側に責任はないということ。口を酸っぱくして言っている。

*5:存在しない場合は妥当な返り値が存在しない上、存在性の判定には計算量を（最悪時）線形にする必要があるのでユーザに責任を押しつけたい。

*6:えびちゃんです。

*7:学術界隈という用語が競プロ界隈語っぽい。アカデミック文脈？みたいな意味合いのつもりです。

「区間更新と言えば遅延セグ木」で思考停止している人向けの記事

指示された「区間更新 + 何かのクエリ」を遅延セグ木で解ける状況で、思考停止で遅延セグ木を貼って AC できる人に対するお気持ち表明ではないです。

「区間更新」の部分だけを見て「どうやら遅延セグ木というので解けるらしいが自分はよく知らない。だから AC できなさそう。ふて寝です」みたいな人向けの記事です。

もしかすると前者の人にも学びのある内容にはなっているかもしれません。

導入

（更新クエリではない方の）値を求めるクエリや、他の更新クエリによって、使うべきデータ構造は変わります。

たとえば、以下のような（ふざけた）問題を考えます。

サイズ $n$ の配列 $a = (0, 0, \dots, 0)$ が与えられる。 以下のクエリをたくさん処理せよ。

  • 1 $l$ $r$ $x$
    • $a_l, a_{l+1}, \dots, a_{r-1}$ の値を $x$ で更新せよ。
  • 2
    • $a_0$ の値を出力せよ。

これであれば、$a_0$ の値さえ管理しておけばよいことがわかります。 ここまでふざけた状況ではなくても、ある状況においては遅延セグ木を使わずに処理できる場合があるので、その紹介です。

いろいろな状況

以下のような問題を考えます。

サイズ $n$ の配列 $a$ が与えられる。 以下のクエリをたくさん処理せよ。

  • 1 $l$ $r$
    • $x = \max\,\{a_l, a_{l+1}, \dots, a_{r-1}\}$ とする。
    • $x$ の値を出力せよ。
    • さらに、$a_l, a_{l+1}, \dots, a_{r-1}$ を $x + 1$ で更新せよ。

これは、一般の「区間更新・区間最大値」よりも限定された状況です。この状況であれば、遅延セグ木なしでも処理することができます。

以下の解説に書いた手法により、BIT や普通のセグ木、あるいは平衡二分探索木（C++ における std::set や std::map）などを用いることで、$\angled{O(n), O(\log(n))}$ (amortized) で処理できます。

atcoder.jp

典型 90 の個別解説、一覧で見れないので若干見つかりにくそう。

あるいは、以下のようなクエリも（簡単な補助のデータ構造を持つことで）同じオーダーの計算量で処理できます。

サイズ $n$ の配列 $a$ が与えられる。 以下のクエリをたくさん処理せよ。

  • 1 $l$ $r$ $x$
    • $a_l, a_{l+1}, \dots, a_{r-1}$ を $x$ で更新せよ。
  • 2 $i$
    • $a_i$ を出力せよ。
  • 3
    • $a$ に含まれる値の種類数、すなわち集合 $\{a_i\mid 0\le i\lt n\}$ の大きさを出力せよ。
  • 4 $x$
    • $a$ に含まれる $x$ の個数、すなわち集合 $\{i \mid a_i = x\}$ の大きさを出力せよ。

特に 3 4 は遅延セグ木で普通に処理するのは難しいと思います。

別のデータ構造

双対セグ木と呼ばれる亜種もあります。区間操作・添字取得をするデータ構造です。

kmyk.github.io

注意

とはいえ、遅延セグ木は避け続けるほど難しいデータ構造ではないはず*1なので、適当なタイミングで学んでしまって、思考停止で貼れる問題は AC できるようにした方が得とも思います。

人によってわかりやすい記事は分かれると思いますが、えびちゃんのお気持ちを追う用の記事は以下です。一番最初に読む用の内容ではないかもしれませんが、他に参考になりそうな記事へのリンクも載っているので紹介します。合わなければ他のブログなどを漁るのもよいでしょう。

rsk0315.hatenablog.com

謝辞

一連の話は、こちらの記事がきっかけで思いついて書く流れになったので、お礼です。

kntychance.hatenablog.jp

おわり

ねこにゃんこ。

*1:初心者のうちに何が何でも勉強するのを強いる意図ではないです。挫折させたいわけではないので。

データ構造の操作に関する動詞

人には人の直感。

データ構造同士をくっつけるとき、なんでも「マージ」と呼んでしまう人がいる気がします。 それはそれでいい気もしますが、どういう性質を持つデータ構造か・どういうくっつけ方かによって適切に感じる動詞は異なる気がします。

マージ以外にも、よくある操作についてニュアンスの違いみたいなのを書きたくなりました。 他の人の直感も知りたいです。

データ構造同士をくっつける操作

型で言うとこんな感じの。

impl<T> Ds<T> {
    fn merge(&mut self, other: Self);
}

merge

一般的・抽象的な感じっぽい。

くっつける操作一般に対して言及したいときは適切な感じがする一方、特定の操作に対して言うにはふわっとしているような気がする。 「データ構造をマージする一般的なテク」などは適切な用例な気がする。

append

「後ろにくっつける」感がある。

可変長配列の末尾に別の配列の要素をくっつけるときに使いそう。

concat

concatenate が正しいかも。

「連結する」感があり、順序としては append と同じそう。文字列感があるかもないかも。

prepend

「前にくっつける」感がある。

append, concat, prepend は、ユーザの決めた順序を保つデータ構造で、順序を指定してくっつける感を感じる。

meld

「融合する」

ヒープ（優先度つきキュー）で使う印象がある。meldable heap 以外の文脈であんまり見ない感。 ユーザが決めた順序ではなく、型で決められた大小関係を管理するので、ユーザからすると順序を意識しない名前がいいのかなあ。 二分木ベースの meldable heap などでは、くっつける際に各要素のポインタが混ざり合う感があるので、融合っぽいニュアンスになるのかなあ。

平衡二分探索木とかみたいに、全部の要素を大小関係で整列するわけではなく、最大値（最小値）だけ管理できるようにしている部分も違うかも？ 順序が入り乱れた平衡二分探索木をくっつけるのは（計算量的にたぶん）難しい気がするから、そういう操作はあんまり見ないかもで、比較しにくいかも。

unite, unify

んーあんまり使ってる人見ないかも？

union-find におけるくっつけ操作用かも。集合（数学）の union (\(\cup)\) だと immutable っぽく見えるので、それに対応する動詞が欲しかった。 Python の set だと、intersection (\(\cap\)) での更新は intersection_update なのに対して、union での更新は update だったのでびっくりした。

splice

「継ぎ合わせる」。

連結リスト (linked list) で、隣り合うポインタを継ぎ接ぎしてくっつける感がある。

insert

「挿入する」。

可変長配列の特定の位置に別の配列を入れる場合など。連結リストのように継ぎ接ぎするわけではなく、押し退けて入れる感が splice との違いかも。概念・実装上の違いで名前が違っていて、インタフェース自体は似ているかも？ 添字を渡すかカーソルを渡すかの違いがある気がするからやっぱり違うかも。

interleave

「綴じ込む」？

データ構造というよりはイテレータ操作で頻出かも。

[a, b, c] と [x, y, z] に対して交互に混ぜて [a, x, b, y, c, z] のようにするイメージ。

extend

まとめて入れる感？

「追加する操作」が一意であるような文脈（可変長配列の末尾に入れる状況や、平衡二分探索木に入れる状況など？）で、その追加操作を繰り返す感？

その他

mix, coalesce, combine, blend, mingle などが類義語らしいものの、あんまり見ない気がする。 coalesce は binomial heap の説明 のときには見た。

connect というのもしっくり来ないかも。

要素を追加する操作

型で言うと以下。

impl<T> Ds<T> {
    fn add(&mut self, elem: T);
}

add

加える。

内部実装や詳細な部分には踏み込まず、単に「追加するよー」感がある気がする。よくも悪くも。

push

入れる？（？）

stack や queue 感があるかも。deque 系だと {front, back} や {left, right} が付加されたりするかも。

enqueue とかもあるかも。

insert

挿入する。

特定の位置に（必要に応じて押し退けて）入れる場合？

可変長配列への insert と、平衡二分探索木への insert をうまく説明できないかも。 後者は push ではだめ？ push は端に押し入れるみたいなイメージがある？（だから不適？）

ユーザが指定した順序・型での大小関係での順序とかは別として、単に間に入れるみたいなイメージ？

ユーザから見て位置が一意なとき（末尾だけとか、型で定まるとか）は push か？と思ったけどそれだと平衡二分探索木は push なんだよね。 ヒープに入れるのが push なのは？ 間に挿入するというよりは、末尾にとりあえず追加して修正 (sift((最初、shift の typo なのかと思ってました。))) するから insert とは違う感ある？

emplace

据え付ける？

C++ 感（？）。in-place に値を構築するみたいな感がある？

その他

配列 [a, b, c, d] があって間に x を混ぜて [a, x, b, x, c, x, d] にする操作は intersperse（点在させる）っぽい。

join は、（文字列の配列をカンマ区切りでくっつけるとかのように）[[T]] と T から [T] を作る感がある。[[a, b], [c], [d, e, f]] と x から [a, b, x, c, x, d, e, f] みたいな。型が違うから immutable に新しいものを作る状況しかないっぽい。

put も push に近い感あるかも？

削除

型だと以下？

impl<T> Ds<T> {
    fn delete(&mut self, elem: &T);
    fn pop(&mut self);
}

delete, erase, remove, discard

消す。

あんまり違いがなくて、どれも「指定した値」「指定した場所」にあるものを消すよー感。

名詞形が deletion, erasure, removal, discard と、どれも作り方が違うの面白くてすき。

pop

取り除く。

stack や queue のように、除くものが一意だと delete とかよりもこちらの印象がある。deque だと {front, back} や {left, right} がつくかも。

dequeue とかも近いかも。stack だと使いにくそう。

queue は「待ち行列に入れる」「自分の番が来る」感のあるイメージだけど、stack を「待ち行列に入れる」「（最後尾の人が）諦めて立ち去る」と見なされることはなさそう。そういう方針で命名しても面白いか？と一瞬思ったけど、自分の番が来ることのない待ち行列に入る状況が不自然すぎて無理だった。

extract

抽出する。

ヒープで最大値（最小値）を抜き出すときに言いそう。実際の実装でこういう命名になることは稀で、抽象データ構造としてのインタフェースを話すときにしか言われない感ある。

その他

destroy, eliminate とかはあんまり言われなさそう。

集合操作だと subtract もあるかも。

take とかもあるかも。これも pop みたいに一意っぽさあるかも。extend の逆みたいに、何個除くみたいなときは .take(n) みたいにしたくなるかも。

検索

impl<T> Ds<T> {
    fn search<K>(&self, key: K) -> Option<T>;
    fn contains<K>(&self, key: K) -> bool;
}

「この要素はある？」とか「これに応じた値が欲しい」とか。

search

調べる。

抽象的っぽい。返り値の型が曖昧な感じがするので、概念の説明とかの文脈で「実装次第で bool を返すか値自体を返すかは文脈に応じてよしなに〜」とかのときには適していそうだけど、実装で見るとうれしくなさそう。

正規表現マッチとかで出てくると、言語ごとに仕様が違って嫌になる系のやつ。

find

探す。

これもややふわっとしていそう？ でも bool を返す感じはしなさそう。

look-up

調べる、探す。

ハッシュテーブル感ある（？）。

contains, has, exists

「含む」「存在する」とか。

bool を返す系のやつ。

あんまりニュアンスの違いはない気がするけど、has は（短いので）スクリプト言語寄り感があったり、exists は（なんとなく）素朴に命名しがちなエンジニアが好みそう感を感じたりするかも。contains が一番安心する（？？）。

関係ないけど、(it.)isFooBar（fooBar であるとき true、でないとき false）みたいな命名で「動詞を先頭に持ってくる」感があるのか、(it.)existsFooBar（fooBar が存在するとき true、しないとき false）みたいな命名を見かけることがややあって、えびちゃん的には違和感がある。それなら (it.)containsFooBar とかのが語順として自然そう。

includes

「含む」。

こっちは、なんとなく、sub-array として含むか？の検索のイメージがあって、[1, 2, 3] includes [1, 2] とか、[1, 2, 3] includes [1, 3] ではないとかっぽさを感じていた。JavaScript では [1, 2, 3] includes 2 とかの意味合いで使われており、そっかーとなった。

その他

ヒープの一番上とかを見るような、見たいものが一意のときは peek とかを使うかも。

consists とかはあんまり見ないかも。is-there (.isThere?(elem)) とかは見たことないけどあってもよさそう。よくないかも。

かなり素朴に命名する人だと .query(elem) みたいにしそう。「クエリ」、検索以外にも「更新クエリ」のように使われたりしてよくわからないがち。「質問」っぽい見た目だから immutable 感あるけど、「（これこれの操作を）していただけますか？」のような要求だったりもしそう。複数種類のクエリがあるとき query って名前はとてもしんどい。

まとめて除く・分ける系の操作

impl<T> Ds<T> {
    fn split<I>(&mut self, position: I) -> Self;
    fn partition(&mut self, pred: impl Fn(&T) -> bool) -> (Self, Self);
}

split

特定の位置の前後で分ける感？ Rust だと split_off となってそう。抽象的感もある気はする。

partition

特定の条件を満たすかどうかで分けるときに使われそう。ある値より大きいかどうかとか、偶数か奇数かとか。

その他

purge とかはあんまり見ない感ある。

特定の条件を満たさない要素を消すのは retain とか。 filter とかもあるけど、フィルタで残すのか消すのかわからなくて怒られそう。イテレータ処理の文脈だとそれは合意が取れてそう。 retain も filter も順序は保たれそう。

remove-if みたいな名前はありそう。

感想

merge 関連は状況に応じていろんな単語があってニュアンスが違うのに対し、add・remove 関連は（一つを出し入れするのは単純だから？）ニュアンスの違いが比較的少なそう？な感じがした。そもそも、データ構造として実装できるような操作がある程度固定されているから、そこまではたくさんの種類の単語が必要になりにくいのかも？と思ったりした。 検索のときは、返り値の型が bool か T かに応じて適切に命名できたらうれしいなと思った。

いろんな動詞を思い通りに使えるとうれしいね。

既存の名前と似た操作ならそれに倣って命名したいけど、既存のものとは違う操作をするときに、既存の語にこだわらずに適切に選べたらもっとうれしい。たとえば、CHT の「与えた \(x\) 座標において、今ある直線たちのうちの最小の \(y\) 座標は？」みたいな操作は、よくあるデータ構造にはないので命名が難しい（.min_at(x) とかにしていた記憶があるけど、改善の余地がありそう）。

おわり

me.meow();

ならし計算量のよくある誤解について

ならし計算量 (amortized complexity) というのがありますが、競プロ初心者層には誤解されがちな概念なので、誤解を解くためのことを書きたくなりました。

以下で「よくある誤解」と称して架空の人物がしゃべりますが、複数回見てきた事例であり、特定個人に対する揶揄等ではありません。えびちゃん自身の事例である場合もあります*1。

多少知っている人へ：ポテンシャル解析などの話を直接はしないので、そういうのは別の記事を見に行ってほしいです。文献の紹介くらいはあります。

導入

データ構造の計算量などで、次のような記述を見かけることがよくあります。

  • vector へのアクセス a[i] は、最悪 \(O(1)\) 時間
  • set での二分探索 a.lower_bound(x) は、最悪 \(O(\log(n))\) 時間

これらは、「一番悪いときでも \(O(1)\) 時間や \(O(\log(n))\) 時間だから安心だな〜」という気持ちで読める人が多そうです。

一方で、次のような記述もよくあります。

  • vector の末尾への追加 a.push_back(x) は、ならし \(O(1)\) 時間
    • 償却 \(O(1)\) 時間という言い方もあり、これらは同じ意味
    • 同様に、ならし計算量を償却計算量とも言う
  • union_find での操作 a.unite(i, j) や a.find(i) は、ならし \(O(\alpha(n))\) 時間

これらは、誤解して「ならしってなに？ やばいときは \(O(1)\) 時間や \(O(\alpha(n))\) 時間にならなくて、知らないうちに TLE になったりしそう？で不安だな〜」という気持ちになる初心者が多い印象があります。

実際には、少なくとも競プロ文脈で言えば、「ならしで \(O(1)\) 時間や \(O(\alpha(n))\) 時間だから安心だな〜」となれるくらいのうれしい保証なので、その説明をします。

説明

お気持ち

データ構造に対して \(n\) 回操作し、\(n\) 回の合計の計算量が \(f(n)\) であったとき、一回あたりの計算量は \(f(n)/n\) と見なせます。 そこで、実際の操作一回一回の計算量は考えず、この \(f(n)/n\) について考えてみることにします。

たとえば \(f(n) = O(n)\) であれば、一回あたり \(O(1)\) 時間ということになります。

これをもう少しちゃんと保証したものが、ならし計算量と呼ばれるものです。

定義（ゆるふわ）

あるデータ構造に対して行える操作（vector に対する push_back とか、stack に対する push・pop とか）を考えます。それらをどういう順番で \(n\) 回処理した場合でも、合計が \(f(n)\) 時間以下になるとします。このとき、それらの操作は「ならし \(O(f(n)/n)\) 時間」であると言います。

たとえば、「union_find に対する操作はならし \(O(\alpha(n))\) 時間」というのは、「union_find に対して \(n\) 回操作をすると \(O(n\cdot \alpha(n))\) 時間」のような意味合いです。

定義（かっちりめ）

データ構造に対する任意の操作列 \( (op_1, op_2, \dots, op_n)\) を考えます（\(op_1\) が .push_back(x) とか、そういう感じです）。 このとき、\(op_i\) (\(1\le i\le n\)) に対して、実際の計算量を \(t(op_i)\) とします。 さらに、\(a(op_i)\) が存在して、各 \(1\le k\le n\) に対して以下が成り立つとします。 \[ \sum_{i=1}^k t(op_i) \le \sum_{i=1}^k a(op_i). \] このとき、\(a(op_i)\) を（\(op_i\) の）ならし計算量と呼びます。

\(t(op_i) \le a(op_i)\) (\(1\le i\le n\)) が成り立つ必要はなく、\(i\) 回目以前の操作の合計さえ抑えられればよいのがミソです。

\(n\) 回の操作全体の計算量が \(\sum_{i=1}^n a(op_i)\) で抑えられるため、たとえば \(op_i\) が「ならし \(O(\log(n))\) 時間」と保証されている操作であれば、全体で \(O(n\log(n))\) 時間とわかったりするわけです。

（補足） この \(a(op_i)\) をうまいこと求めるのが、各問題でならし計算量を求めるために必要なことであり、ならし解析 (amortized analysis) などと呼ばれているものです。解析の具体例だけを見せられると天才に見えますが、典型的な手法がいくつかあります。

やや細かい話

実際には、\(n\) が「操作列の長さ」なのか「その時点のデータ構造のサイズ」なのか「それ以前のデータ構造のサイズの最大値」なのかがぼかして話されたりしがちな気もします。

「空の状態から始めて、操作ごとに増える要素の個数が高々 1 つ」であるような場合には、データ構造のサイズが操作列の長さで上から抑えられるので、問題なさそうな気もします。

そうでない場合は少し気にする必要があるかもしれません。 「サイズ \(n\) で初期化して \(m\) 回操作する」ような場合には、初期化の計算量 \(t(op_0)\) も合わせて考えるかもしれません。 あんまり初期化のことを書いている文献はないかもしれません。

\(\Theta\) とか \(\Omega\) とかの話

ならし計算量の定義だと上からしか抑えてないけど、ならしで \(\Theta\) や \(\Omega\) ってうまく定義されてる？

「ある操作列が存在して」か「任意の操作列に対して」かは文脈にもよりそうだけど、下から抑えれば定義できる？ できそう。

\(O\) 以外を知らない人向け → やや長めの記事

よくある例

可変長配列

vector の .push_back のようなものです。ざっくり以下のようなアルゴリズムです。

  • 初め、長さ \(1\) の領域を確保する
  • 確保した領域に新しく要素を置けるなら置く（\(O(1)\) 時間）
  • 確保した領域が足りなくなったら、長さを倍にしてから置く（領域の長さを \(k\) として \(\Theta(k)\) 時間）

長さ \(n\) にするための計算量は？となり、「\(\Theta(n)\) 時間の操作があって \(n\) 回だから \(\Theta(n^2)\) 時間か...？」とか「\(\Theta(n)\) 時間の操作は \(\floor{\log_2(n)}\) 回起きるから \(\Theta(n\log(n))\) 時間か...？ \(\log\) は定数（）だから一回あたり \(O(1)\) 時間と言われているだけなのか...？」となったりしますが、そうではないです。

長さ \(k\) は毎回固定ではなく \(1 + 2 + 4 + \dots + 2^{\floor{\log_2(n)}}\) のようになっているため、（等比数列の和であることに注意するなどして）全体で \(\Theta(n)\) 時間であることがわかります。

キュー

二つのスタックでキューを作ることができ、two-stack queue などと呼ばれます*2。

下の方にあるスライドにも載っているので、詳細は割愛します。似た方法で deque も作れます*3。

カウンタ

\(0\) から始めて \(n\) まで \(1\) ずつ増やすことを考えます。このとき、各インクリメントに対して、数字が変化する桁はならし \(O(1)\) 個であることが示せます。 なので、変わった桁のみをうまく管理することで、たとえば以下のようなクエリをならし \(O(1)\) 時間で処理できます。

  • 値を \(1\) 増やす
  • 桁和を出力する
    • あるいは桁の二乗和とかを出力する

ゆるふわな話

ならしのイメージの話です。

たとえば、「1 日に使った金額が 100 円を超えちゃいけませんよ」と「1 週間に使った金額が 700 円を超えちゃいけませんよ」という制限を考えます。 後者は「平日は 1 円も使わずに土日に 350 円ずつ使う」といった行動が許されるのに対し、前者ではそうしたことが許されません。

この前者が最悪計算量（各クエリの実際の計算量）に相当し、後者がならし計算量（全体で見たときに一回あたりと見なせる計算量）に相当するつもりです。

より実態に即しているイメージをフォロヮにもらったので書きます。前者は「毎日 100 円ずつあげるけど、使わなかったぶんは没収ね」で、後者は「毎日 100 円ずつあげるから、使っても貯金してもいいよ（借金はだめ、利子はなし）」です。計算量が小さい操作をしたのが貯金を作ったことに相当します。

ならしがうれしい話

ならし計算量が解析の面でうれしい状況としては、

  • 一回一回の解析は難しいが、全体で見れば解析が簡単
  • 重いクエリもあるが、全体で見れば十分軽い

のようなものがあります。それはそれとして、「全体としての計算量さえ保証すればいいときは、ならしだけ保証するように設計する」という方針がうれしいケースもあります。

たとえば、\(n\) 個の操作の計算量が \( (1, 1, \dots, 1, n)\) で合計 \(2n-1\) になっているデータ構造があったとします。 これはならし \(O(1)\) 時間ですが、最悪 \(O(1)\) 時間ではありません（最後の一回が \(n\) になっているので）。

これをなんとか工夫することで \( (10, 10, \dots, 10, 10)\) にできたとします。これは最悪 \(O(1)\) 時間を保証できていますが、合計としては \(10n\) に増えてしまっています。

このとき、定数倍が悪くなっている上、全体のオーダーが改善されているわけでもなく、実装の工夫も必要になってしまい、大変づくしです。

もちろん、最悪計算量を保証するために必ずしも定数倍がハチャメチャに悪化するわけではないので状況によりけりですが、ゆるい制限でいいならそれに応じてうまくやりましょうということです。

ならしだと困る話

競プロだとあんまりないと思います。

たとえば、Web サイトなどで「\(i\) 番目のアクセスに対しては、データ構造に対して処理 \(i\) を行う」という処理があったとします。 このとき、ならし計算量しか保証されていないと、一部のユーザが「めちゃくちゃ時間かかった」というような体験をすることになり、あまりうれしくなさそうです。

競プロでも困る例をフォロヮにもらったので書きます。 「ならし○○時間」の操作を普通にするだけなら問題ないと思いますが、rollback が可能なデータ構造に書き換えようとするときに、元が「ならし」のデータ構造だとつらいことがあります。

先のカウンタの例で言えば、999...9 から（大きい計算量で）1000...0 に更新したあと、rollback をして（大きい計算量で）999...9 に戻り、また（大きい計算量で）1000...0 に更新して、... というのを繰り返すと、毎回大きい計算量がかかるようになりますね。

とはいえ、「ならし○○時間」と保証されているデータ構造を、保証されている通りに使えば問題ないことには変わりない気はします。

ならし計算量あるあるデータ構造

C++/STL にもいろいろありますね。

  • vector の .push_back(x) はならし \(O(1)\) 時間
    • このせいで、vector を内部で使うデータ構造は大抵ならしになりがち
  • set の .erase(it) はならし \(O(1)\) 時間
    • コストを .insert(x) に押しつけることで、.erase(it) の方はならせそう？
    • それはそれとして、赤黒木を平衡させる操作はならし \(O(1)\) 時間
      • どこに挿入・削除するかは、ポインタなどを持っていないと \(O(1)\) で決められないことに注意
      • it はイテレータ

STL ではないものの競プロでよくあるデータ構造にもいろいろあります。

  • union_find の .unite(i, j) や .find(i) は（適切に実装すれば）ならし \(O(\alpha(n))\) 時間
    • 実際には、サイズ \(n\) のそれに \(m\) 回操作すると \(\Theta(n+m\,\alpha(m, n))\) 時間で、\(O(\alpha(n))\) 時間よりも厳しく抑えられる
    • \(\alpha(m, n)\) については → そういう記事
  • foldable_queue の .fold() や .push(x) はならし \(O(1)\) 時間
    • いわゆる SWAG（を勝手にそう呼んでいます）
      • queue への push/pop と、全体のモノイド積 (fold) を処理するデータ構造
      • push と fold は最悪 \(O(1)\) 時間
    • two-stack queue を応用して実装する（ので deque でも可能）
  • decremental_neighbor_query の .less_than(i) や .greater_equal(i) などは、ならし \(O(1)\) 時間
    • \(\{1, 2, \dots, n\}\) で初期化した集合に対し、削除操作と、隣の要素の検索ができる
  • skew_heap の .meld(q) はならし \(O(\log(n))\) 時間
    • ヒープ（優先度つきキュー）二つに対して、それらをくっつけて一つのヒープにする操作を meld と呼ぶ
  • fibonacci_heap の .prioritize(it, k) はならし \(O(1)\) 時間
    • ヒープに対して、ある要素の優先度を高める操作（取り出されやすくする）を prioritize と勝手に呼んでいます
      • 文献によっては decrease_key とか言うかも
    • この操作を \(O(1)\) 時間でできることにより、Dijkstra 法の計算量を \(O(|E|\log(|V|))\) から \(O(|E|+|V|\log(|V|))\) に改善できる

まとめ

ならし計算量は、操作列を全体として見たときの計算量を保証してくれるため、競プロ文脈では「最悪○○時間」と同程度にえらい保証と見なしてよいです。 「入力によっては○○時間になってくれず TLE（平均計算量）」とか「乱数の値によっては○○時間になってくれず TLE（期待計算量）」とかとは事情が異なります。

参考文献

  • cs166.1266
    • 図とかがたのしい感じの講義スライド
    • 他にもいろいろなトピックがある
  • 熨斗袋の記事
    • ならし以外にも、期待計算量や平均計算量についても載っている

おわり

にゃんこ。

*1:そういう意味では特定個人ですが、自分なので許されます。

*2:文法としては、two-week vacation とかのように、ハイフンで数詞とつないで名詞が単数形になる形容詞のやつです。two-stacks queue や two-stack-queue ではないです。

*3:概要：片方が空になったときに \(k\) 個移すのではなく \(\ceil{k/2}\) 個移します。

素数の数え上げのスライドについて

最近スライドを公開しました：

動機について

やや前に Beamer でスライドを作る機会があったのと、最近 LuaLaTeX を触ってみたというのがあって、LuaLaTeX + Beamer でスライドを書きたいなという欲がありました。

素数の数え上げや乗法的関数の和は、一部界隈では知られていそうだったものの、あまり浸透していない印象があったので勉強したいと思っていました。 そこで、それをスライドに書くことで一石たくさん鳥にしようと思いました。文字ベースの記事だと説明がごちゃつきそうに感じたというのもあります*1。

スライドに関して

スライドのこだわりポイントや、作っていてうれしかった点などをぽんぽん挙げていきます（淡々と空行区切りで書いたところ思ったより読みにくくなった感があります）。

暗めの赤と青の配色は、大学時代に学生たちから畏れられていた教授がよく使っていたテーマを真似して作ったものです*2。

Beamer に詳しい人は知っているかもしれませんが、スライドの以下のような部分がリンクになっていて、ページ遷移が容易なのがうれしいです。

  • ヘッダ部にあるセクション名
  • ヘッダ部にある〇
  • フッタ部左側のタイトル

同じトピックのスライドに関して、タイトルに「I, II, III, IV, ...」と振っている箇所が複数ありますが、これはそういう制御綴を置いておくことで自動で採番してくれるのでうれしいです。

\newcounter{slidetopic}
\renewcommand{\theslidetopic}{\stepcounter{slidetopic}\Roman{slidetopic}}

\setcounter{slidetopic}{0}
\begin{frame}
  \frametitle{タイトル \slidetopic}  % タイトル I
\end{frame}
\begin{frame}
  \frametitle{タイトル \slidetopic}  % タイトル II
\end{frame}
% ...

右下にあるページ番号も（当然）自動採番ですが、\appendix と書いた後は appendix 用のものと切り替えられるらしいのを知ってうれしくなりました。

\addtobeamertemplate{navigation symbols}{}{%
  \usebeamerfont{footline}%
  \usebeamercolor[fg]{footline}%
  \hspace{1em}%
  \makeatletter%
  \ifbeamer@inappendix{%
    \textsc{appendix} {\insertframenumberinappendix} / {\insertappendixframenumber}%
  }\else{%
    {\insertframenumber} / {\insertmainframenumber}%
  }\fi%
  \makeatother%
  \hspace{0.8em}%
}

小文字の appendix だと配置が崩れたので small caps を使いました。

\(+=\) ではなく \(\xleftarrow{+}\) と書くのは、\(\gets\) で代入を意味する擬似コードではいい感じの見栄えなんじゃないかなぁと自画自讃しています。 そこはいいと思うんですが、「記法について」のスライドがちょっと突飛かもと思いました。「記法と言えば prelim で、prelim と言えば最初でしょ」みたいなノリだったと思います。

木の部分は気に入っていて、TikZ はえらいなあと思いました。

\usetikzlibrary{
  graphs,
  graphdrawing,
}
\usegdlibrary{trees}

% ... in {tikzpicture}
\graph[tree layout, sibling sep=0pt]{
  1 -> {
    2 -> {
      4 -> {
        8 -> 16,
        12,
        20
      },
      6 -> 18,
      10,
      14
    },
    3 -> {
      9,
      15
    },
    5,
    7,
    e/...,
    19
  }
};

辺ラベルは、白い太文字を書いた上に黒文字をかぶせることで実現しています。

\usepackage{pdfrender}
\newcommand{\tpr}[1]{%
  \textpdfrender{
    TextRenderingMode=FillStrokeClip,
    LineWidth=3pt,
    FillColor=black,
    StrokeColor=white,
    MiterLimit=1
  }{#1}%
}

% ... in {tikzpicture}
\begin{scope}[every node/.style={font=\tiny}]
  \path
  (1) -- node {\tpr{2}} (2)
  (1) -- node {2} (2)
  (1) -- node {\tpr{3}} (3)
  (1) -- node {3} (3)
  % 各辺に対して同じようなことを書いた。Lua を使えばもっと楽にできたと思う。
  ;
\end{scope}

この構成方法（自身を最小素因数で割ったものが親になる）で作られた木に名前がついていないのか気になります。ないのかなあ。

冒頭の篩や付録ページの DP の差分スライドたちは Lua で実際に DP しながら値を計算して、その結果を出力しています*3。 こういうのが柔軟にできるのはうれしいなあという気持ちになります。Lua なのがうれしいかというと怪しいですが、十分ありがたいですね。

付録スライドに載せるようなコンテンツ（擬似コードなど）は、発表後にゆっくり読んでもらう側面が強いと思ったので、付録の擬似コードはめちゃくちゃに縮小してみました。 最初は、

function lucy()
|  foo
|  bar
+ ...
function lucy()
| ...
| baz
| qux
+ ...
function lucy()
| ...
| quux
| corge
+---

などのように分割することも考えたのですが、シンプルに読みにくいし書くのも大変だなとなってやめました。 スライドを PNG などの画像に変換して読んでいる人がいたらかわいそうなことになりますが、まぁいいかなと思いました。

改行位置には結構気をつけたつもりです。

おまけスライドにちょっとした問題を追記したのですが、「読者への課題です」と言って説明を放棄して迷宮入りするのは好ましくないと思ったので、文字を逆向きにしてちょっと読みにくくして載せる手法を使いました。小さい子向けのなぞなぞの本とかでこういうのがあったような気がしていますが、参考書とかではあまり見ないような気がします。 えびちゃんのセグ木スライドでも同様の手法を使った気がします。

スライドを更新した際に（スライドの TeX ファイルなどは private repository で管理しているのですが）commit hash をつけておくと何らかの捗りがある気がしたので、更新日時とともに載せてみました。LuaLaTeX で比較的簡単に実現できたのでうれしかったです。

ねこねこ勉強ぱーてぃというのは架空の勉強会の名前です。とりあえず仮置きで名前をつけていたところ、考え直すのを忘れて投げてしまいました。

承認欲求の満たされについて

うれしい。競プロ界隈でスライドを作っている人が少ししかいないかもという気持ちも少しあります。と見せかけてそんなことないかも？

うれしい。書いてみた甲斐があります。

その他

実験コードを書いて、計測をした後、「念のため擬似コードにしておくか」と思ってコードを読んでいたところ、実装に誤りに気づいてつらくなりました。\(p_{\pi} \gt n^{1/6}\) で判定するところを \(\pi \gt n^{1/6}\) と書いていました。たぶん log 倍悪くなっていそうですが、修正したらちゃんと速くなってくれたのでうれしかったです。

擬似コードで書く利点ってなんなんでしょう。Rust のコードをそのまま貼る方がうれしいかもとも思ったりはしました。 \(\text{\textbf{foreach }}v \in S\) とか \(x \xleftarrow{+} \sum_i f(i)\) のように数式混じりの表現をそのまま使っても違和感がなさげなのがちょっとうれしいかもと思ったりはしました*4。 特定の言語依存の表現だと、たとえば log(x, y) と書いたときどちらが底なのかわかりにくいとか、そういう嫌な点があるかなとも思いました。

どの言語にも依存していないが、どの言語に移植するにも手間がかかってしまうというのはありますね*5。

擬似コードでオブジェクト指向っぽく \(v.\text{push}(x)\) とか書くのが邪道なんじゃないかと思ったりしつつ、どう書くべきかわからなかったりしました。

あと \(\text{\textbf{for each}}\) のように 2 語にする方が気持ちいいんじゃないかという気持ちもあります。どうしよう。

\(\Theta(n^{2/3})\) の方は \(\Theta(n^{3/4}/\log(n))\) のものよりも定数倍が重くてしんどいかもという先入観があったのですが、意外と勝っていてうれしかったです。\(\Theta(n^{2/3}/\log(n)^{1/3})\) の方も速くてご満悦です。

最初は乗法的関数の \(\Theta(n^{2/3})\) の方は難しいと思ったので 2 回シリーズにしようかと思ったのですが、分かれちゃうのもアレかと思って、詰め込んでしまいました。

きもち

AtCoder でこの手のアルゴリズムが出題されるされないとかそういうのは抜きにして話します。 内容自体はそこまでレートが高くなくても読める内容だと思うので、読んでみてもらえるとうれしいかもしれないと思いつつ、書いた後だからそう思うだけで難しいのかもと思ったり、ぐるぐるしています*6。

参考にしていたブログは最初は行間たっぷりに見えていたのですが、今では簡単に見えてしまったりしているので、えびちゃんの目はあてにならないです。

省略する。

とブログで書かれていた部分も、今では「そりゃ省略したくもなるよなぁ」と思ってしまうまであります。

なつかし

floor sum の解説記事を書いたときや、ACL math の解説記事を書いたときにあれこれ調べたのを思い出しました。数学のことを調べるのはやっぱりすきなんだろうなぁと思ったりしました。

おわり

おわりにゃ。次はなにの勉強会をしようかにゃぁ。

*1:実際、前に書いた記事はそういう感じになった気がします。

*2:Thank you! スライドも同様です。

*3:SATySFi でもそういうことができそうな感はありますね。

*4:下手に書くと計算量のごまかしや行間になりそうですが、それについてはスライド中で説明をしているつもりです。

*5:擬似コードってラテン語っぽい雰囲気があったりするでしょうか。

*6:あまり難しくないですよーと言って読んでもらおうとするのは、読めなかったときに落ち込んでしまいがちなので、あまりよくない気がしています。