定数倍高速化
アルゴリズムとはほぼ無関係．
スタート地点
遅いコード 2797 ms Submission #3108991 - AtCoder Regular Contest 025
namespace Twoを修正します．
一番早いantaさんを見て絶対届かないと思いました．
pow
Two::myPowを実装する 1383 ms．思ったより効いた．
Submission #3110273 - AtCoder Regular Contest 025
次の繰り返し二乗法を更に高速化したい．
template<typename T> Matrix<T> pow(Matrix<T> a, long long p) { assert(a.height_ == a.width_); Matrix<T> b(a.height_, a.height_); b.setDiag(1); while (0 < p) { if (p & 1) b *= a; a *= a; p >>= 1; } return b; }
aは常に2のべきのべき乗で，aが一定値ならば，前計算で持っておいて，高速化出来る．
を
vector<Matrix<llmod>> mypow2m;
void initMyPow() {
mypow2m.reserve(38);
mypow2m.push_back(dpmat[0]);
repeat(i, 37)
mypow2m.push_back(mypow2m.back()*mypow2m.back());
}
inline Matrix<llmod> myPow(ll p) {
int i = 0;
Matrix<llmod> b(4, 4); b.setDiag(1);
while (0 < p) {
if (p & 1) b *= mypow2m[i];
++i; p >>= 1;
}
return b;
}
にした
multiply
行列のサイズが分かっているので，気合で展開した．
Submission #3110380 - AtCoder Regular Contest 025 1289 ms
テンプレートで展開する方法もあるとか無いとか．
inline Matrix<llmod> myMultiply(const Matrix<llmod>& mat1, const Matrix<llmod>& mat2) {
return Matrix<llmod>(4, 4, {
mat1(0,0)*mat2(0,0) + mat1(0,1)*mat2(1,0) + mat1(0,2)*mat2(2,0) + mat1(0,3)*mat2(3,0),
mat1(0,0)*mat2(0,1) + mat1(0,1)*mat2(1,1) + mat1(0,2)*mat2(2,1) + mat1(0,3)*mat2(3,1),
mat1(0,0)*mat2(0,2) + mat1(0,1)*mat2(1,2) + mat1(0,2)*mat2(2,2) + mat1(0,3)*mat2(3,2),
mat1(0,0)*mat2(0,3) + mat1(0,1)*mat2(1,3) + mat1(0,2)*mat2(2,3) + mat1(0,3)*mat2(3,3),
mat1(1,0)*mat2(0,0) + mat1(1,1)*mat2(1,0) + mat1(1,2)*mat2(2,0) + mat1(1,3)*mat2(3,0),
mat1(1,0)*mat2(0,1) + mat1(1,1)*mat2(1,1) + mat1(1,2)*mat2(2,1) + mat1(1,3)*mat2(3,1),
mat1(1,0)*mat2(0,2) + mat1(1,1)*mat2(1,2) + mat1(1,2)*mat2(2,2) + mat1(1,3)*mat2(3,2),
mat1(1,0)*mat2(0,3) + mat1(1,1)*mat2(1,3) + mat1(1,2)*mat2(2,3) + mat1(1,3)*mat2(3,3),
mat1(2,0)*mat2(0,0) + mat1(2,1)*mat2(1,0) + mat1(2,2)*mat2(2,0) + mat1(2,3)*mat2(3,0),
mat1(2,0)*mat2(0,1) + mat1(2,1)*mat2(1,1) + mat1(2,2)*mat2(2,1) + mat1(2,3)*mat2(3,1),
mat1(2,0)*mat2(0,2) + mat1(2,1)*mat2(1,2) + mat1(2,2)*mat2(2,2) + mat1(2,3)*mat2(3,2),
mat1(2,0)*mat2(0,3) + mat1(2,1)*mat2(1,3) + mat1(2,2)*mat2(2,3) + mat1(2,3)*mat2(3,3),
mat1(3,0)*mat2(0,0) + mat1(3,1)*mat2(1,0) + mat1(3,2)*mat2(2,0) + mat1(3,3)*mat2(3,0),
mat1(3,0)*mat2(0,1) + mat1(3,1)*mat2(1,1) + mat1(3,2)*mat2(2,1) + mat1(3,3)*mat2(3,1),
mat1(3,0)*mat2(0,2) + mat1(3,1)*mat2(1,2) + mat1(3,2)*mat2(2,2) + mat1(3,3)*mat2(3,2),
mat1(3,0)*mat2(0,3) + mat1(3,1)*mat2(1,3) + mat1(3,2)*mat2(2,3) + mat1(3,3)*mat2(3,3),
});
}
inline vector<llmod> myMultiply(const Matrix<llmod>& mat1, const valarray<llmod>& vec2) {
return vector<llmod>({
mat1(0,0)*vec2[0] + mat1(0,1)*vec2[1] + mat1(0,2)*vec2[2] + mat1(0,3)*vec2[3],
mat1(1,0)*vec2[0] + mat1(1,1)*vec2[1] + mat1(1,2)*vec2[2] + mat1(1,3)*vec2[3],
mat1(2,0)*vec2[0] + mat1(2,1)*vec2[1] + mat1(2,2)*vec2[2] + mat1(2,3)*vec2[3],
mat1(3,0)*vec2[0] + mat1(3,1)*vec2[1] + mat1(3,2)*vec2[2] + mat1(3,3)*vec2[3],
});
}
valarray
valarrayをvectorに戻したら100msほど遅くなった．valarrayの恩恵は微妙にあった様子．
Submission #3110422 - AtCoder Regular Contest 025
効果が無さそうな軽い高速化
なぜ効果が無さそうと思ったのかというと，apply関数に関係がないから．
cappedBitのmapをunordered_mapにしたり，mapの呼び出し回数を減らしたり．
結果は実行時間誤差の方が大きい．
vectorを辞める
vectorを辞めてallocatorを使う．1170 ms
Submission #3110621 - AtCoder Regular Contest 025
vectorのままでも解決出来た気はしますが，性癖の関係でallocatorにした．
vector<T>::resize(n)したり，T[n]したりすると，n回コンストラクタが呼ばれる．
しかし，allocatorやvector<T>::reserveを使えば，コンストラクタを呼ぶ回数を減らすことが出来る．
セグ木のノードの配置順序を変える
「vectorを辞める」でallocator を使っていた理由．「子ノード2つに番号を割り当てる」→「右子ノード構築」→「右子ノード再帰」→「左子ノード構築」→「左子ノード再帰」としていたので，ムーブ構築の呼び出し順と番号順が異なっていた．
「右子ノードに番号を割り当て」→「右子ノード構築」→「右子ノード再帰」→「左子ノードに番号を割り当て」→「左子ノード構築」→「左子ノード再帰」でムーブ構築の呼び出し順と番号順を一致させてみた．
早くなるかなと期待していたが誤差レベル．
Submission #3110697 - AtCoder Regular Contest 025
デストラクタを呼ぶ前にexit(0)
嫌いなテクニックの1つ．1135 ms．謎RE*1が出る場合に使うこともある．
Submission #3110739 - AtCoder Regular Contest 025
やらなかった事
思いついたので少し追記(2018/9/2)
- DPに使う状態を増やす．2列ずつDPするとか．
- antaさんのコードを読む
Matrix<llmod>の改造．幅・高さ情報の除去．4*(MOD**2)がlong longを超えない事を利用して，掛け算中は剰余しない．
*1:謎と言っているが大抵実装者が悪い
