AtCoder Programming Guide for beginners の Ex. 23 最頻値でのWAの原因

Question

質問

競プロ初心者です。
AtCoder Programming Guide for beginners の Ex. 23 最頻値の問題を解いていたのですが、sample01.txt, sample02.txt, sample03.txtのテストはパスしたのですが、test01.txt, test02.txtはWAになってしまいます。test01.txtとtest02.txtの中身がわからないので正確なことはわからないのですが、大きいデータのため何か不都合が生じたのではないかと考えています。下記のコードで上手くいかない原因がわかる方いらっしゃったら教えていただけませんか？

実行結果

ケース名	結果	実行時間	メモリ
sample01.txt	AC	8ms	3636k
sample02.txt	AC	3ms	3700k
sample03.txt	AC	3ms	3656k
test01.txt	WA	23ms	3676k
test02.txt	WA	41ms	3736k

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, n;
  cin >> N;
  priority_queue<int> pq;
  for (int i = 0; i < N; i++) {
    cin >> n;
    pq.push(n);
  }
  int count = 0, max;
  for (int i = 0; i < N; i++) {
    if (i == 0) max = pq.top();
    if (max == pq.top()) {
      count++;
      pq.pop();
    }
  }
  printf("%d %d\n", max, count);
}

AtCoder記載の解答

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }
 
  map<int, int> cnt;
  for (int x : A) {
    if (cnt.count(x)) {
      // 既に含まれているならインクリメント
      cnt.at(x)++;
    } else {
      // 含まれていないなら、1を追加
      cnt[x] = 1;
    }
  }
 
  int max_cnt = 0;  // 出現回数の最大値を保持
  int ans = -1;     // 出現回数が最大になる値を保持
  for (int x : A) {
    // 今見ているxの出現回数が、その時点の最大よりも大きければ更新
    if (max_cnt < cnt.at(x)) {
      max_cnt = cnt.at(x);
      ans = x;
    }
  }
 
  cout << ans << " " << max_cnt << endl;
}

Answer 1

「最頻値」が何なのか正確に理解していないのか、priority_queueの仕様を正確に理解していないんだと思います。

5
1 1 1 1 2

こういうケースの時、何を出力すべきなのか解答例と比較してみてください

Comments

[episteme]

...そか、最"頻"値か。

[johndo]

ご回答ありがとうございます。
最頻値の意味を取り違えていました。
修正し、ACになりました。

Answer 2

if (max == pq.top()) {　... } に else break; を追加して早々にloopから抜けるのはいかがでしょ。

※ スンマセンまったくもって的の外れた回答でした _o/L

Comments

[johndo]

ご回答ありがとうございます！