コンテストがすべて終わったので、この問題ステートメントを再試行しています（したがって、不正行為でも何でもなく、学習したいだけです。回答は公開されておらず、特定のテストケース入力ファイルの正しい出力のみです）。
10 個の特定のテスト ケース入力があり、関連する出力ファイルが送信されます。私の最初の提案は、(start,end) ペアの単純なネストされた for ループの実装であり、次のクエリに答えていましstartたend。
明らかに、問題の最大制限が 10 6の場合、O(N 2 ) は実行不可能であるため、5/10 のテスト ケースしか正しくありませんでした (最初の - もちろん、より単純な - 5)。
そのため、アルゴリズムを改善する方法についてクラウド インテリジェンスを求めるためにここに書いています。つまり、ネストされた for ループ (開始、終了) が最適化の主なボトルネックであると思われます (もちろん!) これまでのところ、私はこれを文字列/部分文字列の問題に関する動的計画法 (DP) として定式化しようとする道をたどりましたが、DP を実装できるように状態表現と遷移ビットを考え出すことにあまり成功していません。
簡単に参照できるように、また、これが宿題ではなく、私が正直に試したことを示すために、元の提出物をここで入手できます。
チュートリアルのブログ投稿/サンプル ソリューション/コンテスト後の編集分析をグーグルで検索できる同様の問題へのリンクでさえ、どんな助けも大歓迎です。