ABC326

AtCoder ABC

総評

A、Bのみ解けた

2UP3DOWN

これは問題の通りに分岐させれば良いだけ

x, y = map(int, input().split())

a = abs(x - y)

if x < y:
    if a > 2:
        print('No')
    else:
        print('Yes')
else:
    if a > 3:
        print('No')
    else:
        print('Yes')

326-like Numbers

全探索する。具体的には、Nから初めて919までを試してみれば良い。各桁ごとの数値に分割する方法は色々あると思う。

N = int(input())

for i in range(N, 920):
    first = i // 100
    second = (i // 10) % 10
    third = i % 10

    if first * second == third:
        print(i)
        break

Peak

解けず。累積和な気がしたが、どうも違うようだ。

コンテスト中の考察

  1. 配列countを作成する。これは座標を擬似的に模したもの。つまり、count[0] ~ count[max(A)]の配列をとる。この配列は全ての要素を0で初期化する。 入力配列Aを読み込み、count[Ai]の値をインクリメントする。 こうすることで、どの座標にいくつプレゼントがあるかが記録される。
  2. 上記のcount配列に対して累積和の配列を作成する。これはPythonであればitertools.accumlateで作成できる。
  3. 累積和配列に対して区間ごとのmaxを調べていく
from itertools import accumulate

n, m = map(int, input().split())
a = list(map(int, input().split()))

maxi = max(a)
l = [0] * (maxi + 1)

for i in a:
    l[i] += 1

acc = [i for i in accumulate(l)]

ans = 0
for i in range(maxi - m):
    ans = max(ans, acc[i+m]-acc[i])

print(ans)

上記ではダメな理由

単純に、Aiの取り得る最大値が10 ^ 9のため、count配列作成時にO(10 ^ 9）の計算量となるため、TLEになる。 与えられた制約からすると、O(N)くらいじゃないと厳しい。

解説ACをする

尺取り法というものを利用すると良いらしい

n,m = map(int,input().split())
a = list(map(int,input().split()))

a.sort()
a.append(9000000000000)

res = 0
r = 0
for l in range(0,n):
    while a[r] < a[l]+m:
        r += 1
    res = max(res,r-l)

print(res)