アルゴリズムと数学的思考力 - 怠惰を求めて勤勉に行き着く

厳しい。年始早々厳しさを感じている。自分のプログラミング力にだ。伸び悩んでいる。 端的に言って、数学力のなさが自分のプログラミング能力に制限をかけている。例えばこの問題。 560. Subarray Sum Equals K 入力として与えられる配列 nums のうち、合計が k となる部分配列の個数を数え上げよ。どうも有名な問題らしいが… まず大前提として、部分配列なので i, j の2重ループで始点・終点を定めて sum(nums[i, j]) = k になるものを数え上げれば必ず答えが得られる。最悪計算量は O(N^3) ただし i < nums.length < 20000 という制約があるので N^3 では遅すぎるから何か考えてくださいというのがスタート地点。 ここで、結果の変わらない累積和を何度も求めているので nums[i, j] = k を求めたい場合、 nums[0, j

[cocoasynn]

この手の問題は数こなしてパターンを記憶することと新しい問題を自分で分解して既知のパターンに落とし込むことが大事だと思う。受験数学に近い。

[wyukawa]

個人的にはこれは数学力でも算数力でもないと思っててあえて言うならアルゴリズム力なのかなと。

[bohemian916]

多くの現場ではレビューで「どうやって実装してるか他の人が分からなくて、バグがあったら管理できないからシンプルな実装にして」と言われて却下されそう。ほとんどの場合は速度<可読性だしなぁ。

[soratokimitonoaidani]

剰余環の逆元とか二項係数の性質とかなら数学だけど、これは数学ではなさそう……アルゴリズムを知っててうまく活用できますか？という論点だと思う。

[blackapple]

お前の限界だから諦めたら？？

[stracciatella]

アルゴリズムはカナデなりマネカーなり名前つく程度に研究対象であるので、数学的センスがないからアルゴリズムができないと思うのは短絡的で、まずは先人の知恵を叩き込む通常の意味での勉強が必要だと競プロで思う

[oktnzm]

"seen.put(0, 1) の部分だけトリッキー" パッと見た感じ単に自明な解を追加してるだけに見えるが(空の部分配列の場合)／目指す所がよくわからんがマセマの微積やってるレベルならまずはそっちを全力で終わらせるべきかと…

[altar]

「部分配列」は問題文原文だとcontinuous subarrayで、予め原文に目を通している層が想定読者なら問題ないけどこの記事だけ読んでも連続と解釈することはできない。

[m_ogawa]

分かりみ。引き出しの多さと引き出すクセ(コツ)の暗記がキモだと思う。まさに受験数学がそうだった。青本赤本を解くほどに偏屈な過去問がなぜか解けるようになるやつ。でも時間が経つと失われる。

[oinume]

自分も数学苦手なのでめちゃわかる

[youko03]

プログラミング能力を数学的思考力に直結させてCSの体系的な学習が必要という考えに至るのは短絡的と感じる

[ttrr]

たとえば優先度付きキューの使い方を知っているのと知らないのとでは解法に至る難易度が違うと思うし、総合力あげたら自然にレートアップしてくんでは。

[take4mats]

まさしく同じように、競技プログラミング系の問題を解いて感じたポイント。一度は学んだ（と信じたい）けどかなり化石化している部分。ある程度の概念はすぐ引き出せるようにしておきたい。

[satmat]

これは似たようなことを過去、受験なり大学の授業なり最近数検準1級を受けたときに思った。一番勉強に時間使える時期で出来なかったものは無理なので数こなしても無理なものは無理と半ば諦めている…

[y_r]

どっちも AtCoder でいえば 500-600 点問題で結構難しい。 / 自分の実力よりも大幅に難しい問題を解こうとしても絶望しかないのだから精進対象は https://kenkoooo.com/atcoder/#/table/ で選定するのがよい

[uunfo]

560はその事実からそのソースコード（アルゴリズム）に至るところにも壁がありそうな。373の方は自分で実際に数えようとしたら自然と閃くのでは？具体的にやってみるのは大事。

[hackpopo]

30を超えたら何を学び経験するのかよりも、何を諦めるのかの方が重要になってくるよな。

[capriccio-bwv-993]

単純にn個の配列の組合せの総和を考えると2^nなので、総当たりでいくとすぐに演算が爆発しそうな感じがする。凡人なので良いアルゴリズムを思いつかなかい (´・ω・｀)

[fai_fx]

苦手な部分だけ他人に考えてもらって、それを上手く利用するだけでもどうにかなる…

[razokulover]

わかる。計算力じゃなくて数学力(=抽象的な思考力)かな。教科書の証明を飛ばしてしまうタイプの人はこれで悩む気がする。

[fa11enprince]

なんか複雑な中学受験問題とかにありそうな問題の印象を受けるのでとてもこの方の印象はわかる気がする。私も苦手。。。

[nakag0711]

プログラミング力と呼ぶべきものがあるとしたら、例えば解法を再利用やテストが可能な単位に分割できているかではないか

[samu_i]

諦めて他の分野に特化(楽しければ続ける

[aya_momo]

完全に慣れだね。簡単。ヒープに突っ込む順番でもっと複雑な場合もある。これは一番単純。/↑自分も最初2^nだと思ったけど、「部分範囲」の解釈を間違えていた。