プログラミング

【競プロ精進日記】ABS編<8>

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

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

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

AtCoder Beginners Selection

AtCoder Beginners Selectionの問題を1から解いていくシリーズです。使用言語はc++とpythonです。今回はABC085B Kagami Mochiです。

c++

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

// 以下は配列を表示するための関数です
// 今回はしっかりと重複が削除されているかどうかを可視化するために利用しました
void printVec(vector<int> &V){
  cout << "[";
  int cnt = 0;
  for (int v: V){
    if (cnt < V.size()-1) cout << v << " ";
    else cout << v;
    cnt ++;
  }
  cout << "]" << endl;
}

int main() {
  int N;
  cin >> N;
  vector<int> D(N);
  rep(i, N){
    cin >> D[i];
  }
 // まずはソートします
 // uniqueは隣合う重複を削除する関数ですので
 // ソートしないと同じ数字が出現する可能性があります
  sort(D.begin(), D.end());
 // uniqueの返り値をそのままeraseで利用します
  D.erase(unique(D.begin(), D.end()), D.end());
  cout << D.size() << endl;
}

配列内の重複を削除する問題です。c++ではSTLにuniqueという関数が装備されています。uniqueは隣り合う重複を削除する関数ですので,昇順ソートした配列に対してuniqueを適用することで,重複を完全に削除した配列を得ることができます。

しかし,それ単体では重複を削除する前の配列と同じ長さの配列を作成します。そのために,作成される配列は末尾にゴミが残っています。uniqueの返り値は末尾のゴミが始まるインデックスですので,そいつをeraseの引数として利用すれば,うまいこと重複を削除した配列が得られます。答えは,重複を削除した後の配列の長さを出力すればOKです。

python

N = int(input())
D = []

for n in range(N):
  D.append(int(input()))

# 美しい!!!
print(len(list(set(D))))

pythonではもっと美しいです。set型を利用することで重複を削除し,そいつをlistに直して長さを取得することでOKです。5行とはびっくりですね。(リスト内包表記などを利用すればもっと簡潔に書けます)

COMMENT

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