ABC050 C - Lining Up

備忘録

問題

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

# import fractions

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)
# lcm = lambda x, y: (x * y) // fractions.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 = collections.Counter(A)

    for k, v in cnt.items():
        if k == 0 and v != 1:
            print(0)
            exit()
        elif k != 0 and v != 2:
            print(0)
            exit()
    print((2 ** (N // 2))%MOD)


if __name__ == '__main__':
    main()

考え方

証言された絶対値の数をそれぞれ数えて置き、
証言の絶対値の数で並ぶことが出来るか否かを判定する。

自分の左に並んでいた人数と自分の右に並んでいた人数の差の絶対値を、
実際にシミュレートしてみると以下のような形になる。

# 例：5人並んでいる場合
[4, 2, 0, 2, 4]
# 例：8人並んでいる場合
[7, 5, 3, 1, 1, 3, 5, 7]

N人並んでいる場合には、
存在する絶対値はN//2個あり、
かつ、絶対値はそれぞれ2個ずつ存在する。
(Nが奇数の場合には0が1個だけ存在する）

以上のことがわかれば、各絶対値の存在している数を数えて置き、
条件と一致するか否かを全探索することでありうる並び方か否かを判定できる。

最後に並び方が何通りあるかについては、
各絶対値はそれぞれ2つの場所に存在することが出来るので、
2 ** 絶対値の数通り存在する。
(10**9 + 7の余りを出力することを忘れないこと）