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 解説

これの続き
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 解説

これの続き
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

project Euler 51-100 解説

これの続き
sugarknri.hatenablog.com

51
3の倍数で枝刈り

52
有名問題すぎる

53
尺取
rが小さいうちは境界を直接計算すると早い

54
気合

55
多倍長整数

56
多倍長整数
嘘下界を使って嘘枝刈りで高速化

57
連分数の最後に1項増やしたときの挙動を知っていますか
分子と分母の一般項を求めると、N→無限での比率の極限がlog10(2)/2だと予想できる。面白いね

58
一般項が二次多項式で与えられる数列を篩にかける方法を知っていますか
あとこれ
上限が不明なときの問題解決法 - inamori’s diary

59
頻度分析を知っていますか

60
全探索
5-cliqueを求める問題だと思ってNetworkXにぶち込んでも解けるそうです（え？）

61
全探索
条件が厳しいところからやる

62
49と同じ
ちなみに「5個」ではなく「7個」に対する答えは10314675896832ではありません。問題文を正しく読めましたか？

63
高校数学
常用対数表を見ながら紙とペンで解け

64
分母の有理化
実はN=4k,4k+3のときには必ず偶数周期になることが証明できます。ヒント：ペル方程式

65
57と同じ
分母のなす数列はp-recursiveなので、高速に求めることもできます

66
ペル方程式の解き方を知っていますか？
64,65で書いたコードが役に立ちます
実は賢くやると多倍長整数なしでも解けます。マジ？
めちゃくちゃやばい制約でも解けます。マジ？？？？？
SPOJ.com - Problem PELLFOUR

67
18で解説した

68
手で解け

69
トーティエント関数の性質を知っていますか
手で解け

70
正解者掲示板が嘘解法だらけ。何が嘘か考えて1つずつ論破しましょう
実はプラキューを(ダイクストラのように)適切に使うと、嘘なしで、余分な計算をかなり少なくしてn/phi(n)の順にnを取り出すことができます
類題は615です

71
ファレイ数列を知っていますか
近似したい分数をa/bとして、O(N)やO(b)やO(log b)の解法があります

72
お ま た せ　い つ も の　親 の 顔 よ り 見 た totient sum
https://yukicoder.me/wiki/sum_totient

73
bounded totient sum、実は72と同じ計算量で解けます（えー）

74
競プロでありがち。実装が面倒
並び替えを同一視して状態を圧縮もできる

75
39で挙げた生成行列のやつでまず互いに素なものを生成したあと約数ゼータ変換
O(NlogN)

76
DPでO(N^2)
五角数定理でO(N^1.5)
五角数定理＋FPSの逆数でO(NlogN)

77
DPでO(N^2/logN)
FPSのlog+expでO(NlogN)

78
76でやった

79
トポロジカルソートして解けるならそれで終わり
一般の場合はハルヒ問題(最小超置換問題)の一般化なのでヤバそう

80
開平法を知っていますか
むしろ知らなければisqrt(D*10**198)で解けます

81
DP O(N^2)

82
愚直DP O(N^3)
賢いDP O(N^2)

83
ダイクストラ O(N^2 logN)

84
モンテカルロ

85
手で解け

86
またピタゴラス数の列挙です

87
全探索
条件が厳しいところからやる

88
DFS

89
実は数種類の置換をするだけで十分です

90
全探索

91
全探索 O(N^4)
少し考えるとO(N^2 logN)
gcdを表引きするとlogが落ちる

92
メモ化再帰でO(N)
桁DPと組み合わせるとO((logN)^2)

93
全探索

94
ペル方程式

95
74でやった

96
naked single＋バックトラックだけで解ける
比較的簡単な理詰めだけで解けるので、ひとによっては手で解いた方が早いかも

97
二分累乗
オイラーの定理

98
全探索
条件が厳しい方からみる　条件が厳しいのはどーっちだ？

99
高校数学
なお一般には破滅します
No.219 巨大数の概算 - yukicoder

100
ペル方程式

続き
sugarknri.hatenablog.com

project Euler 1-50 解説

間違ってたりより良い解法があったら教えて

計算量は四則計算の回数。桁が増えすぎると壊れる

1
包除原理
これくらい手で解け

2
愚直で解ける
項数を先に求めて行列累乗すればO(loglogN)
一般項を出して適当なmodを取ってCRTすると実質O(1)

3
素因数分解の計算量よくわからん
変な数を素因数分解したくなったら、そのへんのサイトに投げてみよう
https://www.alpertron.com.ar/ECM.HTM
http://factordb.com

4
乗数と被乗数を全探索 計算量は謎
こういうのは、

int width=1e4;
for(int U=1e6;;U-=width){
  int L=U-width;
  for(int x=999;x*x>=L;x--){
    for(int y=min(U/x,x);x*y>=L;y--){
      //hoge
    }
  }
}

みたいにやるのが定石。意外と忘れやすい

5
lcm取るだけ O(NlogN)
素数の指数のmaxを考えると O(NloglogN)

6
1乗和・2乗和・3乗和のclosed-formを知っていますか？
ファウルハーバーの公式 - Wikipedia

7
篩をするとO(NlogN poly(loglogN))とかになるはず
O(N^(2/3))素数カウント+二分探索+区間篩でもっと早くなったりするのかな

8
愚直 O(NK)
0に注意して尺取するとO(N)

9
愚直 O(N^2)
ピタゴラス数の列挙式を使うと O(√N)
ピタゴラスの定理 - Wikipedia
正解者掲示板で1000ふぁぼついてる投稿が嘘解法で草。何が嘘かわからない人は1000じゃなくて36で解いてみて

10
愚直 O(NloglogN)
お ま た せ　い つ も の　親 の 顔 よ り 見 た Lucy DP　O(N^(3/4)/logN)
実はO(N^(2/3))とかで出来るらしいです

11
愚直 O(NNK)
0に注意して尺取するとO(NN)
この前のABCで見た
C - Connect 6

12
愚直にやると約数カウントが大変そう
osa_k法で高速素因数分解すると早そう
計算量はわからん

13
やるだけ
ところで、例えば上n桁で概算すると、その下2桁は(100個の数を足すので)50くらいの誤差を持つことが期待される。ということは上13桁くらいで概算すればよさそう
この手の嘘計算量削減や、最後の1桁総当り作戦もオイラーでは重要なテクニックの一つ（？）

14
メモ化再帰

15
二項係数

16
多倍長整数

17
桁ごとに分けるテク
この前のABCで見た
C - Comma

18
愚直 O(2^N)
DP O(N^2)

19
ツェラーの公式
日付型ライブラリ
だいたい1/7くらいでしょ！ｗ→1200/7の前後を総当り

20
多倍長整数

21
エラトステネスみたいに約数和の配列を作ってO(NlogN)
線形篩と同様にすればO(N)

22
ファイル入出力

23
21と同様に過剰数を列挙して愚直でO(N^2)
FFTでO(NlogN)

24
貪欲でO(N^2)
セグ木で持てばO(NlogN)（実際には桁数が膨大になって四則演算がO(1)にならないが……）

25
ビネの公式

26
ラグランジュの定理
ラグランジュの定理 (群論) - Wikipedia

27
枝刈り全探索
最悪でもn=bで終わるので、2e6+αくらいまで篩えばOK

28
階差数列

29
多倍長整数 or logとってset O(N^2 logN)
実はN=10^16とかでも解けて466がそれ（え？）

30
左辺ではなく右辺を全探索

31
DP
制約強化版がここにある
No.137 貯金箱の焦り - yukicoder

32
全探索

33
全探索
実は手でも解けるらしい

34
30と同じようにやると見せかけて、桁数が多いので上下に分けるとより高速になる（こういうのもmeet in middleっていうのか？）

35
1e6まで篩っておいて4^kを全探索

36
回文は上半分を決めると決まる
この前のABCで見た
E - (∀x∀)
2進数で回文かどうかの判定は、bit reverseしてtrailing zeroを削除するとビット演算だけでできる

37
素数を上に一桁伸ばすのと下に一桁伸ばすの、条件が厳しいのはどーっちだ？
条件が厳しいということは候補が少ないということです。そっちを全探索しましょう

38
これくらいなら紙と鉛筆で解きませんか？

39
9で解いた
ピタゴラス数の列挙式ではなく、生成行列を使うと、gcdのlogがつかない分早い
Pythagorean Triple -- from Wolfram MathWorld

40
再掲
C - Comma

41
一般に、2,3,5,7あたりの自明な条件は、最初に考察で弾くほうが良い
残りは全探索

42
set でクエリあたりO(log)＋前計算
平方根を計算すればクエリあたりO(1)

43
条件が厳しいということは候補が少ないということです（再）
手でも解けるそうです

44
実は適当にやっても通ってしまいますが、その解法が正しいことは誰も証明できていません（俺は思いつかないし、正解者掲示板にも書いていない）
計算量の保証がある解法を思いつくのはめちゃくちゃ難しい
Project Euler 44（1） - inamori’s diary

45
ペル方程式

46
答えが小さいことを祈る

47
答えが小さいことを祈る2

48
modの基礎
二分累乗するまでもない

49
並び替えを試す前に map< int, vector< int >> に分解しておくと早い

50
累積和＋尺取
尺取でバグらせたくなければ、区間DPみたいにlenでループするのもあり

for(int len=U;len>0;len--){
  for(int l=0,r=len;sum[r]-sum[l]<1e6;l++,r++){
    //hoge
  }
}

続き
sugarknri.hatenablog.com