Advent of Code 2022
ikd
25 問解いた。
- とくに難しかったのは Day 17, Day 19, Day 22
- 比較的とっつきやすいのは Day 1, Day 3, Day 4, Day 6, Day 8, Day 9, Day 12, Day 13
ikdDay 25
10 進数と 5 進数を変換する問題。ただし
解法
3 進数の場合の問題が https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0306 にあるので同じようにして解ける。
ikdDay 22
2 次元のグリッド上で
- 時計回りに 90 度回転
- 反時計回りに 90 度回転
- N マス直進
- 「壁」のマスには進めない
からなる命令列を処理して、最後にいる位置と向きを求める問題。
解法
グリッドの高さ (幅) ≦ 250, N ≦ 100, 命令の個数 ≦ 4000 程度なので、計算量はとくに気にせず 1 マスずつ動かせばよい。
Part 1
グリッドの上と下、右と左がトーラスのようにつながっている設定。
行番号 % グリッドの高さ や 列番号 % グリッドの幅 をして解く。
Part 2
グリッドを展開図とみなして、うまく折りたたんでサイコロのような立方体にした設定。😵💫
立方体の面をまたぐ移動をすると (展開図で見たときの) 向きが変わりうるので気をつける。
ikdDay 24
2 次元のグリッド上でスタートからゴールまで行く最短の時間を求める問題。
各マスは自由に通れる空きマスか通れない blizzard のマス。プレイヤーは毎分隣り合った上下左右のマスに動くかいまのマスに留まる。
- blizzard は上下左右の向きが決まっていて毎分その方向に 1 ずつ動く
- blizzard はグリッドの端をはみ出すと逆側から出てくる (トーラスのように)
グリッドの高さ ≦ 30, グリッドの幅 ≦ 130
解法
t 分で行けるマスが分かっていれば t + 1 分で行けるマスも分かる。
無限ループ：1 分で行けるマスを列挙 → 2 分で行けるマスを列挙 → ... をゴールのマスが出てきた段階で打ち切ればよい。
実際に実行してみると 300 ステップ程度でゴールにたどり着く。
(今回与えられたマップでは答えが小さめに収まったけど、最悪ケースではどうなるんだろう？ ゴールにたどり着ける ⇒ 所要時間は [(グリッドの高さ) × (グリッドの幅)]^2 以下、は言えそう)
Part 1
スタート → ゴール
Part 2
スタート → ゴール → スタート → ゴール の合計時間
Part1 とほとんど同じ
ikdDay 19
4 種類の鉱石 (ore, clay, obisidan, geode) と対応する 4 種類のロボット (ore robot, clay roboto, obsidian robot, geode robot) がある。◯◯ロボット 1 台につき 1 分ごとに鉱石◯◯が増える。
各ロボットを作るのに必要な鉱石の個数が入力で与えられる (図の a, b, c, d, e, f) 。毎分取れる行動は、なにもしないか鉱石を消費してロボットをどれか 1 台作ること。はじめ ore robot 1 台のみを持っている。N 分後に持っている geode の個数を最大化する問題。
解法
毎分取れる行動をぜんぶ試して再帰的に全探索する。再帰の呼び出し回数は ≦ 5^N になる。
- なにもしない
- (鉱石が足りるなら) ore robot を作る
- (鉱石が足りるなら) clay robot を作る
- (鉱石が足りるなら) obsidian robot を作る
- (鉱石が足りるなら) geode robot を作る
Part 1
N = 24
N ≦ 20 程度ならすぐに実行が終わったが N = 24 になるときびしいので探索の枝刈りをする。
暫定的な答え、つまり真の答え以下となる値 M がわかっているとする (M は N 分後まで探索してわかった geode の個数で更新していく) 。現在の時刻以降で毎分 geode robot を作れたとして開始から N 分後に持っている geode の個数 m は (現在の geode, geode robot の個数から) 計算できる。m ≦ M ならば探索を打ち切ってよい。
実行時間は数秒で済む。
Part 2
N = 32
Part 1 と同じ。数十秒待つと実行が終わる。
より良い観点での枝刈りがあるかも。もしくは m を精度良く見積もるとか。
ikdDay 23
2 次元グリッド上にエルフが何人かいる。1 ラウンドで、エルフたちは自身の周り 8 マスに他のエルフがいるかどうかに応じて、上下左右いずれかに移動するかその場に留まる。移動先が他のエルフと被るとその場に留まる。
エルフの人数 ≦ 5000
解法
問題文に書いてある条件の通りに、関数 F: ラウンド開始時のエルフたちの位置リスト → ラウンド終了後のエルフたちの位置リスト を実装すればよい。
与えられたグリッドの外に出る移動も有効なことに気をつける。
Part 1
ラウンド 10 終了後にエルフたちを包含する最小長方形の面積を求める問題。
F を 10 回呼ぶ。F(F(F(F(F(F(F(F(F(F(▲))))))))))
Part 2
ラウンド t → ラウンド t + 1 でエルフたちが全員移動しないような最小の t を求める問題。
F を繰り返し呼んで
- ▲ == F(▲)
- F(▲) == F(F(▲))
- F(F(▲)) == F(F(F(▲)))
- ...
が初めて true になるところを調べる。
ikdDay 17
テトリスのような落ち物ゲーム。ピースの回転はない。段が揃っても消えることはない。
ピースの左右への移動操作は長さ 10000 程度のパターンを繰り返す。
N ピース落としたあとのピースが積もった高さを求める問題。
Part 1
N = 2022
単純にシミュレーションをする。
Part 2
N = 1000000000000
手計算で解く。
「1 ピース落としたときの高さの増分」の列を 3000 〜 4000 項ほど見ると周期的になっていそう。繰り返し部分の高さへの寄与をまとめて計算して答えを求める。
3, 2, 0, 1, 1, 0, 2, 0, 1, 1,
2, 1, 0, 2, 0,
2, 1, 0, 2, 0,
2, 1, 0, 2, 0,
...
Day 20
列 A = (1, 2, ..., N), B = (B[1], B[2], ..., B[N]) がある。
x = 1, 2, ..., N の順に A 内で x を B[x] だけ動かしたときの最終的な A を求める問題。B[x] > 0 のときは後ろ、B[x] < 0 のときは前に移動。端まで来たら反対側に移る。N の後ろは 1、1 の前は N のように。
(もとの問題文からここまで言い換えるパートがいちばん難しいかもしれない……)
N ≦ 5000
Part 1
-10000 ≦ B[x] ≦ 10000
A から x を消して、移動先に x を挿入する。off-by-one エラーに気をつける。
もしくは「ひとつ後ろ (ひとつ前) と swap」を |B[x]| 回繰り返してもよいはず。
Part 2
-10000000000000 ≦ B[x] ≦ 10000000000000
A は先頭と末尾がつながっているので B[x] % N のようにしてよく Part 1 と同じになる。
ikdDay 21
完全二分木が与えられる。
- 葉：数値
- 内部の頂点：演算子 (
+,-,*,/)
頂点数 ≦ 2500
Part 1
根の計算結果を求める問題。
木が表す式を再帰的に評価する。
Part 2
根の左の子、右の子を L, R とする。
葉 X が指定される。[L の計算結果] = [R の計算結果] になるように X の数値を書き換える問題。
X に関係ない部分木は計算結果が決まっている。根から降りていって次の要領で X を求める。
- ((1 + 3) + (2 * X)) / 4 = (6 - 2) * 5
- → (1 + 3) + (2 * X) = (6 - 2) * 5 * 4
- → 2 * X = (6 - 2) * 5 * 4 - (1 + 3)
- → X = ((6 - 2) * 5 * 4 - (1 + 3)) / 2 = 38
ikdDay 16
1 分で移動できるバルブの組のリストと R[1], ..., R[N] が与えれる。バルブ v を開けると 1 分あたり R[v] の水が流れるようになる。指定されたバルブから始めて、移動とバルブを開ける操作をうまくして 30 分後に流れた水の合計を最大化する問題。
N ≦ 60
解法
入力をよく見ると R[v] = 0 のバルブが多く R[v] > 0 のバルブは 16 個以下。
開ける意味のあるバルブたちの間の移動時間を計算しておいて「縮約」したグラフ上で頂点数 ≦ 16 の問題を解けばよい。
DP[t][v][S] := 残り時間が t で、頂点 v にいて、これから開けるバルブの集合が S のときの総流量の最大値 とすると答えが DP[30][(スタートの頂点)][{v[1], ..., v[16]}] になる。状態数は 30 × 16 × 2^16 = 31457280 で遷移は O(1) でできる。
Part 1
上の DP を実装する。
Part 2
- 時間が 30 分 → 26 分
- バルブを開けてまわる人が 2 人
という設定が追加された問題。
ふたりの「担当」するバルブの集合を分けて、それぞれの成果の合計の max をとればよい。
つまり S ∪ T = {v[1], ..., v[16]}, S ∩ T = ∅ にわたる max(DP[26][(スタートの頂点)][S] + DP[26][(スタートの頂点)][T]) が答え。
実行時間は 20 分ほどになった。
ikdDay 18
キューブ # の位置が与えられて「表面積」を求める問題。
↓の 3 次元版。
........
..####..
..#..#..
..#..#..
...#.#..
...##...
..##....
........
- キューブの個数 ≦ 3000
- 0 ≦ 座標 ≦ 20
Part 1
@ の部分を数える問題。問題文に計算方法が書いてある (?) ので実装する。
..@@@@..
.@####@.
.@#@@#@.
.@#@@#@.
..@#@#@.
..@##@..
.@##@...
..@@....
Part 2
X の部分のみ数える問題。キューブたちの「外側」がわかればよい。(-1, -1) から BFS や DFS するとわかる。
..XXXX..
.X####X.
.X#..#X.
.X#..#X.
..X#.#X.
..X##X..
.X##X...
..XX....
Day 15
2 次元グリッド上にセンサーがいくつかある。センサー k は自身からマンハッタン距離 D[k] 以内にあるマスが見える。
- センサーの個数 ≦ 23
- -4000000 ≦ 座標 ≦ 4000000
Part 1
y = 2000000 にあるマスのうち、ひとつ以上のセンサーから見えるマスの個数を求める問題。
y を固定すると、ひとつのセンサーの視野が覆う x の範囲は、まったくないか [l, r] という区間の形。
センサーの数だけ [l, r] たちを併合していけばよい。左端でソートして前から見るとできる。(Part 1 だとマスをひとつずつ見ていっても大丈夫そう)
........... ...........
........... ...........
........... .....#.....
> ........... > ....###....
........... ...#####...
.....#..... ..#######..
....###.... .#########.
...#####... ###########
..#######.. .#########.
.#########. ..#######..
Part 2
0 ≦ x, y ≦ 4000000 の範囲に、どのセンサーにも見えないマスがひとつだけある。そのマスを求める問題。
センサーたちが見えている x の範囲が [▲, r], [r + 2, ■] となるかどうかを y = 0, 1, ..., 4000000 についてひとつずつ調べればよい。x = r + 1 が条件を満たすマス。Part 1 と同じ要領で求められる。
実行時間は 2 分ほどになった。
ikdDay 14
2 次元グリッド上で砂が落ちてくる問題。
砂は基本的には真下に落ちる。他の砂や障害物がある場合は左下に落ちようとする。左下もダメだったら右下に落ちようとする。右下もダメだったらその位置で砂が固定される。そして次の砂が落ちてくる。
0 ≦ 座標 ≦ 600
Part 1
「底」がない設定。砂が障害物に引っかかるうちはいつか止まって新しい砂が落ちてくるが、あふれると底がないので砂が無限に下に行く。この状態になるまでに、砂が積もった個数を求める問題。
砂の落下を 1 粒ずつシミュレーションする。砂が底に着いたら打ち切り。与えられる障害物が多そうなので、シミュレーション回数 = 答えが抑えられる。
Part 2
「底」がある設定。積もった砂が高くなって、新しい砂の出てくる箇所 P が詰まった時点での砂の個数を求める問題。
Part 1 とだいたい同じ。シミュレーションした結果 P の位置に砂が固定されることがわかった時点で打ち切り。(Part 1 より易しいような……？)
計算量はよくわからないが 20 秒ほどで実行が終わる。
ikdDay 13
こういう数値のリスト [3, [1, 4], [[1]], 5, [9, [2, 6]]] がたくさんある。
リスト同士の大小の定義が決まっている。
- リスト内の要素数 ≦ 50
- リストの個数 ≦ 400
Part 1
ふたつのリストの大小を判定する問題。
入力をがんばってパースする。もしくは JSON とみなして標準ライブラリなどでパースする。
大小比較は問題文に書いてある定義通りに実装する。
Part 2
リストたちをソートする問題。
Part 1 の処理を流用すればできる。
ikdDay 12
辺の長さがすべて 1 の有向グラフが与えられる。
- 頂点数 ≦ 8000
- 辺数 ≦ 12000
Part 1
スタートの頂点 S とゴールの頂点 G が与えられて S → G の最短距離を求める問題。
BFS をして解ける。
Part 2
スタートの頂点候補 S[1], S[2], ... とゴールの頂点 G が与えられて min(S[1] → G の最短距離, S[2] → G の最短距離, ...) を求める問題。
超頂点から S[1], S[2], ... に長さ 0 の辺を追加したグラフ上で Part 1 と同じ BFS をすれば解ける。
ikdDay 11
番号のついた猿が何匹かいて、はじめアイテムをいくつか持っている。アイテムには心配度という数値が設定されている。
番号の小さい順に、猿が次の行動をする：
自身の持っているアイテムそれぞれについて、心配度を +▲ する。心配度が ■ で割りきれるなら猿 A にそのアイテムを渡す。割り切れないなら猿 B に渡す。
▲, ■, A, B は猿ごとに決まった値で入力から与えられる。「+▲」の部分は他に「×▲」「2乗する」のバリエーションがある。
最後の猿の行動が終わったら 1 ラウンドの終わり。これを N ラウンド繰り返して、アイテムを触った回数の多い猿トップ 2 を求める問題。
- 猿の数 ≦ 8
- アイテムの合計個数 ≦ 50
- ▲, ■ ≦ 100
Part 1
- N = 20
- 「アイテムの心配度を +▲」のあとに ÷3 する
- (オーバーフローが起きないようにする制約)
素直にシミュレーションをする。ラウンドの途中でアイテムが増える猿がいることに気をつける。
Part 2
N = 10000
Part 1 のままだとアイテムの心配度がオーバーフローする。
「心配度が ■ で割りきれるなら〜」の ■ たちの最小公倍数を L として、mod L で心配度を持つ。正当性は 実際の心配度 % L の値を a とすると、実際の心配度 = a + Lb と書けて L は ■ で割り切れるため、実際の心配度 ≡ a (mod ■) となることからわかる。
ikdDay 10
はじめ X = 1 である。2 種類の命令がたくさん与えられる。前から順に実行される。
- noop：1 サイクル何もしない
- addx v：2 サイクル後に
X += vをする- X の更新が終わったあとに次の命令が実行される
20 番目のサイクル中の X の値、60 番目の……、220 番目のサイクル中の X の値を求める問題。
命令の個数 ≦ 140
Part 1
各サイクルでの X を記録しておけばよい。「そのサイクル中の X」「そのサイクル終了後の X」どちらにするかで微妙に変わってくるが適当に ±1 を合わせる。
Part 2
X を列番号、サイクル / 40 (切り捨て) を行番号と見て、2 次元グリッドに模様を描く問題 (よくわからなかった🫠)
X の履歴を大きさ 40 のチャンクに分けて見ていけばよい。
ikdDay 9
ロープに結び目がいくつかある。2次元グリッド上で先頭の結び目を
R 4
U 4
L 3
︙
のような指示にしたがって動かす。
- 指示の個数 ≦ 2000
- ひとつの指示で移動するマス ≦ 20
Part 1
先頭の結び目と末尾の結び目がある。末尾の結び目は先頭が 1 マス動いたあと (斜めもゆるして) 隣り合うように追いかける。末尾の結び目が通るマスを求める問題。
こういうケースで末尾 T は真上ではなくて右上に動くことに注意して実装する。
... .H. .H.
.H. -> ... -> .T.
T.. T.. ...
Part 2
先頭、末尾含めて合計 10 個の結び目がある。先頭から動き出し、それぞれの結び目は自分のひとつ前の結び目を追いかけるように移動する。末尾の結び目が通るマスを求める問題。
結び目たちを knots[1], knots[2], knots[3], knots[4], ... として次を繰り返せばよい。各ステップは knots[i] を先頭、knots[i+1] を末尾とみなせば Part 1 と同じ。
- knots[1] を 1 マス動かす
- knots[2] を knots[1] に追従させる
- knots[3] を knots[2] に追従させる
- knots[4] を knots[3] に追従させる
- ︙
ikdDay 8
2 次元グリッド上の各マスに木が生えている。木 (i, j) の高さ h[i][j] が与えられる。
グリッドの縦、横 ≦ 100
Part 1
グリッドの外から見える木の本数を求める問題。木がグリッドの外から見えるとは、上下左右いずれかの方向で、グリッドの端と自身との間にある木がぜんぶ自身より真に低いこと。
各マス、各方向ごとに木の高さを見ていけばよい。グリッドの 90 度回転を実装するとラクかもしれない。
Part 2
マスの景観度の最大値を求める問題。景観度は、自身以上の高さを持つ木までの距離 (そのような木が存在しなければ 0)、を 4 方向についてかけ合わせたもの。
Part 1 とだいたい同じ。
ikdDay 7
実行したコマンド
$ cd x$ cd ..-
$ lsとその出力数値で始まる行はファイル、dir で始まる行はディレクトリ14848514 b.txt 8504156 c.dat dir d
の列が与えられる。
- コマンドの個数 ≦ 1000
-
$ lsのあとに続くファイル・ディレクトリの個数 ≦ 1000
Part 1
サイズ 100000 以下のディレクトリを列挙する問題。
Part 2
ディスクの容量が 70000000 ある。空き容量 30000000 を確保するために消すディレクトリのうちサイズが最小のものを求める問題。
解法
Part 1 も Part 2 もディレクトリたちのサイズを列挙できれば解ける。
コマンド履歴は規則正しくなっている (ちょうど 1 回ずつディレクトリを訪れる) ぽいのでがんばってパースする。ファイルが葉、ディレクトリがそれ以外の頂点に対応する木になる。各部分木について「サイズ」を求める。これは 1 回の DFS で葉からボトムアップに決まる。
ikdDay 06
英小文字からなる文字列が与えられる。含まれる文字が被らない長さ L の部分文字列が最初に現れる位置を求める問題。
文字列の長さ ≦ 4500
Part 1
L = 4
Part 2
L = 14
解法
切り出した部分文字列の中で文字の重複があるかを判定できればよい。ソート & unique や set を使うとできる。
ikdDay 5
荷物の山が N 個ある。たくさん与えられる指示にしたがって荷物を移す問題。
- 山の個数 ≦ 10
- 荷物の個数 ≦ 60
- 指示の個数 ≦ 600
Part 1
指示が「山 A から山 B に上から K 個、ひとつずつ荷物を移す」という形。
Part 2
指示が「山 A から山 B に上から K 個まとめて (上下関係を保って) 荷物を移す」という形。
解法
Part 2 は、列 A の先頭 K 項を取り出し、列 B の先頭に連結する を繰り返せばよい。
Part 1 は、列 A から取り出した先頭 K 項を reverse して列 B に連結すれば、ひとつずつ荷物を移したときと同じ結果を得られる。
ikdDay 4
区間の組 [A, B], [C, D] が N 個与えられる。
- 0 ≦ A, B, C, D ≦ 100
- N ≦ 1000
Part 1
一方が他方を含む組の個数を求める問題。
Part 2
共通部分がある組の個数を求める問題。
解法
値の範囲が狭いので、集合
- {A, A + 1, ..., B}
- {C, C + 1, ..., D}
を実際につくって集合操作系の機能を使うことで十分高速に解ける。
もしくは端点たちの大小関係だけを見てもよい。Part 1 だと A <= C <= D <= B || C <= A <= B <= D を満たす組が条件を満たす。
ikdDay 3
英小文字と英大文字からなる文字列が N 個与えられる。
- 文字列の長さ ≦ 50
- N ≦ 300
Part 1
文字列の前半と後半で共通して現れる文字がひとつだけあるのでそれを求める問題。
Part 2
文字列を 3 個ずつセットにして考える。3 つの文字列に共通して現れる文字がひとつだけあるのでそれを求める問題。
解法
文字の集合たちの共通部分 S ∩ T や S ∩ T ∩ U を集合操作系の機能で計算する。
もしくは a 〜 z, A 〜 Z に対して ▲ ∈ S && ▲ ∈ T を満たすかチェックしていっても解ける。
ikdDay 2
じゃんけんの履歴が N 件ある。
N ≦ 2500
Part 1
各履歴では、相手の手と自分の手が与えられる。じゃんけんの結果を (自分の勝ち/負け/引き分け) を求める問題。
相手の手 3 通り × 自分の手 3 通りの場合分けをすればよい。
Part 2
各履歴では、相手の手とじゃんけんの結果が与えられる。その結果になるように自分が出すべき手を求める問題。
自分の手を 3 通りすべて試してじゃんけんの結果と合うものを選べばよい。
ikdDay 1
アイテムが N 個ありグループ分けされている。各アイテムにはカロリーが決まっている。
N ≦ 2500
Part 1
各グループ内のアイテムの合計カロリー最大値を求める問題。
Part 2
各グループ内のアイテムの合計カロリートップ 3 を求める問題。
解法
合計カロリーたちを求めて降順ソートする。Part 1 では先頭を、Part 2 では先頭 3 項を見ればよい。