「10進数585は2進数で1001001001です。 それは両方のベースでパリンドロームです。 n番目の回文数を見つけます。 または、ロシア語で：「2進数システムの10進数585は1001001001のように見えます。両方の番号システムの回文です。 n番目の回文を見つけます。
著者は、 1からNまでのすべての数値と計算の複雑さO（N * log（N））を並べ替えてチェックすることにより、最も簡単なソリューションから魅力的なストーリーを始めました。Nはチェックする最大数です。 ログ（N）係数が必要な理由は チェックされた番号ごとに、その桁数に応じていくつかのアクションが実行されます。
最初の作業の最適化、つまり、すべての数値の列挙を10進パリンドロームのみの列挙に置き換えると、計算される数がO（N 1/2 * log（N））に劇的に改善されました。 ） また、アルゴリズムの複雑さによるいくらかの損失にもかかわらず、十分に大きいNの場合、実行時間は桁違いに予測可能に改善されました。
いくつかの小さな最適化を行った後、著者はランタイムを3倍改善し、この良い結果で停止することにしました。
まだ最後まで読んでいないので、同じ計算の複雑さで、 O（N 1/2 * log（N））はおそらく文字列ではなく、直接数値ではるかに速く動作すると思いました。 つまり、算術演算ではなく算術演算を使用してパリンドロームのシーケンスを生成します。
そして、同じ長さのパリンドローム数のシーケンスは、 BASE 、 BASE 2 、 BASE 3 、...要素ごとに調整する必要がある一定のステップを伴う算術的進行に似ているため、まったく難しくないことが判明しました。
たとえば、幅が5の 10進数回文の場合、メインステップは+100になります。
10001, 10101, 10201, 10301, 10401, 10501, 10601, 10701, 10801, 10901, 11001
シーケンスの最後の要素はパリンドロームではないため、 +10から
11011
への修正が必要です
11011, 11111, 11211, 11311, 11411, 11511, 11611, 11711, 11811, 11911, 12011
シーケンスの要素の最後の要素には、再び+10から
12021
への修正が必要です。
したがって、 99番目と100番目の要素を取得します：
19991, 20091
100番目の要素に必要な補正+ 10-99 = -89の結果、
20002
なり、
99999
に達するまで続行します。
パリンドロームの算術生成が非常に高速になったため（平均して、数個のアセンブラーコマンドのみ）、あるベースでのパリンドロームの生成+別のベースでのパリンドロームのチェックは、両方のベースでのパリンドロームの生成と比較よりも遅いと判断しました。
その結果、次のC ++コードが取得されました。
必要な基礎度を備えた補助構造：
#undef POWER #define POWER(exp) m_powers[exp] template<typename IntT> struct BaseData { static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT; BaseData( size_t base, IntT maxValue) : m_base(base) { POWER(0) = IntT(1); for (size_t i = 1; i < MAX_WIDTH; ++i) { POWER(i) = POWER(i - 1) * IntT(base); if (POWER(i) >= maxValue) { m_maxWidth = i - 1; break; } } } size_t m_base; size_t m_maxWidth; IntT m_powers[MAX_WIDTH]; };
パリンドロームイテレーター：
template<typename IntT> class Iterator { static const size_t MAX_WIDTH = sizeof(IntT) * CHAR_BIT; private: struct IncrementData { size_t m_counter; // current counter value size_t m_counterLimit; // number of iterations, usually B, but B - 1 for last increment IntT m_increment; // increment value }; public: inline Iterator( const size_t base, const IntT * powers) : m_base(base) , m_powers(powers) { m_value = POWER(0); SetWidth(1); } inline void operator ++() { // always increment by basic m_value += m_basicIncrement; size_t i = 0; do { if (--m_counters[i].m_counter) return; // reset counter m_counters[i].m_counter = m_counters[i].m_counterLimit; // correct value on digit overflow m_value += m_counters[i].m_increment; } while (++i < m_countersSize); // prepare to next width SetWidth(m_width + 1); } inline const IntT & operator *() const { return m_value; } private: void SetWidth( size_t width) { m_width = width; m_countersSize = (m_width + 1) / 2; m_basicIncrement = POWER(m_countersSize - 1); size_t i; for (i = 0; i < m_countersSize - 1; ++i) { m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base; m_counters[i].m_increment = POWER(m_countersSize - i - 2) - POWER(m_countersSize - i - 2) * m_base * m_base; } m_counters[i].m_counter = m_counters[i].m_counterLimit = m_base - 1; m_counters[i].m_increment = POWER(0) - POWER(1); if (m_width & 1) m_counters[0].m_increment += POWER(m_countersSize); else m_basicIncrement += POWER(m_countersSize); } IntT m_value; // current value IntT m_basicIncrement; // basic increment (100... for odd width, 1100... for even width size_t m_countersSize; // just greater half of width: (width + 1) / 2 IncrementData m_counters[MAX_WIDTH]; size_t m_width; // current width = number of digits size_t m_base; const IntT * m_powers; };
そして最後にメイン：
int _tmain(int argc, _TCHAR* argv[]) { int64 limit = 18279440804497281; BaseData<int64> base0(2, limit); BaseData<int64> base1(10, limit); Iterator<int64> it0(base0.m_base, base0.m_powers); Iterator<int64> it1(base1.m_base, base1.m_powers); while (*it0 <= limit) { if (*it0 < *it1) ++it0; else if (*it0 > *it1) ++it1; else { std::cout << *it0 << std::endl; ++it0; ++it1; } } return 0; }
18279440804497281に相当する56番目のパリンドロームは、 1.85秒後に取得されました。これは、以前の結果よりも約150倍高速です（ grey_wolfsコンピューターのIntel Core i7-3770 CPU @ 3.40GHzと同等の計算能力があると仮定）。 もちろん、私の利点の大部分はPHPからC ++への移行によって生じましたが、私はまだ満足して手をこすりました：アルゴリズムはすでに1秒あたりほぼ300,000,000回のパリンドロームを整理しており、さらに2枚の切り札がありました：奇数の10進パリンドロームのみを生成します（ - 20-25 ％）およびマルチスレッドを使用（8スレッドで-70-85 ％）...
そして、私はちょうど私を「殺した」というコメントを見ました：
@hellman
少し前まで、codechefコンテストの1つでも同じ問題が発生していました。 2から16までの微積分システムのベースのみが任意であり、2 ^ 60より小さい最初の1000回の回文が必要でした。 制限時間は8秒です（ただし、入力には5つのテストがある場合があります）。 社説があります。
私のアルゴリズムは、 15秒で2 60までのすべての回文を見つけました。 最悪の場合、マルチスレッドを使用しても制限時間に収まりません。 しかし、エディトリアルには、「なぜこの質問の制限時間は8秒と非常に長いのですか？質問でこのような高い制限が見られないのはなぜですか？」という。笑的なコメントもありました。
満足度はすぐに失望に変わりました。計算の複雑さO（N 1/2 * log（N））の列挙の私の実装は、理論上の最小限界に近かったのですが、それでもまだ十分ではありませんでした。 エディトリアルで説明されている理論的な解決策を見つけようとしましたが、コードを見ても、 O（N 1/4 * log（N））付近の計算の複雑さで問題を解決できることに初めて気付きました。
この時点で、タスクの作業を停止しましたが、頭から出ませんでした。 そして数日後、私は彼女に戻りました。
継続する 。