Toshusai blog

知識の保管庫

【AtCoder】ABC072C解説

時間制限 : 2sec / メモリ制限 : 256MB

配点 : 300 点

問題文 長さ N の整数列 a1,a2,…,aN が与えられます。

各 1≤i≤N に対し、ai に 1 足すか、1 引くか、なにもしないかの三つの操作からどれか一つを選んで行います。

この操作の後、ある整数 X を選んで、ai=X となる i の個数を数えます。

うまく操作を行い、X を選ぶことで、この個数を最大化してください。

制約
1≤N≤105
0≤ai<105(1≤i≤N)
ai は整数
入力
入力は以下の形式で標準入力から与えられる。

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

自分の考え

1降順ソートしてから先頭から見る
2今のai+2までのaiの個数を数える
3aiの連続が途切れる度2を繰り返す
これで2の最大が出力になる。 ちょっと上手く説明できないのでコードで。

n = int(input())
a_n = list(map(int, input().split()))
a_n.sort()
a_n.reverse()
def check(idx):
    global a_n
    base = a_n[idx]
    count = 0
    dif = 0
    while dif <= 2:
        idx += 1
        count += 1
        if(idx == n):
            return count
        dif = base - a_n[idx]
    return count
 
ans = 1
i = 0
c = check(i)
tmp = a_n[0]
while(i != n):
    if(tmp != a_n[i]):
        tmp = a_n[i]
        c = check(i)
    if(ans < c):
        ans = c
    i += 1
print(ans)

なんとも冗長なコードになってしまった。 ここでコード長最短ACの方のコードを見てみよう。

c=[0]*10**5;input()
for i in map(int,input().split()):
    c[i]+=1
print(max([sum(c[i:i+3]) for i in range(10**5)]))

たった4行である。 入力の最大個数である105の長さの配列を宣言し、入力のそれぞれの値に対応するインデックスにその値がいくつあるのかカウントしている。 最後に3つごとにスライスし、その合計の最大を出力する。 非常に美しいコードだ。

メモ

Pythonでセミコロンを使うと1行に2行分書けることを初めて知った。最初の入力Nは使う必要がないので、最初の行の後ろに書いたのだろう。