C - Together

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 072
C - Together
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

長さNの整数列 a1,a2,...,aN が与えられます。
各 1≤i≤N に対し、ai に 1 足すか、1 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。
この操作の後、ある整数 X を選んで、ai=X となる i の個数を数えます。
うまく操作を行い、X を選ぶことで、この個数を最大化してください。

制約

・1≤N≤10^5
・0≤ai<10^5(1≤i≤N)
・aiは整数

入力

入力は以下の形式で標準入力から与えられる。

N
a1 a2 .. aN

出力

うまく操作を行い、X を選んだ時の ai=X なる i の個数の最大値を出力せよ。

解き方

以下を参考にしています。

https://img.atcoder.jp/arc082/editorial.pdf
https://atcoder.jp/contests/abc072/submissions/4582952?lang=ja

全体の流れ

aiに数を1足すか、1引くか、そのままにするかの操作を行い
Xとなる数字の個数を最大化する問題です。

数列の中からXを見つけ出すことに目がいきそうになりますが、
操作が3パターンしかないことに注目します。

aiからaNに対して3つの操作を行って
数字の出現回数を配列に保存しておき
その配列の中で最も数が大きいもの
（操作後に出現する回数の多い数）
がXとなるとともに
その配列に入っている数字
（操作後に出現する回数）が答えになります。

つまりこの問題は
「X」を出してから
「ai=X なる i の個数の最大値」を出すのではなく
3つの操作を行ったときの
数字の出現回数から
「ai=X なる i の個数の最大値」を出す、
という流れで解きます。
（答えを出すためにXを求める必要はない）

流れのまとめ
①aiからaNに対して3つの操作を全て行い、それぞれの数字の出現した数をカウントして配列に保存
②出現する数を保存してある配列で最も大きい数字を出力

実装する

まずは
①aiからaNに対して3つの操作を全て行い、それぞれの数字の出現した数をカウントして配列に保存
を実装してみます。

実装してみると以下のような形になると思います。

var N = Int32.Parse(Console.ReadLine());
var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
//操作した後の数字が出現する回数を保存する配列
//0≤ai<10^5なので1を足すことを考えて10^5+1+1
var array = new int[100002];
//操作した数をカウントする
for (int i = 0; i < N; ++i)
{
    //1を引く
    array[a[i] - 1]++;
    //何もしない
    array[a[i]]++;
    //1を足す
    array[a[i] + 1]++;
}

しかし、
ここで一つ問題があります。
0≤ai<105なので
もしaiが０だった場合

//1を引く
array[a[i] - 1]++;

をしたときに
Indexの外にはみ出てエラーになってしまいます。

これを避けるために
問題文の操作の値をそれぞれ１を足し、
「各 1≤i≤N に対し、ai になにもしないか 、1 足すか、2 足すか、の三つの操作」
というように書き換えます。

なぜこれで
元の操作をした場合と同じ答えになるのかは分からないのですが
（他の記事にも見当たらなかった）
入力例で試してみても
同じ答えになることが分かります。

入力例1
7
3 1 4 1 5 9 2
足す数 ****** ****** ****** ****** ****** ****** ******
-1 2 0 3 0 4 8 1
+0 3 1 4 1 5 9 2
+1 4 2 5 2 6 10 3
+2 5 3 6 3 7 11 4

上の表で
緑色の部分が操作を問題文通りの「-1,+0,+1」でしたときに同じ数字になる箇所、
赤色の部分が操作の数字に1を足した「+0,+1,+2」でしたときに同じ数字になる箇所です。

出現する場所は変わらず、
Xが1大きい値にはなりますが
（Xの値は問題の答えを出す上で特に必要ないので、変わっても問題ない。）
求めたい答えの値は変わらないことが分かります。

そのため、
各aiに操作を加えてカウントする部分の処理は
以下のように書き換えることができます。

var N = Int32.Parse(Console.ReadLine());
var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
//操作した後の数字が出現する回数を保存する配列
//0≤ai<10^5なので2を足すことを考えて10^5+2+1
var array = new int[100003];
//操作した数をカウントする
for (int i = 0; i < N; ++i)
{
    //何もしない
    array[a[i]]++;
    //1を足す
    array[a[i] + 1]++;
    //2を足す
    array[a[i] + 2]++;
}


②出現する数を保存してある配列で最も大きい数字を出力

最後に数字の出現回数を保存しておいた配列の中で
最も大きい値（＝答え）を求め、
出力すれば完了です。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var a = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).OrderBy(x => x).ToArray();
        //操作した後の数字が出現する回数を保存する配列
        //0≤ai<10^5なので2を足すことを考えて10^5+2+1
        var array = new int[100003];
        //操作した数をカウントする
        for (int i = 0; i < N; ++i)
        {
            //何もしない
            array[a[i]]++;
            //1を足す
            array[a[i] + 1]++;
            //2を足す
            array[a[i] + 2]++;
        }
        //出現回数が最も多い値を取り出す
        var ans = array.Max();
        Console.WriteLine(ans);
    }
}