AtCoder Beginner Contest 111 C - 今日から始める競プロ日記

はじめに

chokudaiさんの今日の一問を解いてみた。

AtCoder Beginner Contest 111 C ( ABC 111 C )

方針はすぐに立ったけど、 結局20分くらいかかってしまった。

たぶん方針の立て方が甘いのだと思う。

今日の問題は、 /\/\/\/！
……ごめん、名前のインパクトで選びました。でも普通に良い問題です。といてね！#chokudai今日の一問https://t.co/1dhKInp8qS

— chokudai(高橋 直大)🌸🍆🍡 (@chokudai) September 11, 2019

C - /\/\/\/

数列が与えられる。

この数列の偶数番目と奇数番目をそれぞれ同じ値にしたい。

値を書き換える最小回数を求めよ。

atcoder.jp

解いた方針

1. 与えられた数列を偶数番目の数列と奇数番の数列に分ける
2. 二つの数列においてそれぞれ最頻値と二番目の最頻値を求める
3. あとは最頻値となる値に数列を揃えればよい（書き換える最小回数を求める）
4. 気を付けることは偶数番目と奇数番目の値は異なる必要があること
5. つまり最頻値となる値が同じ場合はどちらかを二番目の最頻値の値にすることが必要

コード

解いた方針とちょっと違うことをしてる。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
 
int main()
{
    // 入力
    map<int, int> mp1;
    map<int, int> mp2;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++)
    {
        int a;
        cin >> a;
        if(i % 2 == 0) mp1[a]++;
        else mp2[a]++;
    }

    // 最頻値から答えを求める１
    int max1 = 0;
    int key = 0;
    for(pair<int, int> m: mp1)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    int max2 = 0;
    for(pair<int, int> m: mp2)
    {
        // mp1の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans1 = (N/2 - max1) + (N/2 - max2);

    // 最頻値から答えを求める２
    max1 = 0;
    key = 0;
    for(pair<int, int> m: mp2)
    {
        if(m.second > max1)
        {
            max1 = m.second;
            key = m.first;
        }
    }
    max2 = 0;
    for(pair<int, int> m: mp1)
    {
        // mp2の最頻値となるkeyとは異なる値を選ぶ
        if(m.second > max2 && m.first != key) max2 = m.second;
    }
    int ans2 = (N/2 - max1) + (N/2 - max2);

    // 答えを出力
    int ans = min(ans1, ans2);
    cout << ans << endl;
    return 0;
}

おわりに

無難に解けた

今日から始める競プロ日記のまとめページ

kato-robotics.hatenablog.com