2022-03-25

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

2022-03-24

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

2022-03-11

segment tree beats 覚書

ポエム

これを読め
rsm9.hatenablog.com
～終わり～

以下ポエム
ひとなのでさんによるこの記事を読むまでbeatsの理解が困難だったが、この記事を読むと全てを3秒で理解できた。
これ以前に存在していた記事で理解が困難だったのは、まずそもそもbeatsというデータ構造の概念の部分の話・実装に関する話・計算量解析に関する話がいっしょくたにされていることが多かったため。
beatsの本質は「mapping(f,x)が計算できないなら、op(left,right)で計算する」というだけ。冒頭の記事ではこれを一番最初に説明してくれており、それでようやくbeatsというものが何をするデータ構造なのか理解できた。この段階では計算量解析には触れずに「もしそういうことができるなら、これでうまくいくね」という話し方をしている。非常にわかりやすい。

作用 f(x) の計算に失敗してしまった場合，「とりあえず f を x の子に伝播させて子の計算を先に行い，子に関する計算結果を用いてボトムアップに x′ を再構築する」という方法で問題を回避できそうです．ここで計算の失敗回数が多すぎる（例えば列の長さ N やクエリ個数 Q に関する二乗のオーダーになってしまう）と計算量が悪化してしまいますが， S や F の構造などに由来する何らかの理由で「Segtree 上の全頂点における失敗回数の合計」に良い上界（例えば O((N+Q)log2⁡N)）が与えられるならば，計算量の本質的な悪化が回避でき，高速なクエリ処理が可能となります．
atcoder::lazy_segtree に1行書き足すだけの抽象化 Segment Tree Beats - ひとなので

実装パートも、beatsが何なのかを冒頭のように理解していれば1行書き足すだけなのは自明。非常にわかりやすい。
計算量解析パートの理解が困難だったのも、chmin/sumのような複雑な例を最初に出されることが多かったため。ひとなのでさんの記事はこの点でも完璧で、1番目の例は、gcdが本質的にchminであることから「failするたびその区間に属する値の"max"が真に小さくなるため(特に1回目でクエリの値まで落ちる)」と簡単に理解できる。次の例も「(Z/2Z)^64という束の"高さ"が64であり、failするたびにその区間に属する値の"min"と"max"の"高さ"の差が真に小さくなるため」と理解できる（ハッセダイアグラムを頭に思い浮かべながらchand/chorクエリの効果をイメージできますか？ぼくはできます）。わかりやすい。
データの持ち方パートについても、これらはともに「chminがうまく走るか見たいから区間の最大値もっとこ（最大値＜chminクエリの値なら無視できるので）」というだけなのでかなり自然。
それに比べてchmin/sumはめちゃくちゃ複雑。なぜかというと「failするたびにその区間に属する値のmaxが真に小さくなる」を言っても、それは1e9回起こりうるため。もっと小さくなる何かを持ちてえなあという気持ちになり、second maxを持って区間内の値の種類数を減らそうと思える（は？）。計算量解析は難しい（「failするたびにその区間に属する値の種類数が減るため」ではO(N^2)しか言えないので）（は？）　こんなもんを初心者に見せるな
以上です。

2022-02-14

a+b=a^b+2(a&b)の一般化

bit毎の排他的論理和を $\oplus$ 、論理積を $\odot$ と置くと、
任意の非負整数 $a, b$ に対して
$a+b=a\oplus b+2(a \odot b)$
が成り立ちます。
これは
$0\oplus 0+2(1\odot 1)=0+0=0\\ 1\oplus 1+2(1\odot 1)=0+2=2\\ 0\oplus 1+2(0\odot 1)=1+0=1$
を観察すれば成り立つことが示せます。
この等式は競技プログラミングで非常によく使われるテクニックの一つです。
Yukiちゃんはこの等式を一般化して、
$\displaystyle x_1+x_2+\cdots+x_N=\sum_{k=1}^{N}a_k\sigma_k$

の形で表せないか気になりました。ここで $\sigma_k$ は $\oplus ,\odot$ を演算とする $x_1,x_2,\ldots,x_N$ の $k$ 次対称式です。
例えば、 $N=3$ のときは、
$\displaystyle x_1+x_2+x_3=a_1(x_1\oplus x_2\oplus x_3)+a_2(x_1\odot x_2\oplus x_2\odot x_3\oplus x_3\odot x_1)+a_3(x_1\odot x_2\odot x_3)$
です。
実は帰納法により、
$\displaystyle x_1+x_2+\cdots+x_N=\sigma_1+2\sigma_2+4\sigma_4+8\sigma_8+16\sigma_{16}+\cdots$
であることが示せます。