ABC108/ARC102 D All Your Paths are Different Lengths
公式解説の英語版の方法
$L=L'$のグラフから$L=L'+1, 2L'$のグラフを作るには
$L=L'+1$
先頭から末尾の頂点へ長さ$L'$の辺を引く
$L=2L'$
すでに引いてある辺の長さを全て2倍にして、末尾の頂点から新しい頂点へ長さ$0$と長さ$1$の辺を引く
Implementation and Visualization Binary Heap
二分ヒープを実装しました。
機能
| 操作 | 最悪計算量 |
|---|---|
| 最大（最小）値の取得 | $O(1)$ |
| 要素の挿入 | $O(\log_2 n)$ |
| 最大（最小）値を持つ要素の削除 | $O(\log_2 n)$ |
$n$はヒープの要素数です。
実装
up-heapは簡単だけど、down-heapは子が2つある場合優先度の高いほうと比較しないといけないことに注意します。
ベンチマーク
方法
- $10^5$回要素を挿入
- $10^5/2$回最大値を持つ要素を削除
- $10^5$回要素を挿入
- $10^5/2$回最大値を持つ要素を削除
挿入する要素は$[-10^9, 10^9)$の範囲の整数をランダムに選びます。
環境
dmd --version DMD64 D Compiler v2.081.2
コンパイルオプションは -O -release -inline
結果
| std.container.binaryheap.BinaryHeap | 1 sec 552 ms |
| std.container.rbtree.RedBlackTree | 7 secs 480 ms |
| myBinaryHeap | 2 secs 265 ms |
検証用のソースコード
ビジュアライザ
https://ia7ck.github.io/visualization/binary-heap
数独をプログラムで解く
数独（SUDOKU)をプログラム (Ruby) で解きます。
アルゴリズム
マスを前から見ていって、空欄のマスに1, 2, ..., 9の順で置けるかどうか試します。
- 置けるならその数字を置いて次のマスを見る
- どの数字も置けないなら、いままでの数字の置き方がまずかったということなので前のマスに戻る
これで解けます。
$9^{81}$通りくらい試すことになりそうですが、いい感じに枝刈りされてすぐに答えが出ます。
Demo
アルゴリズムの動作のイメージはこんな感じです。
https://ia7ck.github.io/visualization/backtracking/sudoku/index.html
ソースコード
データは 1 million Sudoku games | Kaggle のものを使いました。
