プログラミング

【競プロ精進日記】c++習得編<24>

本記事は管理人が競技プログラミングを始めたため,その精進日記としてログを取ったものです。アウトプットして積極的にモチベーションを上げていく作戦です。まずはc++を習得するところから始めます。その他の記事は以下をご覧ください。

内容は管理人の推測や恣意的な感想を大いに含みます。もし間違い等ありましたらご指摘ください。あくまでも参考程度にお願い致します。

【競プロ精進日記】目次まとめ ABC Atcoder Beginner Contestの過去問を解いています。最低限のコメントと一言が添えられています。 ...

最頻値

C++入門 AtCoder Programming Guide for beginners (APG4b)を1からさらっていく内容です。

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N){
    cin >> A[i];
  }
  map<int, int> C;
  rep(i, N){
    if (C.count(A[i])){
      C[A[i]] ++;
    }
    else{
      C[A[i]] = 1;
    }
  }
  int max_value, max_cnt = 0;
  for (int x : A){
    if (max_cnt < C[x]){
      max_cnt = max(max_cnt, C[x]);
      max_value = x;
    }
  }
  cout << max_value << " " << max_cnt << endl;
}

mapやqueue,stackなどを活用しましょうというお話。mapは辞書型のようなものですね。今回は各数字の頻度を格納するためにmapを利用しました。存在判定をしてから処理を記述することで不用意な初期化を防ぎました。

ここら辺コツなのかもしれないのですが,最初のうちはfor文は分けた方が分かりやすいですよね。例えば,今回の場合は入寮をとりあえず格納するためのfor文を最初に回しています。おそらく,慣れている人にとっては冗長なfor文だとは思うのですが,最初のうちは着実にアルゴリズムを展開させていくために必要だと思っています。

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です