ひさびさのEuler充
週末に20問くらい解いた。
フォーラム見てたら、数列の階差を取ってみると1個とばしのフィボナッチ数列で一個おきに2倍になってるよ (F[3], 2F[5], F[7], 2F[9], ...) とか普通に気づく人がいたりして笑った。変態すぎるぜ。
今まで問題の手のつけ方が汚くてプロフィールページの見た目があまりにもアレだったので、ちまちまと食べ残しの穴を片付けてます。だいぶマシになったかしら。きちんと順番に解いてる人えらいー。
以下ここ数日の回想(ネタバレ)
60
各素数をノードとするグラフ作ってサイズ5のクリークを求める。
次数の低い、数字の大きな方からチェックすると速い。
そして遅延評価をうまくつかった brute force かっこいい。そんな素直にいけちゃうのかー。
84
遷移確率の行列作るだけ。めんどかった。
100
このあたりで一般的な二次曲線上の整数点の列挙の方法を学ぶ。
101
連立一次方程式をつくって解く。行列ライブラリ便利ー。
103, 105, 106 (Special Sum Set)
大きい要素k個よりも、小さい要素(k+1)個のほうがでかくなればいい。サブセット間で和が等しくならないかチェックは重いので後回し。
103は、なんかヒントがそのまま答えだった。周りを探索しても何も見つからなくてあれ？と思った。
106は (∀i. B[i] < C[i]) => S(B) < S(C) を使うだけ。
110
x = n+k, y = n(n+k)/k (x ≦ y) を考える。k は n^2 の約数のうち n 以下のもの。
n = (2^a)(3^b)(5^c)... のとき n^2 の約数の個数は (2a+1)(2b+1)(2c+1)... で、そのうち半分が n 未満かつ n は約数になる。
結局条件 (2a+1)(2b+1)(2c+1)... > M を満たしつつ n = (2^a)(3^b)(5^c)... を最小化する話になる。
111
"repeated" って 1151みたいに連続してなくても良いんか？っておもった。愚直にやると計算量が怖かったけど、実際やってみるとそうでもなかった。
127
rad は予め全部計算して配列に入れとく。
gcd(b,a) == 1 && rad[a]*rad[b] < q
を
rad[a]*rad[b] < q && gcd(b,a) == 1
にしたら 1m40s → 6s になった。意味的には前者の方が気持ち良いんだけど…。
