AOJ ALDS1 を Rust で全埋めしたので感想
はじめに
ALDS1 を埋めると大学のアルゴリズムとデータ構造の講義が出席免除になって試験だけで単位がもらえると聞いて埋めました。
本当は全 15 トピック中 13 までで良かったんですが勢い余って全部解いた
ちなみに Rust で解きました イキリオタクなので
Rust 特有の問題とか難しかった問題について簡単に発想/解説を書くつもりなので同級生たちの手助けになればいいな、と思います。
TLE に関して
何人かに聞かれたので、書きます
AOJ で C/C++ を使って実行時間制限 1 sec に間に合わせたい場合、ループ回数が大体 $10^8$ 回くらいになっていれば良いです。
$O(f(n))$ のようにして計算量を見積もると思いますが、問題の制約下での $f(n)$ の最大値を考えれば問題ありません。
競プロerであるところの僕の肌感覚としては大体こんな感じ
| 計算回数 | お気持ち |
|---|---|
| $10^7$ | 十分間に合う |
| $10^8$ | おそらく間に合う |
| $10^9$ | 十中八九無理 除算が絡んだら諦める 加算/乗算だけ、とかならワンチャン |
章ごと所感
1. 入門
C は計算量意識しないと TLE する
C: 正整数 $N$ は $O(\sqrt N)$ で因数分解できます。
$N$ の約数のペア( $a \times b = N$ である $a, b$) に着目したとき、 $a \le \sqrt N$ または $b \le \sqrt N$ が成り立ちます。
$a \times b = N$ のとき $a$ を増やせば $b$ が減ります。逆も同様。
ここで、 $a = b = \sqrt N$ を考えて $a, b$ をがちゃがちゃするとお気持ちがわかる。
2. 初等的ソート
擬似コードに従ってコードを書けばおーけー
D のパラメータを適当に決めて動きを見ると意外と面白い
手元で swap 回数を見たりするために適当な乱数データを用意しておくと良いと思う
3. 基本データ構造
文句を言わずにコードを書きます
List は先頭からポインタを辿って print する関数を作るとデバッグしやすいと思う
D は括弧列を stack で管理しましょう、みたいな問題 けっこう面白かった
4. 探索
A: 文句を言わずにコードを書きます
B: 探索区間を半開区間で扱うとバグらせにくいです。詳細は既存の解説記事に任せます 1
C: ハッシュテーブルを実装します 4進数として解釈して配列の添字として使うのが楽?
D: ある程度競技ミングをやると見た瞬間「二分探索ですねえ！」ってなる問題
ある $P$ での最適解はトラックに貪欲に荷物を積んでいけば求まる
また $P$ が増えるほどにトラックの必要台数が減っていく(単調性がある) ので二分探索で条件に沿う $P$ を探せばよい
5. 分割統治法
A, B, C: 再帰関数を書くのに慣れるしかなくて、こればかりは書いて覚えるしかない
Merge Sortの計算量解析、めっちゃ綺麗なので好き
D: 競技ミングやってない人間に解ける問題に見えない
犯罪者なので定義通りに書いたあとセグメント木で高速化した $O(N \log N)$
6. ソート
A, B, C: 問題文に擬似コードも載ってるし文句を言わずにコードを書きます
Quick Sortの計算量について色々考えておくと後々二分探索木で伏線がつながってオタク・大盛り上がりするからオススメ
D むっっっっっっっっっっずかしかった ソート後に各 $w_i$ がどこに行って欲しいかでグラフを作る 必ず閉路ができるのでこの閉路ごとに解くことを考えると良い
7. 木構造
左子右兄弟表現とか使うメリットはあんまり無いと思う
再帰は量書いて慣れるのが最良の練習方法だと思うので頑張りましょう
D: 区間DPっぽくやる 中間順巡回で並んでいる頂点のうち、ある一つを根に持ち上げるとその左右に書かれている要素達がそのまま左部分木, 右部分木に対応するのがミソ
先行順巡回から木の元の根が分かるので、これを元に区間を分割して再帰的に解いていく
すごい面白い問題だった
8. 二分探索木
擬似コードついてるので文句を言わずにコードを書きます
Rust で書くと親へのリンクを持ったときに循環参照が起きてメモリリークするので辛かった(ノード配列を持ってリンクを配列の添字として持つことで解決)
問題文に書いてある擬似コードが Rust と相性悪くて苦戦した
9. ヒープ
A -> B -> C と上手く誘導に乗れるか勝負！みたいな章
頂点への番号の振り方がよくわからなかったら自分で手を動かしてみると良いです
デバッグはこんな感じで木を出力すると楽
void print_tree(int root, int depth) {
if (root >= n) return;
print_tree(root * 2 + 1, depth + 1);
for (int i = 0; i < depth; i++) printf(" ");
printf("(%d, %d)\n", root, A[root]);
print_tree(root * 2, depth + 1);
}
print(1, 0) みたいにして呼び出す 木を横向きにして辺を消した感じの表示になる
A問題 を例にすると
$ ./a.out
(7, 4)
(3, 5)
(6, 9)
(1, 25)
(5, 8)
(2, 12)
(9, 7)
(4, 6)
(8, 3)
こんな感じの出力になる
10. 動的計画法
DP苦手なのでびっくりしたんだけど流石にこれくらいはね、できる
A: 文句を言わずにコードを書きます
B: 授業でこれ扱うの！？って思ってびっくりした 区間DP 2
C: Bより簡単だと思う
D: Bより簡単だと思う $O(N^3)$ の区間DP
B:
$M_1 \times M_2 \times … \times M_n$ を計算するとき、最終的には $(M_1 \times M_2 \times … \times M_i) \times (M_{i + 1} \times M_{i + 2} \times … M_n)$ を計算するはず
ここで、左側と右側で独立にスカラ乗算の回数を最小化しようっていうのが基本方針\
11. グラフ1
再帰関数書けるかな？みたいな問題群
Rust だとグラフを探索するのに結構冗長な書き方を強いられてちょっとモチベを下げた
12. グラフ2
11 までちゃんとやってたらすぐ解ける問題ばかりだと思う
やってなかったらさようなら….
Dijkstra法なんだけど DP の特殊形として見ると面白くない？ちなみに Rust は標準ライブラリのドキュメントにDijkstra法の実装が載ってる 3 草
13. ヒューリスティック探索
実装が面倒なくらいで思考要素はそんなに無いと思う
文句を言わずにコードを書きます
14. 文字列
全体的に制約がきっっつい
A: やります
B: Rolling Hash が楽だと思う
C: 2D Rolling Hash 以外思いつかない
D: 全文索引ですねぇ！！！！
Dのメモリ制限がアホみたいにきつくてめちゃくちゃ時間かかった
SuffixTree で MLE 回避するために map を自作してる人まで居て面白かった
あと B を演習室で解いてたんですが怪しい陽キャの方が「一年生のアルゴですか？僕教えますよ！」って言って $O(N^2)$ のパターンマッチングを教えてくれた ありがとう
15. 貪欲アルゴリズム
A, B, D: やります
C: イベントソート
完走した感想
これはね、できる なぜなら競技ミングをやってたからねって言ってたら9割5分終わってた
真面目に考えないと出来なかったのは 6D, 14D
4Q は電磁気もあるし微積もあるしアルゴもあるし絶対どれかぶっちぎらないと死ぬと思っていたので切れて嬉しい