えびちゃんの日記

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

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

「初心者が貪欲法を覚えて、全てそれで解こうとしている」のかな？と思い込んでいたのですが、そうではないような気がしてきました。 諸々のコーナーケース（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:かわいそう。