結果
問題 | No.1905 PURE PHRASE |
ユーザー |
![]() |
提出日時 | 2022-02-06 15:06:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,231 bytes |
コンパイル時間 | 891 ms |
コンパイル使用メモリ | 89,032 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 17:20:33 |
合計ジャッジ時間 | 2,050 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
// 想定解1// (A_i) と (A_{i + period}) の内積(自己相関)を見る#include <iostream>#include <vector>using namespace std;const vector<double> freqs{261.6, 294.3, 327.0, 348.8, 392.4, 436.0, 490.5};int main() {cin.tie(nullptr), ios::sync_with_stdio(false);int N;cin >> N;vector<int> A(N);for (auto &x : A) cin >> x;long long bestscore = -1;int argbest = -1;for (int d = 0; d < freqs.size(); ++d) {long long score = 0;// freq[d] Hz -> 長さ N で freq[d] 周期 -> 一周期 period は N / freq[d] 要素分int period = N / freqs[d];for (int i = 0; i < N / 2; ++i) {// 周期が period くらいならば、// A[i] 自体と A[i] を period だけずらした A'[i] = A[i + period] は// ほぼ同じ形状になるはず// A と A' の内積を適当にとって、これが最大になるようなものが答えscore += (long long)A[i] * A[i + period];}if (score > bestscore) {bestscore = score;argbest = d;}}cout << (char)('A' + (2 + argbest) % 7) << "4\n";}