競 プロ定番 カタログ(Part 6 総まとめ )
この章は、Part 6(22〜26)で使った実装パターンを、問題投入前に見返せる形で整理した実戦メモです。
ポイントは「短いが安全」「標準ライブラリ優先」「std/streamio で入出力の雛形を固定」の 3 つです。
まず使うテンプレート
TESTstdionormalize_newlines
#entry main
#indent 4
#target std
#import "core/math" as *
#import "core/result" as *
#import "std/streamio" as *
#import "std/iotarget" as *
#import "alloc/collections/vec" as *
#import "core/mem" as *
fn main <()*> ()> ():
// 入力を Vec に貯め、配列走査の雛形として合計を計算します。
let sc <StreamScanner> unwrap_ok open ReadStream::Stdio;
let n <i32> read sc;
let mut a <Vec<i32>> unwrap_ok new<i32>;
let mut i <i32> 0;
while lt i n:
do:
set a unwrap_ok push a read sc;
set i add i 1;
let mut sum <i32> 0;
let s <VecDataLen<i32>> data_len<i32> a;
let p <i32> mem_ptr_addr get s "data";
let len <i32> get s "len";
let mut j <i32> 0;
while lt j len:
do:
set sum add sum load_i32 add p mul j 4;
set j add j 1;
close sc;
unwrap_ok open WriteStream::Stdio
|> writeln sum
|> flush
|> close典型パターンと対応ライブラリ
入出力
- 入力:
std/streamioのopen,read,close - 出力:
std/streamioのopen,write,writeln,flush,close
配列・ソート・探索
- 配列構築:
alloc/collections/vecのnew,push,len,get - ソート:
alloc/collections/vec/sortのsort_quick_ret - 二分探索:
kp/kpsearchのlower_bound_vec_i32,upper_bound_vec_i32,count_equal_range_vec_i32
区間和・2 ポインタ
- 累積和:
kp/kpprefixのprefix_build_vec_i32,prefix_sum_i32,prefix_free_i32 - 2 ポインタ:
Vec+whileでl,rを単調増加させる
グラフ
- 密行列 BFS:
kp/kpgraphのdense_graph_new,dense_graph_add_undirected,dense_graph_bfs_dist_raw - 入力形式付き構築:
dense_graph_read_undirected_1indexed
データ構造
- Union-Find:
kp/kpdsu - Fenwick Tree:
kp/kpfenwick
解法フロー(提出前チェック)
- 入力を
StreamScannerで読み切る(型は i32 / i64 を先に確定)。 - 状態を
Vecや専用構造へ入れる(手書きヒープ操作を避ける)。 - 本体ロジックを
sort/search/prefix/graph補助で短く保つ。 - 出力を
StreamWriterでまとめて flush する。 - 境界ケース(空配列、1要素、同値多数、最大値付近)を
neplg2:testで固定する。
20 テーマの使い分けメモ
- 高速入力:
read - 高速出力:
write/writeln - 1D 累積和:
prefix_build_vec_i32 - 2D 累積和: 問題ごとに実装(行列サイズ注意)
- いもす法: 差分配列 + 累積和
- lower_bound:
lower_bound_vec_i32 - upper_bound:
upper_bound_vec_i32 - 存在判定:
contains_vec_i32 - 尺取り法:
l,r単調増加 - 座標圧縮: sort + unique + lower_bound
- BFS:
dense_graph_bfs_dist_raw(小〜中規模) - DFS: 再帰深さに注意
- Union-Find:
kp/kpdsu - BIT:
kp/kpfenwick - セグ木: 問題別モノイド設計
- Dijkstra: 優先度付きキュー
- トポソ: 入次数管理
- mod べき乗: 繰り返し二乗法
- 組合せ前計算:
fact/inv_fact - DP: 状態・遷移・初期値を固定
Part 6 の目的は「全部を暗記すること」ではなく、
「問題文を見たらどの型・どの補助 API を使うかをすぐ選べる状態」にすることです。