メモ

yukicoderでゆるふわgolf

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くらいでしょ!w→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