典型90【024 – Select +／- One（★2）】をpython解説

AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。

今回は、その内、の24問目である「024 – Select +／- One（★2）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！

問題名　【024 – Select +／- One（★2）】

024 – Select +／- One（★2）

考察

K回の操作でピッタリできる状況は、たくさんありそうなので、K回の操作で、ピッタリ実行できない状況について考えます。

K回の操作できないパターン
1, Σabs(A[i]-B[i]) > K
2, K-1,3,5・・・回の操作ですべての数が一致している

の2パターンが考えられます。

パターン1

パターン1については、それぞれの差分をとって、差分がK以上ならNOと出力すればよいです。

パターン2

パターン2について、

1. K回の操作で一致させるには、K-1回の操作時には、差が1であることが必要です
2. K-1回の操作で差が1にするには、K-2回の操作時に差が0 or 2である必要があります。
   (K-2回目時点で、差が0であっても、K-1回目の操作で1にすることができるから)
3. K-2回の操作で差を0 or 2にするには、K-3回目の操作時に・・・

となります。つまり、初めて差分が0になる操作回数とKの偶奇が揃っている必要があります。

よって、今回求める条件は、
Σabs(A[i]-B[i]) < K かつ Σabs(A[i]-B[i])%2 == K%2
であるので、その内容を実装していきます

コード

import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


N,K = MI()
A = LI()
B = LI()

sa = 0
for i in range(N):
    sa += abs(A[i]-B[i])
    
if sa <= K and sa%2 == K%2:
    print("Yes")
else:
    print("No")

まとめ

前の問題【022 – Cubic Cake（★2）】
次の問題【026 – Independent Set on a Tree（★4）】