Chapter 11

Day 10: Adapter Array

sugyan
sugyan
2021.03.09に更新

https://adventofcode.com/2020/day/10

いよいよアルゴリズムの問題っぽくなってきた。

part1

16
10
15
5
1
11
7
19
6
12
4

のような数値列の入力が与えられる。
これらを使って、0から最大値+3まで、差分が3以下になるように繋げていく必要がある、とのこと。

part1は、すべてを使って繋げていく場合に差分が1になる数と3になる数を掛け合わせたものを求めよ、というもの。
上の例だと、 0 -> 1 -> 4 -> 5 -> 6 -> 7 -> 10 -> 11 -> 12 -> 15 -> 16 -> 19 -> 22 と繋げていくことになり、差分17個、差分35個 現れるので、 35 が解となる。

考え方

単純に全入力をsortして順番に差分を数えていけば良いだけ。最後は最大値+3になるので差分3になるのは確定していて、0は入力には含まれないので考慮し忘れないよう注意。

part2

全部使う必要はないとして、前述のルール通り差分3以下で繋げていって最大値+3まで繋ぐ方法は何通りあるか数えよ、という問題。
前述の例だと、

(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 5, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 6, 7, 10, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 11, 12, 15, 16, 19, (22)
(0), 1, 4, 7, 10, 12, 15, 16, 19, (22)

8通りが存在するので、これが解となる。

考え方

ここはDP(動的計画法)を使っていく。
part1と同様に全入力をsortした数値列aに対し、DP[i]を「a[i]に到達する繋ぎ方の数」と定義する。
差分は3以下である必要があるので、a[i]の直前の数は a[i-3], a[i-2], a[i-1] までしか可能性が無い(全入力がuniqueであるという前提)。それらが差分3以内に収まっているかを調べて、可能なものだけ足し合わせればDP[i]となる。
DP[0]から順番に埋めていき、最後の要素が求める全組み合わせの数となる。
これも32bit整数では収まらないような数になるので注意。

解答例

from typing import List


class Solution:
    def __init__(self, inputs: List[str]) -> None:
        # `0`を含め 全入力を`sort`したものを使う
        self.adaptors = [0, *sorted([int(x) for x in inputs])]

    def part_1(self) -> int:
        diff1, diff3 = 0, 0
        # 直前の値との差分だけ確認して数えていけば良い
        for i in range(len(self.adaptors) - 1):
            diff = self.adaptors[i + 1] - self.adaptors[i]
            if diff == 1:
                diff1 += 1
            if diff == 3:
                diff3 += 1
        return diff1 * (diff3 + 1)

    def part_2(self) -> int:
        dp = [0] * len(self.adaptors)
        dp[0] = 1
        for i in range(len(self.adaptors) - 1):
            # 3つ前まで確認し、差分が`3`以下であれば次の要素に足し合わせる
            for j in range(3):
                if i >= j and self.adaptors[i + 1] - self.adaptors[i - j] <= 3:
                    dp[i + 1] += dp[i - j]
        return dp[-1]