ABC069 C - 4-adjacent

備忘録

問題

atcoder.jp

回答

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()

    cnt = 0
    for a in A:
        if a % 4 == 0:
            cnt += 1
        elif a % 2 == 0:
            cnt += .5
    print('Yes' if N // 2 <= int(cnt) else 'No')


if __name__ == '__main__':
    main()

考え方

n番目とn+1番目の積が4の倍数となり得るのは、
n番目またはn+1番目が4の倍数の場合と、
n番目とn+1番目が両方とも2の倍数の場合。
それらのケースを数え、目標を達成できるか否かを判定する。

---

目標を達成する数列にするためには、
１からN番目までの各整数の間に4または２の倍数が並ぶ必要がある。

# 4の倍数とそれ以外の値が交互に並んでいる場合、
# 目標を達成できる
[1, 4, 3, 4, 7, 4, 7, 8, 1]

# 4の倍数の前後以外は、2の倍数が並んでいる場合、
# 目標を達成できる
[1, 4, 1, 4, 2, 2, 6, 6]

２つの積が４の倍数となり得るのは、上記で上げた２パターン。
n番目またはn+1番目が4の倍数の場合には、
どちらか一方が4の倍数であれば、片方の値は問わない。
つまり、n番目が4の倍数の場合には、
n-1番目とn+1番目がどのような数字であっても、積は必ず４の倍数となる。

２の倍数は整数が２つ揃って初めて１つの場所を４の倍数にすることが出来る。
つまり、n-1番目またはn+1番目のどちらかが２の倍数である必要があり、
１つだけでは積で４の倍数を作ることが出来ない。
そのため、２の倍数の場合には+0.5カウントとして扱った。

あとは各整数の間に、４の倍数にすることができる整数を並べることが出来れば、
目標を達成できるので、N // 2 <= int(上記で求めたパターンの数)で成否を判定した。