CODE FESTIVAL 2017 qual C B - Similar Arrays

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time


# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


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


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


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
# MOD = 998244353
INF = 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 % 2 == 0:
            cnt += 1

    print(3 ** N - 2 ** cnt)


if __name__ == '__main__':
    main()

考え方

整数列Aと「似ている」が成り立つ整数列Bの数は、
3 ** N個存在します。
（N個の要素を持った配列で各要素がA-1, A, A+1の３通りを取ることができるため）

このうち、全ての項の積が奇数となる配列を減算します。
項の積が奇数となるためには、全ての項が奇数である必要があります。
整数列Aのある項が奇数の場合には、その項は一通りの選択肢しかありませんが、
項が偶数の場合にはAi + 1, Ai - 1の二通りの選択肢を取ることが出来ます。

あとは何通りの選択肢があるかを計算するだけなので、
2 ** 偶数の数が整数列Bの全ての積の項が奇数となる数となります。
以上から3 ** N - 2 ** 偶数の数(似ている整数列の総数 - 全ての項の積が奇数となる似ている整数列の総数)で回答を求めることが出来ます。