メモ

yukicoderでゆるふわgolf

yukicoder 1962の解説の解説

テクニック

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。

FPSパワーを感じる学びがあったのでまとめる。出典

「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は \displaystyle f_i(x):=\sum_{jはiの倍数でない}x^j になる。
したがって、「全ての要素が等しく、条件を満たすような長さ N の数列の個数」の母関数は g(x):=\sum_{i} f_i(x) であり、もとの条件を満たすような数列は、このような形の数列を任意個連結したものとして表すことができるので（？）、個数の母関数は \sum_k g(x)^k=\frac{1}{1-g(x)} となる……？
……というのは嘘。これだと例えば (2,2,2) と (2,2,2) を連結して (2,2,2,2,2,2) が作れてしまう。

こういうことが起きる原因は、「全ての要素が i であり、条件を満たすような長さNの数列」のなす集合が連結で閉じていないせい。なので閉じるようにしよう（！）

一般に、あるオブジェクトであって重みNのものの個数の母関数が f であるとき、 \sum_{k\geq 1}f^k=\frac{f}{1-f} は、「オブジェクトを1個以上並べた列であって、重みの和がNになるものの個数」の母関数になる。この概念を悪用する。
あるオブジェクトであって重みNのものの個数の母関数が f であるとき、f=\frac{F}{1-F} を満たす F は「"それ"を1個以上並べることでオブジェクトを生成する何か」であって重みNのものの個数の母関数になる（？？？）
よって、fのかわりにFで考えることで任意個の連結について閉じるので、あとは前半で述べたのと同じようにして問題が解けた。

正当性はいい感じにやると示せるらしいけど（参考）、もとのオブジェクトを形式的に謎の概念に分解するという考え方はヤバさがあって好き。

この問題は「1のみからなる数列であって条件を満たすもの」「2のみからなる数列であって条件を満たすもの」「3のみからなる数列であって条件を満たすもの」……を同じものが連続しないように並べたいということなので、「"同じもの"が連続しない」という条件をFPSで形式的に処理することができるようになった。すげー

練習のためにいくつか問題を解いてみよう

類題
1以上M以下の整数からなる数列であって、同じ値が連続せず、和がNになるようなものはいくつあるか？
例：(N,M)=(4,3)のとき、(1,2,1),(1,3),(3,1)の3通り

「1」「2」「3」……を同じものが連続しないように並べたいということなので f_i(x)=x^i、F_i=\frac{f_i}{1+f_i}、G=\sum_i F_iとして、\frac{1}{1-G}が母関数

M=3の母関数　w|a


類題２
1以上M以下の整数からなる数列であって、mod Pが等しい値が連続せず、長さがNの数列はいくつ？
例：(N,M,P)=(3,4,3)のとき、(1or4,2,1or3or4),(1or4,3,1or2or4),(2or3,1or4,2or3),(2,3,1or2or4),(3,2,1or3or4)の26通り

1以上M以下の整数であってmod Pでiになるものの個数をC_iとする。「mod Pで1の数」「mod Pで2の数」「mod Pで3の数」……を同じものが連続しないように並べたいということなのでf_i(x)=C_i x、F_i=\frac{f_i}{1+f_i}、G=\sum_i F_iとして、\frac{1}{1-G}が母関数

(M,P)=(4,3)の母関数　w|a

ABC249Ex解説の解説

公式解説の読解に5000兆年かかったので、記号や論理の展開の仕方を全て俺好みに書き換えたものを記す。
オリジナル：Editorial - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）


数列 A に対して、終了条件を満たすまでの操作回数の期待値を E(A) とおく。
数列 A が1回の操作で数列 A' に変化する確率を P(A,A') とおく。
数列 A と整数 v に対して、f(A,v)=|\{i \mid A_i=v\}| とおく。
もし ある関数 E':\mathbb{N}\to\mathbb{R} と定数 C であって、
★ \sum_{v=1}^{N}E'(f(A,v))=E(A)+C
を満たすものが存在し、E',C を求めることができれば元の問題には答えられる。（f(A,v) を全ての v について求めるのは O(N) でできるので）

・そもそもそんな E' は存在するのか
E' が満たすべき必要十分条件を考える。
E は定義から、関数等式 E(A)=1+\sum_{A'} P(A,A')E(A') を満たす。
逆にこの性質を持つ関数 g であって、終了条件を満たす全ての A で g(A)=0 を満たすならば g=E である。
この関数等式に E',f と E の関係式★をぶち込むと
\begin{eqnarray*} -C+\sum_{v=1}^{N}E'(f(A,v))&=&E(A)\\ &=&1+\sum_{A'} P(A,A')E(A')\\ &=&1+\sum_{A'} P(A,A')(-C+\sum_{v=1}^{N}E'(f(A',v))) \end{eqnarray*}
となり、整理することで
① 任意の A で \sum_{v=1}^{N}E'(f(A,v))=1+\sum_{A'} P(A,A')\sum_{v=1}^{N}E'(f(A',v))
という、E' が満たすべき関数等式を得る。さらに境界条件 「A が終了条件を満たすならば g(A)=0」から、C は C=E'(N)+(N-1)E'(0) を満たすよう取れば良い。
よって①を満たすことが必要十分。
この条件をさらに厳しくし、
①' 任意の A,v で E'(f(A,v))=\frac{1}{N}+\sum_{A'} P(A,A')E'(f(A',v))
を満たすものについて考えることにする。

ここで、\sum_{A'} P(A,A')E'(f(A',v)) を \sum_{y}E'(y)\sum_{f(A',v)=y} P(A,A') と書き換える。
\sum_{f(A',v)=y} P(A,A')、すなわち「A に対して1回操作を行った数列を A'とするとき、f(A',v)=y となる確率」は、操作を具体的に考察することで(←adhocポイント) f(A,v) のみに依存していることがわかるため、Q(f(A,v),y) と書ける。したがって①'は
①'' 任意の x で E'(x)=\frac{1}{N}+\sum_{y}E'(y)Q(x,y)
に置き換えられる。両辺 N 倍することで、E' は明らかに、ある吸収マルコフ連鎖における各状態から終端状態に到るまでのステップ数の期待値を表す関数として実現可能であることがわかる。以上により存在が示せた。

・E' を計算できるか
実際にE' を吸収マルコフ連鎖の期待値の関数だと思って計算したい気持ちになるので、やってみる。
全ての Q(x,y) がわかっているとする。
遷移行列をごちゃごちゃ計算すると O(N^3) で解けるがそれでは間に合わない。
操作を具体的に考察することで(←adhocポイント)、k>1 のとき Q(x,x+k)=0 となることがわかるので、遷移行列はほぼ三角行列になっている。
①''をぐっと睨むと E' に定数足したものも E' が満たすべき関数等式①''を満たすので、E'(0)の値を適当に決め打ちしてから、小さい方から順に求めていくことで O(N^2) で求められることがわかる。

・Q を計算できるか
できます。頑張れ

Project Euler 201-250 解説

これの続き
sugarknri.hatenablog.com

201
DP

202
前座パートは中受典型
No.306 さいたま2008 - yukicoder
本編前半は3種類の直線をZ[ω]座標系で書いて考える
本編後半は素因数分解してDPなり包除原理なり

203
やるだけ
クンマーの定理を思い出してもいい

204
O(N^(3/4))で素数を求めるDPの逆　O(√N)
普通にDFS/BFSで全探索してもいい　O(ans)

205
さんすう
DPするまでもなく全探索が許される制約

206
自明な枝刈りだけで残りは10^7通りです
下から2桁ずつ決めるのが早い

207
センター数学とかでよくみる
電卓ありなら楽々手で解ける

208
前半パート：
向いている方向は5種類なので、移動量のベクトルは10種類。これらの登場回数が満たすべき条件は？
後半パート：
適当にDPすると解ける
実はO(N)解法もある。前半パートで求めた条件を1つ固定して、向いている方向を頂点、移動を辺としたグラフを考えると、オイラー路の数え上げになる
BEST theorem - Wikipedia
Kirchhoff's theorem - Wikipedia
BEST theoremの証明はこれを読ん……でません……
https://pure.tue.nl/ws/portalfiles/portal/3311129/597493.pdf
類題：
No.310 2文字しりとり - yukicoder
D - C4

209
問題文の条件を τ(x) and τ(f(x)) = 0と書いて、(x,f(x))の64頂点グラフを考える
類題？ F - Cards

210
図を書く
適当にやってO(N)
格子点テクでO(N^(2/3))になる

211
やるだけO(NlogN)
素数ごとに計算しておいて平方数になる組合せを探すのでも解けるらしいが計算量はわからん

212
2次元の問題をO( (N+X)logX)で解く方法知ってる？
それを10^4回やれば O(X(N+X)logX)
wikipediaによるとO(N^1.5)の解法が存在しているらしい
Klee's measure problem - Wikipedia
dx,dy,dzが小さいことを使って、平面走査ならぬ空間走査でO(XΣdydz)でも間に合う
適当に空間を分割して、関係者が少なくなったら包除とかでも解けるらしい

213
期待値の線形性・独立な確率変数の積の期待値

214
O(NlogN)
φ^k(N)=1になる最小のkはθ(logN)

215
DP
縦に見ても横に見ても

216
131で見た
二次式の篩 O(NlogN)
ミラーラビンとかで雑に殴ってもいい

217
桁DP O(BN^2)

218
ギャグ
原始ピタゴラス数の生成式をぐっと睨む

219
N要素の最適な集合からN+1要素の最適な集合が構成できることを証明しましたか？
あとは適当にやるとできます O(logN)くらい

220
ドラゴン曲線 - Wikipedia
再帰構造がありそうな雰囲気があるのでぐっと睨む

221
適当に式変形すると約数を求める問題っぽくなるので、小さいところで適当に探索を打ち切ればAC
ところで、小さいところで適当に探索を打ち切っていいことの証明をできますか？（私はできません&掲示板にも誰も書いてなさそう）
ちなみに、ad-bc=1を満たす4整数abcdでparametrizeされるのでStern-Brocot treeを使ってO(NlogN)で解けます（は？）

222
2次元の問題になるのでbitDP O(2^N N^2)
ちなみに、2-optでswapした方が得になるケースを考えると最適な順序がただちにわかります（！）

223
式変形すると積=積の形になるので約数を求める
素因数分解するんじゃなく(xy)(zw)=(xz)(yw)とparametrizeするとxy-zw=2を満たす4整数xyzwが出てくるのでStern-Brocot treeを使っても解けるっぽい？（未確認）
ちなみに、ピタゴラス数の生成行列はa^2+b^2-c^2を保っているので、この問題もこれを使って解けます（！）
再掲：Pythagorean Triple -- from Wolfram MathWorld

224
223と同じ式変形をして、2次式の篩
生成行列を使う解法だと223と全く同様に解ける

225
愚直
計算量はよくわからない　自明な上界はO(ans^4)だが……

226
積分と無限和の順序を交換
普通に区分求積法でやっても精度足りるらしい

227
O(N)状態になので収束するまで適当にDP
Absorbing Markov Chainなので、手計算で解けるらしい
Absorbing Markov chain - Wikipedia

228
辺の傾きをぐっと睨む
適当にやるとO~(R(R-L))だが包除するとO(RlogR)になる

229
1つ目の条件だけなら当然解けますよね
二個の平方数の和 - Wikipedia
ほかも、対応する2次体の類数が1なので、平方剰余に関する自明な条件を満たせばOK
5が入ってなくて優しいね
二次体 Q(√-5) のイデアル類群と xx + 5yy 型の二次形式 - tsujimotterのノートブック

230
再帰構造があるので云々するやつ
類題：D - Christmas

231
素数ごとに個数数えるだけ　O(NloglogN)
√Nより大きいところはprime sumなので、トータルでO(N^(3/4))になる

232
確率DP　O(N^2logN)

233
229で見た
証明はZ[i]の素因数分解

234
区間(p^2,q^2)で包除

235
s(n)のclosed-formが手計算で出せるので二分探索

236
無意味な水増しを取り除くと、7変数に条件式が4本あるので、3変数全探索すると解ける
面倒なら4変数全探索しても間に合う

237
O(logN)
類題：No.541 3 x N グリッド上のサイクルの個数 - yukicoder

238
周期性
zを固定して探したくなるけど、kを固定した方が早い
なぜならwは乱数列なので、sum(w[:i])>=kとなるiを取ると[0,i)の十分近くに和がkになる区間がありそうなので

239
包除原理

240
挿入DP
D面ダイスN個の上位T個の和をSにする方法の個数を求めるのに O(NNDS)

241
「次に使う素数」を順番に決めるのは難しいが、分子の因数から適当に選んでDFSすると解ける
実はσ(n)/nにはかなり強いupper boundがあり、それを超えるような分子の素因数は全部約分される必要があることを使うとさらに早くなる

242
f(n,k)をn,kの式で書いて、Lucasの定理を使ったり二項係数の畳み込み和を計算したりして式変形する

243
69とほぼ同じだが、n/(n-1)がついているので……

244
最短経路問題

245
最後の1個の素因数をいい感じに決めるやつ
計算量はわからない

246
ひたすら数学をすると比較的簡単な式になる

247
プラキューでO(ans log ans)
最初にサイズを求めておいてそれより大きいものを列挙すればO(ans+hoge)

248
nの素因数の候補は少ないので全探索

249
DP
O(N^3/(logN)^2)くらい？
mod998ならlog,expでO(N^2)くらい

250
DP
周期性を使うと計算量が落ちる

続き
sugarknri.hatenablog.com

Project Euler 151-200 解説

f:id:sugarknri:20220401163514p:plain

これの続き
sugarknri.hatenablog.com

「DPの状態数が少ないので行列累乗や高速きたまさ法で計算量落ちまーす」の類は実りがないので以降言及しません。

151
DP

152
1/kpを使ったら、pがどこかで約分される必要があります
バックトラックDFSで全探索
指数でも分けたらもっと早くなるらしい

153
主客転倒でO(N)
計算式をよく見ると、totient sumのようにgcdで除原理をするやつ＋Dilichlet convolutionでできるのでO(N^(3/4))
さらに、除原理する前のパートの計算を、上は格子点数え上げ、下は愚直でO(N^(2/3))にできるので全体でO~(N^(2/3))
格子点の数え上げの高速化 - memo

154
雑にやるとO(N^2logN)とかだが早い言語なら間に合う
以下の記事の真ん中らへんに書いてある「補題」を念頭に、5進digitsumで分類しておくと定数倍の小さいO(N^2)になる
クンマーの定理とその証明 | 高校数学の美しい物語

155
n=k+(n-k)です
分母が小さいことが帰納的に示せるので、setではなく表で持つとlogがおちて数十倍早くなる

156
2000未満に1は1600回登場して、2000～2999に1は300回しか登場しないので、2000≦n≦2999の範囲にf(n,1)=nの解は存在しません
そんな感じで間を飛ばすと間に合う

157
108でやった

158
手で解けます
No.411 昇順昇順ソート - yukicoder

159
DP O(NlogN)

160
n!/5^k mod 5^5みたいなのを求めたいですね。5の倍数だけ避けて再帰的に計算すればよい
ウィルソンの定理を使うと手抜きができる部分もある
類題は592
こういうのもある。この問題でここまでする必要はないが……
二項係数 mod Prime Power - memo

161
DP O(6*4^NNM)
F - Hanjo 2

162
包除原理　手で解け

163
Nが小さいので多項式時間なら何やっても許される
2点選んで全探索するのが一番簡単そう
O(1)でも解けるらしい

164
DP

165
幾何

166
条件式がrank8なので、8つ決めれば一意

167
もしこの問題に対する証明を自力で与えることができたなら、あと30年早く生まれていれば論文になりました。おめでとう
問題を解くだけであれば、実験してエスパーするか、wikipediaに書いてある本質情報を使う。
証明を理解したいのであれば、[1]のtheorem1と[2]のtheorem2を組み合わせると、LFSRに帰着されることからわかります（！？）
[1] https://core.ac.uk/download/pdf/82710604.pdf The Regularity of Some 1-Additive Sequences, JAMES SCHMERL AND EUGENE SPIEGEL
[2] https://www.mathstat.dal.ca/FQ/Scanned/29-3/finch.pdf CONJECTURES ABOUT s-ADDITIVE SEQUENCES, Steven R. Finch

168
誰でも一度は考えたことがあるはず
10N+dとおいてやるだけ

169
ド典型 O(logN)
D - Number of Multisets

170
どっちを全探索するか迷うところだが、少し考えると乗数の候補がかなり絞れることがわかる

171
DP O(B^3(logN)^2)
mod998244353ならFPSのlog,expで O~(B^2logN)

172
DP O(B^3logN)
EGFを考えても解ける

173
2変数で条件式が1本あるので、全探索 O(√N)

174
173で出した式をそのまま使う O(NlogN)
自明な改良をするとO(N)になる

175
169で作った漸化式を思い出して、同じように漸化式を作る

176
因数分解するだけ
偶数のときはparityが壊れないよう気をつける必要があるという細かい罠がある

177
幾何
全探索するだけ
回転一致・対称一致に注意

178
DP
部分集合やminmaxを持ちたくなるが、そこまでは必要はないのでO(BlogN)

179
やるだけ O(NlogN)
線形篩でO(N)

180
ギャグ
式変形する

181
DP O(B^2 W^2)
適当な順にソート

182
乗法群(Z/nZ)^*の構造を知っていますか

183
連続緩和(?)

184
偏角ソート＋2点決め打ちでO(r^4)
その時の和がどういう形になっているかよく見るとO(r^2)
gcdを引いていくいつものやつでsublinearにもなるらしいです。こわい

185
現代の計算機は早いので適当に探索してもわりと間に合う
整数計画問題だと思ってそのへんのIP solverに投げてもいい

186
UF

187
そのまま篩ってO(NlogN)
いつもの素数カウントのやつでO(N^(3/4)/logN)とかにもなる

188
Library Checker

189
遷移がだるいDP

190
ラグランジュの未定乗数法を使うな
AM-GM典型だぞ

191
DP

192
連分数
計算量は悪いがStern-Brocot treeで愚直にやっても間に合うらしい
何ステップ連続するか求めて間を飛ばせば同じ計算量になるが、精度に不安あり

193
ディリクレ級数を考えるとO(N^(2/3))
Dirichlet 積と、数論関数の累積和 | maspyのHP
メビウス関数の性質を使うとO(N^(1/2))
https://twitter.com/37zigen/status/1460288422015242241
さらに商でまとめるテクでO(N^(2/5))
[1107.4890] Counting Square-Free Numbers

194
DPをしようとすると本質に気づきDPはいらないことがわかる
え？何が本質かわからない？しょうがないにゃあ
https://kokiymgch.hatenablog.com/entry/2018/01/27/235959

195
60度の三角形の生成式は143で見た
生成パラメータの探索範囲は初等幾何で示せばO(NlogN)
いつものようにO(N^(2/3))になるらしい。2変数でもできるんだ……

196
区間篩

197
これは実験＋エスパー以外の解き筋ないです

198
Stern-Brocot tree
左端を適当にまとめると早くなる
1/102みたいなのを数え忘れないように(1敗)

199
デカルトの円定理 - Wikipedia

200
プラキューでp^2q^3を小さい順に生成してもよし
N以下のそういう数はO~(N^(2/3))個しかないので(区間ごとに)雑に列挙してもよし

続き
sugarknri.hatenablog.com

Project Euler 101-150 解説

f:id:sugarknri:20220401163514p:plain

これの続き
sugarknri.hatenablog.com

101
ラグランジュ補間
普通にやるとO(N^3)
補間に使う点が等差数列なのでO(N^2)にできる
ラグランジュ補間したときの係数をぐっと睨むと求めるものをexplicitにも書ける

102
多角形の内外判定
普通は半直線と線分の交差判定をやるが、三角形なのでいろいろ手抜きができる
画像処理ライブラリに丸投げするという手もある
OpenCV: Structural Analysis and Shape Descriptors

103
問題文に書いてあるsuboptimalな解を上界として愚直探索

104
ビネの公式　O(N)
13でやったような手抜きでも許されるらしい
pisano period を考えるまでもない
Pisano period - Wikipedia

105
部分集合全探索　O(Σ3^K)

106
よく考えると手で解けるらしい。
余事象を考えるとO(NlogN)で解ける。なにそれ怖い

107
最小全域木

108
競技数学/受験数学のド典型
高度合成数を求めるのとほぼ同じ問題になるので、プラキューを使う
2013年に頭脳王でほぼ同じ問題が出題されたらしい
頭脳王 - 超数理能力の解き方 | 東大首席会計士の備忘録

109
全探索やるだけ

110
108でやった
615も似たような感じで解ける

111
組合せ全探索
leading zeroに注意

112
Nが与えられたとき求める割合f(N)は桁DPでO(logN)で求まるが単調性が無いのでにぶたんできず意味がない
……ということはなく、adhocな高速化ができます
「今シーズン100打数25安打のイチローが、打率3割に戻すにはあと何打数必要？」

113
桁DPかと思いきや、算数

114
これくらいの漸化式は手で解きましょう。累積和を取ります

115
114と全く同じ問題。なにがおもろいねん

116
DPの基本

117
DPの基本2

118
bitDPがわかりやすいんじゃないですか

119
4みたいに区間を切って全探索するとよい。そこまでせずに雑に全部まとめて計算してもよい
http://www.asahi-net.or.jp/~kc2h-msm/pbsb/yurunavi01.htm
指数を固定したときの底の上限は小さいことを使ってもいい

120
式変形するだけ。手で解け

121
DP O(N^2)
実はある有名問題に帰着されるのでO(NlogN)でも解ける

122
ちょっと待って！！その枝刈り、本当に正当？
数学的に未解決な仮定をおいて枝刈りをすると解けます（は？）
数学的に証明されている範囲でやろうとすると、定数倍高速化バトル勃発

123
120でやった
素数の個数のオーダーから当てをつけて、素数カウント＋近傍だけ区間篩、とすると早い

124
やるだけ O(NlogN)
radごとに数えてO(M)で解いてもいい

125
全探索 O(N)……に見えて、以下のような自然な実装は実はO(N^(5/6))です

for(int l=1;hoge;l++){
  for(int r=l;;r++){
    if(l**2+...+r**2>N)break;
  }
}

126
上限が　不明なときの　解決法

127
124で見た
radごとにやりましょう

128
parityを見る

129
10∈(Z/9nZ)^*の位数
乗法群の構造をしっていますか？
ABC174C Extra - kyopro_friends’ diary

130
数行上の全てが書いてある

131
式変形をします。(n+k)^3とおいたら破滅するので別の方法を考えましょう
二次式の篩でO(√NlogN)で求められます。

132
やるだけ

133
O(NlogN)で全ての位数を求めてもいいし、O(NloglogN)で雑にチェックすることもできる

134
1次合同式を解くだけ
O(N)？

135
3変数1条件なので、当然2重ループで解けます
計算量解析をちゃんとやるとO(NlogN)になっていることが言えるはず

136
135と同じようにO(NlogN)で解いてもいい
天才考察をすると素数カウントに帰着されるので（は？）O(N^(2/3))で解けます

137
母関数を知っていますか？
2変数2次方程式になるので、ペル方程式です
右辺が±1でないやつの解き方を知っていますか？

138
ペル方程式です2

139
原始的なタプルだけを考えると、ペル方程式です3

140
137と全く同じで、ペル方程式です4

141
ある数がprogressive numberかどうかの判定は難しい。そういうときは列挙
式を整理すると3変数残るので、全探索するとO(N^(1/2)logN)
賢くやるとO(N^(1/3) poly(logN))にもできるそうです

142
適切に枝刈り全探索すると間に合う
ピタゴラス数列挙のやつでx+y≦Nの解がO(N poly(logN))で列挙できるのでそれやってもよい
有名問題らしいです
Pietro Mengoli - Wikipedia

143
トリチェリポイントを知っていますか？
120度の角度もち各辺が整数の三角形の列挙ができますか？
まあ別にできなくてもO(N^2)全探索を定数倍に気をつければ間に合うんですが……

144
全て問題文に書いてある。実装するだけ

145
全探索O(NlogN)が間に合ったり間に合わなかったり
桁DPでO(logN)
状態数が少ないので手でも解ける

146
小さいところはadhocに弾いてからミラーラビン
篩で2,3,5は先にやっておいて4/15に圧縮するテクみたいなやつのこと
WAになった人は問題文をよく読み直しましょう(1敗)

147
85と同様にO(1)で解けます
面倒だったらDPでも

148
Kummerだと思っても、Lucasだと思っても
Kummer's theorem - Wikipedia
Lucas's theorem - Wikipedia
あとは桁DPだが、Digits Paradise in Hexadecimal のように、初めてNと異なる桁で場合分けして考えるとDPするまでもない
F - Digits Paradise in Hexadecimal

149
愚直だとO(N^3)
少し考えるとO(N^2)
Kadane's algorithmをちゃんと名前で呼んであげてくれよな！
Maximum subarray problem - Wikipedia
定数倍を気にしないなら単に累積和のmax-minをするだけなんですが……

150
149とだいたい同じ
累積和を取ってから全探索してO(N^3)

続き
sugarknri.hatenablog.com