メモ

yukicoderでゆるふわgolf

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