Advent of Code 2024
ikd
面白かったのは、Day 5, Day 9, Day 11, Day 12, Day 13, Day 17, Day 20, Day 21, Day 24
難しかったのは、Day 5, Day 12, Day 14, Day 15, Day 17, Day 21, Day 24
ikdDay 1: Historian Hysteria
Part 1
ふたつの数列 A と B が与えられる。
- A の1番小さい値と B の1番小さい値の距離 (差の絶対値)
- A の2番目に小さい値と B の2番目に小さい値の距離
- …
の総和を求める問題。
解法
A, B をそれぞれソートして前から見る。
Part 2
- A[1] × (A[1] が B に現われる回数)
- A[2] × (A[2] が B に現われる回数)
- …
の総和を求める問題。
解法
あらかじめ B の各要素について (値, 出てくる回数) を hash map などで記録しておく。A の要素を順に見ていけば答えを求められる。
別解
A の要素数 (= B の要素数) ≦ 1000 だったので、各 A[i] について B の要素を全部見るようにしてもすぐに答えが出そう。
ikdDay 2: Red-Nosed Reports
Part 1
数列がたくさん与えられる。
次の条件を両方満たす数列の個数を求める問題。
- 単調増加 or 単調減少
- 隣接項の差の絶対値が 1 以上 3 以下
解法
各数列について条件をひとつずつ確かめる。
数列が単調増加/減少であるかどうかはソートした数列と元の数列を比べると分かる。
Part 2
各数列から 1 個まで要素を消せるとき、Part 1 と同じ条件を満たすものの個数を求める問題。
解法
どの要素を消すか全通り試す。削除後の数列に対して Part 1 の処理を流用して条件を満たすか判定する。
数列の個数 ≦ 1000, 数列の長さ ≦ 8 なので実行時間は短い。
ikdDay 3: Mull It Over
Part 1
文字列から mul(123,45) の形をした部分を全て抽出して計算結果 123 × 45 を合計する問題。
解法
mul(, 数値, ,, 数値, ) の順にパースするとかけ算に使うふたつの数を得られる。
Part 2
Part 1 での問題設定に加えて、文字列の中に命令 do() が出てきたら mul による計算を有効化し、命令 don't() が出てきたら無効化する。
解法
Part 1 のパース処理 → 失敗したら do() をパース → 失敗したら don't() をパース、というふうにしたら命令列を得られる。
計算が有効化されているかの状態を持って命令列を前から見ていって答えを求める。
別解
Part 1 も Part 2 も正規表現で matchAll のような機能を使って解けそう。
ikdDay 4: Ceres Search
Part 1
X, M, A, S からなる2次元の表が与えられる。
縦・横・斜めに XMAS が現われる回数を求める問題。
解法
X の位置 (i, j) を全通り試す。(i, j) から 8 方位を見た文字列が XMAS と一致する個数を数える。
Part 2
MAS が X の形になっている個数を求める問題。
M.M
.A.
S.S
解法
Part 1 と同じ要領で A の位置を全通り試して 4 方位を見る。
ikdDay 5: Print Queue
Part 1
「ページ番号 p は q より前にある」という条件 ★ がたくさん与えられる。
ページ番号の列 a = (a[1], a[2], ..., a[n]) について、上の条件をすべて満たすか判定する問題。
解法
全部のページ番号の組 (a[i], a[j]) に対して条件 ★ をチェックする。
Part 2
ページ番号の列 a = (a[1], a[2], ..., a[n]) を、条件 ★ を満たすように並びかえる問題。
解法
列の並びかえ n! 通りを全てためすのは時間がかかりそうなので別の方法を考える。
条件 ★ をもとにページ番号の列をソートするとよさそう。比較関数は
- 条件 ★ の中に (a[i], a[j]) という形のものがあるなら
< - それ以外なら
>
とした。
これでうまくいくのは入力が特別な形をしているから。サンプル入力の条件を図示すると全頂点間に辺が張られた DAG になっていた。
ChukwumaHello, can I ask why, you choose to use Seq, rather than List, if you still had to convert to a list in a later expression?
Thank you, your repo has a source of imagination and knowledge for me. Thank you making it open-source.
ikdThank you for your comment! The reason for using Seq is that, from the perspective of the solver function in this problem, a sequence is sufficient for calculating the answer without restricting the type to something more specific like a List or Array.
That said, for problems like Advent of Code, it’s perfectly fine to simplify things by converting everything to a List or Array if that makes the code easier to manage.
ChukwumaOkay, thank you. I tried retrofitting your code to OCaml. In OCaml, they only have list and not Seq.
It's been a good learning experience.
ikdDay 6: Guard Gallivant
Part 1
空きマス . と壁 # からなるグリッドと、スタート地点が与えられる。始めは上向きにまっすぐ進み、壁に当たる直前で時計回りに 90 度回転、右向きにまっすぐ……というのを繰り返す。最後は盤面外に出るのでそれまでに通ったマスの個数を求める問題。
解法
問題文の通りに 1 歩ずつ進む処理を実装する。
Part 2
グリッドを 1 マス壁に変えて「ループ」ができるようなマスがいくつあるか求める問題。
解法
壁に変えるマスを全通りためしてループができるか判定する。
ループがあるかどうかは
- グリッドでの位置
- 向き
の履歴を覚えておきながら Part 1 と同様の処理をすれば分かる。
ChukwumaHi ikd,
I enjoyed your Day 06 code, and I appreciate you pushing us to find the solution! My attempt at solving the challenge required some adjustments to the parsing logic. Your parsing function didn't work correctly with my input file (input.txt), likely due to differences in formatting. This is the function I used instead:
let parse (input: string) =
input.Split([| '\r'; '\n' |], System.StringSplitOptions.RemoveEmptyEntries)
|> Array.map (fun row -> row.Trim().ToCharArray())
Thanks again!
ChukwumaFor part 2 function, I re-wrote it to use mutability by applying hashsets and queues in it.
Thank you for your making your work open source.
ikdI also struggled with newline character issues when I was coding on Windows.
ikdDay 7: Bridge Repair
Part 1
292 = 11 ■ 6 ■ 16 ■ 20 という形の式がたくさん与えられる。■ に + or * を入れて等式を成立させられるか判定する問題。ただし、演算子の優先度は考えないで左から順に計算する。
11 + 6 * 16 + 20
= 17 * 16 + 20
= 272 + 20
= 292
解法
2^(■の個数) 通りの式を全部ためして計算結果が合うかチェックする。
Part 2
■ に入る演算子として || (文字列としての結合) も考えたときに等式を成立させられるか判定する問題。
6 * 8 || 6 * 15
= 48 || 6 * 15
= 486 * 15
= 7290
解法
Part 1 とほとんど同じ。|| の演算は toInt(toString(L) + toString(R)) のように実装できる。
ikdDay 8: Resonant Collinearity
Part 1
. と [0-9A-Za-z] からなる 2次元の表が与えられる。. 以外の文字はアンテナを表している。
同じ種類のアンテナの組 P, Q について
- P への距離 = (Q への距離) × 2 となる位置
- (P への距離) × 2 = Q への距離 となる位置
に antinode が発生する。
全部のアンテナについて考えたときに antinode ができる位置の個数を求める問題。
例: 下図のようにアンテナ a がふたつあるとき、antinode は # の位置に発生する。
..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
..........
解法
antinode の位置は、一方のアンテナを対称中心として他方のアンテナを点対称に移動させた位置と同じ。
座標の計算は軸ごとに独立に考えられるので1次元の問題が解ければよい。ふたつのアンテナの座標をそれぞれ a, b とすると antinode の座標は 2b - a と計算できる。
Part 2
Part 1 から antinode の発生する位置が変わる。
同じ種類のアンテナの組 P, Q について、直線 PQ 上の格子点に antinode が発生する。
Part 1 と同じ例を使うと antinode は # の位置とアンテナ a と被る位置の合計 5 箇所に現われる。
..........
...#......
..........
....a.....
..........
.....a....
..........
......#...
..........
.......#..
解法
再び1次元で考えれば十分。アンテナの座標を a, b とすると、antinode の座標は 初項 a, 階差 b - a の数列の各項と一致する。
感想
問題文がむずかしかった。
ikdDay 9: Disk Fragmenter
Part 1
ディスクの各ブロックが下図のように
- ファイル ID の塊
- 空きスペースの塊
の並びになっている。
後ろのファイルブロックから順に、一番左の空きブロックに移すことを繰り返す。最終的なディスクの状態を求める問題。
ブロック数 ≦ 200000
[
'0', '0',
'.', '.', '.',
'1', '1', '1',
'.', '.', '.',
'2',
'.', '.', '.',
'3', '3', '3',
'4', '4',
]
例：4 を 2 つ移動したあとのディスクはこうなる
[
'0', '0',
'4', '4', '.',
'1', '1', '1',
'.', '.', '.',
'2',
'.', '.', '.',
'3', '3', '3',
'.', '.',
]
解法
最左の空きブロックの位置 left を管理しながら、ディスクを後ろから見ていく。いま見ている位置にファイルがあるなら、left の空きブロックと交換、次の空きブロックが見つかるまで left を増やす、というふうにする。線形で動く。
Part 2
Part 1 ではファイルはブロックごとに動かせたが、塊をまとめて動かすことしかできない場合の問題。
解法
ファイルの塊ごとに、それが収まるような空きスペースの塊を先頭から検索する。見つかったら交換。最悪計算量は2乗になるけど実行してみたら 60 秒ほどで答えを求められた。
別解
次の連想配列を管理すれば、空きスペースの検索や更新を O(logN) でおこなえる。
- キー: 空きスペースの塊の長さ
- 値: その塊たちの位置の集合
- 最小値を取りだせる必要があるので priority queue や sorted set を使う
ikdDay 10: Hoof It
Part 1
二次元グリッドが与えられる。各マスには高さが 0 〜 9 の値で決まっている。
隣り合うマスのうち自分より高さが 1 大きいマスに移動できる。高さ 0 のマスからスタートして辿りつける高さ 9 のマスの個数を求める問題。
解法
- 頂点: グリッドのマス
- 辺: 移動可能な隣合ったマスの組
として有向グラフ上で DFS や BFS をする。
Part 2
高さ 0 のマスから高さ 9 のマスに至る経路数を求める問題。
解法
通ってきたマスの履歴を持って Part 1 と同じ要領で解ける。
ikdDay 11: Plutonian Pebbles
Part 1
非負整数の書かれた石がいくつかある。まばたきするたびにそれぞれの石が一斉に次の変化をする。
- 石に書かれた数が 0 ならば 1 になる
- それ以外の場合、石に書かれた数の桁数が偶数ならば石がふたつに分かれる。それぞれの石には左半分の数、右半分の数が書かれる
- 例: 123456 → 123, 456
- それ以外の場合、石に書かれた数が 2024 倍になる
25 回まばたきをしたあとの石の個数を求める問題。
解法
問題文の通りにシミュレーションをする。
Part 2
75 回まばたきをしたあとの石の個数を求める問題。
解法
Part 1 と同じようにシミュレーションすると、答えになる石の個数が多くてプログラムの実行が全然終わらない。
石に書かれた数の種類数を調べると (石の個数より) だいぶ少ないことが分かる。そこで、(石に書かれた数, 個数) の連想配列を持ってシミュレーションすると答えを求められた。
ikdDay 12: Garden Groups
Part 1
二次元のグリッドがいくつかの領域に分かれている。それぞれの領域の面積・周長を求める問題。
AAAA
BBCD
BBCC
EEEC
見やすく描いた図
- 領域 A
- 面積 4
- 周長 10
- 領域 B
- 面積 4
- 周長 8
- ...
+-+-+-+-+
|A A A A|
+-+-+-+-+ +-+
|D|
+-+-+ +-+ +-+
|B B| |C|
+ + + +-+
|B B| |C C|
+-+-+ +-+ +
|C|
+-+-+-+ +-+
|E E E|
+-+-+-+
解法
領域の面積 = マス数は DFS や BFS で求められる。
領域の周長は、領域内の各マスについて上下左右に隣り合ったマスを見ると分かる。隣のマスも領域に含まれるなら +0, 含まれないなら +1 として合計する。
Part 2
領域の辺の数を求める問題。
上の例だと
- 領域 B
- 辺数 4
- 領域 C
- 辺数 8
- ...
解法
辺数のかわりに頂点数を求める。
https://atcoder.jp/contests/abc191/tasks/abc191_c とだいたい同じ。下図の領域Aの扱いに気をつける。
AAAAAA
AAABBA
AAABBA
ABBAAA
ABBAAA
AAAAAA
ikdDay 13: Claw Contraption
Part 1
ふたつのボタン A, B がある。また、ふたつの変数 X, Y があり初めは両方 0 である。
ボタン A を 1 回押すと X, Y が一定量増える。ボタン B についても同じ。
目標となる X, Y の値が与えられる。ボタン A, B を何回か押して目標を達成できるか判定、可能ならそれぞれのボタンを押す回数を求める問題。Part 1 では 100 回以下であることが保証されている。
X, Y の目標値 ≦ 20000
解法
ボタン A を押す回数 0 〜 100, ボタン B を押す回数 0 〜 100 を全通り試す。
Part 2
Part 1 と同じ設定で、X, Y の目標値が 10000000000000 以上もありうる場合の問題。
解法
ボタン A を押す回数を s, ボタン B を押す回数を t とすると、X, Y の目標値に関する条件は
という形の連立方程式で書ける。たとえば2×2の行列・逆行列を使って解を求められる。
ikdDay 14: Restroom Redoubt
Part 1
二次元グリッド上にロボットがたくさんいる。
各ロボットは縦方向、横方向の速度を持っていて1秒ごとに移動する。グリッドをはみ出た分はトーラスの要領で反対側の端から現われる。
100秒後のロボットたちの位置を求める問題。
解法
問題文の通りにシミュレーションする。
Part 2
ロボットたちの位置がクリスマスツリーの形になる最初の秒数を求める問題。
解法
クリスマスツリーの形について具体的な情報が与えられないので色々がんばる。
ロボットたちを 1000 秒くらい動かしてみると、グリッドの幅を w, 高さを h として
- 時刻 ■, ■ + w, ■ + 2w, ■ + 3w, ...
- 時刻 ▲, ▲ + h, ▲ + 2h, ▲ + 3h, ...
のタイミングで模様らしきものを描いていることが分かる。これらが一致する時刻にクリスマスツリーが現われることを祈ろう。
式にすると
得られたクリスマスツリー
@ @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @
@ @
@ @
@ @
@ @ @
@ @ @
@ @ @@ @
@ @ @@@ @ @
@ @@ @@@@ @ @ @
@ @ @ @@@@@@@@ @
@ @ @ @ @@ @@@@@@@@@ @
@ @ @ @@@@@@@@@@@@@ @ @
@ @@ @@@@@@@@@@@@@@ @ @
@ @@@@@@@@@@@@@@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @@@@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @@@@@@@@@@@@@@@@@@@@@@ @
@ @@@@@@@@@@@@@@@@@@ @ @
@ @ @ @@ @@@@@@@@@@@@@@ @
@ @ @@@@@@@@@@@@@ @
@ @@ @@@@@@@@@ @ @
@ @ @ @@@@@@@@ @
@ @@ @@@@ @
@ @ @@@ @
@ @@ @ @
@ @ @ @ @
@ @ @
@ @
@ @
@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @
Day 15: Warehouse Woes
Part 1
下図のような盤面が与えられる。
-
@ロボット -
O箱 -
#壁
また、ロボットの移動列が与えられる。ロボットの移動先に箱がある場合は箱がその方向に押される。壁があったら止まる。全部の移動を処理した後の盤面を求める問題。
##########
#..O..O.O#
#......O.#
#.OO..O.O#
#..O@..O.#
#O#..O...#
#O..O..O.#
#.OO.O.OO#
#....O...#
##########
解法
こういう状態からの左移動を考える。
...OOO@..
O が連続する部分を求めて、まとめてずらすと処理できる。他の方向への移動も同様にできる。
Part 2
Part 1 の盤面が横に2倍されて箱が「幅」を持つようになる。ロボットの移動を処理した後の盤面を求める問題。
####################
##....[]....[]..[]##
##............[]..##
##..[][]....[]..[]##
##....[]@.....[]..##
##[]##....[]......##
##[]....[]....[]..##
##..[][]..[]..[][]##
##........[]......##
####################
解法
左右への移動については Part 1 と同じ。上下は同じようにはいかなそう。
上への移動を考える。
....#. (1)
....[] (2)
.[][]. (3)
..[].. (4)
..@... (5)
ロボットの真上にある (4) の箱が動くかどうかは、(3) の箱が動くかどうかで決まる。(3) の箱は (2) の箱が動くかどうかで……というように再帰的に決まる。
感想
Part 2 がむずかしかった。
ikdDay 16: Reindeer Maze
Part 1
2次元グリッド上でスタート S からゴール E まで行く最小コストを求める問題。
はじめ東を向いており、90度回転にコスト 1000, 正面に1マス進むのにコスト 1 かかる。
###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############
解法
頂点を (行, 列, 向き) としたグラフで Dijkstra をする。
(i, j, 東) から伸びる辺は
- コスト 1 の (i, j+1, 東)
- コスト 1000 の (i, j, 北)
- コスト 1000 の (i, j, 南)
Part 2
スタートからゴールへの最短経路 (の少なくともひとつ) に含まれるマス数を求める問題。
解法
- スタートからマス x への最短距離を d1[x]
- 逆辺を張ったグラフにおける、ゴールからマス x への最短距離を d2[x]
とおく。
マス x が条件を満たすかは d1[x] + d2[x] がスタートからゴールへの最短距離と等しいかどうかで判定できる。
感想
Part 2 はよく見る問題
ikdDay 17: Chronospatial Computer
Part 1
レジスタ A, B, C の初期値と opcode, operand からなるプログラムが与えられる。opcode は 0 から 7 まであり、レジスタの内容を書き換えたり出力したりプログラムの位置を指定して jump したりする。
プログラムが出力する数列を求める問題。
解法
問題文の通りにがんばって実装する。
Part 2
プログラムの出力がプログラム自身になるようなレジスタ A の初期値を求める問題。
解法
与えられたプログラムを疑似コードにしてみる。
do
B = A & 0b111
// B をいろいろ更新する
print (B & 0b111)
A = A >> 3
while A != 0
A を 3 ビットずつの塊に分けたときの前から k 番目の塊が、プログラムの出力の後ろから k 番目の値に大きく影響を与えそう。
そこで、プログラムの出力とプログラム自身の suffix が一致する状態を保って A を 3 ビットずつ決めていくような探索をすると正解を得られた。
感想
Part 2 むずかしい。
ikdDay 18: RAM Run
Part 1
はじめ全部のマスを通れる2次元グリッドを考える。時刻 t = 1, 2, ... の順にマス (X[t], Y[t]) に岩が落ちて通れなくなる。
t = 1024 まで経過したときグリッドの入口 = 左上から出口 = 右下に移動するための最短距離を求める問題。
解法
左上のマスから BFS をする。
Part 2
入口から出口までの経路がなくなるような最小の時刻 t を求める問題。
解法
特定の時刻における到達可能性も BFS で分かる。
求める値を T とおくと t < T では出口に辿りつける、T ≦ t では出口に辿りつけない、となって t に関して単調なので二分探索をすると T が決まる。
ikdDay 19: Linen Layout
Part 1
パターン文字列が複数と、目標となる文字列 T が与えられる。
パターン文字列を組み合わせて T を作れるか判定する問題。2回以上使ったり、使わないパターンがあってもよい。
解法
たとえば T = abracadabra でパターンに ab があれば、T の先頭から ab を除いた T' = racadabra について再帰的に問題を解く。これをすべてのパターンで試すと答えが求められる。
Part 2
T を作るパターンの組み合わせ方の総数を求める問題。
解法
Part 1 の処理を数え上げに変えてメモ化再帰にすると解ける。
解法
素直な DP の問題。
ikdDay 20: Race Condition
Part 1
2次元グリッドとスタート S, ゴール E が与えられる。マス # は壁で通れない。
スタートからゴールまでの最短距離を D とおく。壁を 1 個だけ壊せるとき、スタート → ゴール の距離が D より 100 以上短くなるような壁の壊し方がいくつあるか求める問題。
###############
#...#...#.....#
#.#.#.#.#.###.#
#S#...#.#.#...#
#######.#.#.###
#######.#.#...#
#######.#.###.#
###..E#...#...#
###.#######.###
#...###...#...#
#.#####.#.###.#
#.#...#.#.#...#
#.#.#.#.#.#.###
#...#...#...###
###############
解法
それぞれの壁を壊した状態でスタートから BFS をして最短距離を求めて、D より 100 以上小さくなたかチェックする。
Part 2
好きなマスを選んでそこから 20 個まで壁を壊せるとき、距離を 100 以上短くできるマスの選び方・壁の壊し方がいくつあるか求める問題。
解法
(距離 20 以内にある) マス P からマス Q まで壁を壊してショートカットした場合に、スタートからゴールまでの最短距離 D をどれだけ節約できるか求めよう。
(壁を壊していない状態での) スタートからマス ■ への最短距離を d[■] と書く。いま P から Q までの壁は無いので d' を P, Q のマンハッタン距離として、スタートから P, 壁を壊してできた道 と辿ると Q までの距離 d[P] + d' を達成できる。よって全体では d[Q] - (d[P] + d') だけ節約できる。値が負になるのは遠回りした場合に対応する。
感想
Part 2 で壁の壊し方のルールを読み解くのがちょっとむずい。
ikdDay 21: Keypad Conundrum
Part 1
テンキーのキーパッドがある。これらのキーの並び (例: 029A) が与えられる。この順にキーを押したいが直接テンキーを触ることはできない。
+---+---+---+
| 7 | 8 | 9 |
+---+---+---+
| 4 | 5 | 6 |
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| 0 | A |
+---+---+
矢印のキーパッドを通じて別のキーパッドを操作できる。これがテンキーまでに3つ挟まっている。つまり、人間 → 矢印キー → 矢印キー → 矢印キー → テンキー という状況で、目的を達成するために人間がキーを押す最小回数を求める問題。
^, <, v, > を押すと (ひとつ先のキーパッドにおける) カーソルの移動、A を押すとカーソル位置にあるキーを押すことができる。全部のキーパッドでカーソルは最初 A の位置にある。
空白になっているキー
-
1の下 =0の左 -
^の左 =<の上
にカーソルが乗るような移動はできない。
+---+---+
| ^ | A |
+---+---+---+
| < | v | > |
+---+---+---+
たとえば
-
029Aを押すためには -
<A^A>^^AvvvAを押す必要があり、これを押すためには -
v<<A>>^A<A>AvA<^AA>A<vAAA>^Aを押す必要があり、これを押すためには -
<vA<AA>>^AvAA<^A>A<v<A>>^AvA^A<vA>^A<v<A>^A>AAvA^A<v<A>A>^AAAvA<^A>Aを押す必要がある
解法
現在のカーソル位置から与えられたキーを押すために、人間がキーを押す最小回数が分かれば十分。
029A の例だと
-
A→0 -
0→2 -
2→9 -
9→A
と分けて考えてよい。
ふたつのキーの間の移動は縦方向が先か横方向が先かの自由度がある。本当はジグザグの移動もあるけど最適にならなそうなので無視しよう。
たとえば 3 → 7 だと ^^<< か <<^^ の2通りある[1]。どちらが最適か (人間が押すべきキー数が少なくなるか) は、< → ^ や ^ → < の移動順について再帰的に考えると分かる。
Part 2
テンキーまでに矢印のキーパッドが26個挟まっているという設定。
解法
Part 1 をメモ化再帰にする。
感想
空白キーの位置を通れないのがちょっとめんどうだけど面白い。
-
この例だと
<<^^が最適と分かる ↩︎
ikdDay 22: Monkey Market
Part 1
数値がたくさん与えられる。それぞれの数値に暗号化処理を 2000 回おこなった後の値を求める問題。暗号化は剰余や xor などの計算からなる。
解法
問題文に書いてある手順通りに暗号化を実装する。
Part 2
暗号化の関数を f と書く。入力で与えられる各数値 x について暗号化を 0 回, 1 回, ..., 2000 回適用した値 x % 10, f(x) % 10, f(f(x)) % 10, ... の階差の列
f(x) % 10 - x % 10f(f(x)) % 10 - f(x) % 10- ...
を考える。
4つの数値 a, b, c, d を指定できる。階差の列に初めて a, b, c, d が現われる位置を p とすると、もとの列における p+1 項目の値だけ点数を得られる。そのような p が存在しなければ点数は 0 になる。入力で与えられたそれぞれの数値にわたる点数の合計の最大値を求める問題。
解法
それぞれの階差数列について幅 4 の window: (d[i], d[i+1], d[i+2], d[i+3]) を前から見ていき、連想配列に
- キー: (d[i], d[i+1], d[i+2], d[i+3])
- 値: もとの列における i+4 番目の値
という組を記録しておく。ただし、同じキーに対する値の上書きはしない。
この連想配列たちをひとつずつ検索すれば、固定した a, b, c, d に対して点数の合計を計算できる。
a, b, c, d を動かして合計点数の最大を取ろう。それぞれ -10 以上 10 以下まで考えれば十分。
感想
Part 2 の計算量がけっこう大きめ。これでよかったのか感がある。
ikdDay 23: LAN Party
Part 1
無向グラフが与えられる。サイズ 3 のクリークをすべて求める問題。
頂点数 ≦ 4000
解法
頂点の三つ組を全て試すのは計算量的にちょっときびしい。
入力を解析すると頂点の次数 ≦ 13 と小さめなのでこれを利用する。
クリークに含まれる頂点 x を全通り試そう。2 つ目の頂点 y は x に隣接するものを全部試す。最後の頂点 z は y に隣接するもののうち、辺 (x, z) が存在するものとして求められる。
Part 2
最大サイズのクリークを求める問題。
解法
サイズ k のクリークを全列挙 → サイズ k+1 のクリークを全列挙、というように k を大きくしていく。初めてサイズ k+1 のクリークが存在しなくなったときの k に対するクリークが答えになる。
例として k = 3 を考える。クリークを構成する頂点たちを x, y, z とする。頂点 x に隣接する頂点 w について、辺 (y, w), 辺 (z, w) が両方存在するとき x, y, z, w がサイズ 4 のクリークになる。
感想
Part 2 は有名問題なので検索すると色々アルゴリズムがありそう。
ikdDay 24: Crossed Wires
Part 1
0, 1 の値を持つ変数 x00, x01, ..., x44, y00, y01, ..., y44 が与えられる。また
- ● AND ▲ → ■
- ● OR ▲ → ■
- ● XOR ▲ → ■
の形のゲートがたくさん与えられる。ゲートたちの終端にある変数 z00, z01, ..., z45 の値を求める問題。
解法
ゲートを処理するたびに出力先の変数の値が確定する。値の確定した変数 (とその値の組)、未処理のゲートを管理してトポロジカルソートっぽく更新していく。
Part 2
x00, x01, ..., x44, y00, y01, ..., y44 の初期値は無視する。
ゲートの組を 4 つ選んで出力先を交換することで、45 ビット整数 x, y の和が z に入るような回路 (加算器) にする問題。
解法
ビットを下位から z[0], z[1], ... の順に見て初めて z[*] を求める回路が誤りになるものを求めよう (★) 。
z[k] が誤りだとする。z[k] の計算途中に出てくるゲートたちのどれかが出力先を交換する必要がありそう。交換対象は次のようにして分かる。実際に出力先を入れ替えてみて (★) の処理を実行する。元々と同じか早いタイミングで (下のビットで) 誤りが見つかったら却下、そうでなければ交換対象として採用とする。
順番に回路を修正していくことで全体で正しい加算器になる。
z[k] の回路が正しいか (誤りか) 判定する方法を考える。入力で与えられたゲートたちから z00, z01, z02, z03 を論理式にしてみると規則性が見える。これに当てはまるときに正しい回路であるというふうにした。
- z00:
(x00)xor(y00) - z01:
((x00)and(y00))xor((x01)xor(y01)) - z02:
((((x00)and(y00))and((x01)xor(y01)))or((x01)and(y01)))xor((x02)xor(y02)) - z03:
((((((x00)and(y00))and((x01)xor(y01)))or((x01)and(y01)))and((x02)xor(y02)))or((x02)and(y02)))xor((x03)xor(y03))
感想
Part 2 はグラフ描画ツールを使って目で解く方法もあるかも。
ikdDay 25: Code Chronicle
Part 1
錠を表すシルエットと鍵を表すシルエットがたくさん与えられる。錠と鍵の組のうち形が合うもの (# が重ならないもの) の個数を求める問題。
たとえば下図の錠1は鍵1と合わないが鍵2とは合う。
錠1
#####
.####
.####
.####
.#.#.
.#...
.....
鍵1
.....
#....
#....
#...#
#.#.#
#.###
#####
鍵2
.....
.....
.....
#....
#.#..
#.#.#
#####
解法
全部の錠・鍵の組について # が重なるかをチェックする。