Rust 競プロ AHC参加の準備してみた（チートシート集）
AtCoder Heuristic Contest (AHC)参加に向けて、thunder本や鉄則本を学習するときに、アルゴとは異なり、ヒューリスティック特有で詰まった箇所について、チートシート集として共有します。まだAHC参加したことがなく、洗練されてはいませんが、強々の上位勢のコードを良いとこ取りをしていますので、そんなに的外れではないと思います。
適宜気づきがあれば、更新・修正していく予定です。
Time Keeper
AHCでは制限時間いっぱい探索することをします。やり方は色々あるのですが、やり方を間違うと処理が重くなったりすることがあるので注意が必要です。
以下、2つのやり方を紹介します。個人的には構造体で作る方法の方が、制限時間を複数回設定したい場合に使いやすいのでオススメです。
構造体で作る方法
インスタンスを生成するときに、時間制限を設定して、そのときから、時間制限を過ぎたときに、isTimeOver関数を呼び出すとtrueが返ってきます。もちろん時間制限以内に呼び出すとfalseが返ってきます。
#[derive(Debug, Clone)]
struct TimeKeeper {
start_time: std::time::Instant,
time_threshold: f64,
}
impl TimeKeeper {
fn new(time_threshold: f64) -> Self {
TimeKeeper {
start_time: std::time::Instant::now(),
time_threshold,
}
}
#[inline]
fn isTimeOver(&self) -> bool {
let elapsed_time = self.start_time.elapsed().as_nanos() as f64 * 1e-9;
#[cfg(feature = "local")]
{
elapsed_time * 0.85 >= self.time_threshold
}
#[cfg(not(feature = "local"))]
{
elapsed_time >= self.time_threshold
}
}
}
使い方は以下の通り。以下は制限時間を0.98secに設定しています。
let time_keeper = TimeKeeper::new(0.98);
while !time_keeper.isTimeOver() {
// 処理
}
関数で作る方法
関数を初回呼び出したときにSTIMEが設定され、そのときからの経過時間（単位：秒）を返します。
#[inline]
fn get_time() -> f64 { // sec
static mut STIME: f64 = -1.0;
let t = std::time::SystemTime::now()
.duration_since(std::time::UNIX_EPOCH)
.unwrap();
let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
unsafe {
if STIME < 0.0 {
STIME = ms;
}
#[cfg(feature = "local")]
{
(ms - STIME) * 0.85
}
#[cfg(not(feature = "local"))]
{
ms - STIME
}
}
}
使い方は以下の通り。以下は制限時間を0.98秒に設定しています。
get_time();
while get_time() < 0.98 {
// 処理
}
feature = "local"
feature = "local"は、ジャッジサーバと自分のPCの処理速度を調整するための設定です。
特に何も設定をしていなければ（ジャッジサーバでは）、以下の処理が実行されます。
#[cfg(not(feature = "local"))]
{
// 処理
}
Cargo.tomlで設定をして、実行時にコマンドで指定すると、以下の処理が実行されます。
#[cfg(feature = "local")]
{
// 処理
}
- Cargo.toml
[features]
local = []
- コマンド
cargo run --features local
- 時間調整
以下のように設定します。
elapsed_time * 0.85 >= self.time_threshold // ジャッジサーバの0.85倍の速度（自分のPCが遅い場合）
elapsed_time * 1.5 >= self.time_threshold // ジャッジサーバの1.5倍の速度（自分のPCが速い場合）
入力は、最大ケースが以下のように既に提供されているのであれば、それを使用します。そうでない場合や精度を良くするために複数ケース試したい場合は、制約内の入力を乱数を使用して生成することになるかと思います。あまり拘らずだいたいで良いとは思います。。。
入力コピペで入力すると入力に時間がかかるので、注意。
実行する際は、名前を例えばinとして、プロジェクトのトップに保存した後、以下のコマンドで実行できます。
cargo run < in
Rand（乱数）
基本
乱数は基本的には、以下を使用することで問題ありません。
use rand::Rng;
let mut rng = rand::thread_rng();
let r = rng.gen_range(0, 10); // 0-9
let r = rng.gen::<bool>(); // true or false
let r = rng.gen::<f64>(); // 0.0-1.0
デバッグする際にseedを設定して、乱数を固定する場合は以下を使用します。
use rand::rngs::StdRng;
use rand::Rng;
let seed = 123;
let mut rng: rand::rngs::StdRng = rand::SeedableRng::seed_from_u64(seed);
let r = rng.gen_range(0, 10); // 0-9
let r = rng.gen::<bool>(); // true or false
let r = rng.gen::<f64>(); // 0.0-1.0
シードのランダムと固定の切り替え
デバッグの際は固定シードで、デバッグが完了したら、ランダムシードで動作確認したいので、簡単にシードを切り替えられるようにします。
前項と同じように、以下の通りfeatureで設定します。
#[allow(unused_mut, unused_assignments)]
let mut seed: usize = rand::thread_rng().gen();
// 以下でもOKだが、ランダムシードで同じシードを使いまわしたい場合は上記を使用
// let mut seed = 0;
#[cfg(feature = "seed")]
{
seed = 11216848234635351618;
}
- Cargo.toml
[features]
seed = []
- コマンド
コマンドは以下の通りです。時間調整の設定も同時にする場合は、2行目のコマンドです。
cargo run --features seed
cargo run --features local --features seed
モジュール
上述の基本のやり方で基本的には問題ないのですが、Rustはグローバル変数が扱えないので、色々な関数で使用する場合は、引数地獄になって、大変です。また、わざわざ乱数のインスタンスを何回も生成するもの面倒だし、処理が重くなりそうで気持ちが良くありません。
どの関数からも呼び出せるように、モジュール化して使用します。init関数で初期化して、種々のgen関数で乱数を返します。init関数でseedを0にしたときは、ランダムでseedが設定され、それ以外だと固定のseedが設定されます。
mod rnd {
use rand::Rng;
static mut S: usize = 0;
static MAX: usize = 1e9 as usize;
#[inline]
pub fn init(seed: usize) {
unsafe {
if seed == 0 {
S = rand::thread_rng().gen();
} else {
S = seed;
}
}
}
#[inline]
pub fn gen() -> usize {
unsafe {
if S == 0 {
init(0);
}
S ^= S << 7;
S ^= S >> 9;
S
}
}
#[inline]
pub fn gen_range(a: usize, b: usize) -> usize {
gen() % (b - a) + a
}
#[inline]
pub fn gen_bool() -> bool {
gen() & 1 == 1
}
#[inline]
pub fn gen_float() -> f64 {
((gen() % MAX) as f64) / MAX as f64
}
}
使い方は以下の通り。initを実行した関数以外でも、initを実行した状態で引き継がれ、乱数を取得できます。
#[allow(unused_mut, unused_assignments)]
let mut seed: usize = rand::thread_rng().gen();
// 以下でもOKだが、ランダムシードで同じシードを使いまわしたい場合は上記を使用
// let mut seed = 0;
#[cfg(feature = "seed")]
{
seed = 11216848234635351618;
}
rnd::init(seed);
let r = rnd::gen_range(0, 10); // 0-9
let r = rnd::gen_bool(); // true or false
let r = rnd::gen_float(); // 0.0-1.0
演算子オーバーロード
ビームサーチを使用するとき、構造体を優先キューに入れるという処理を行いますが、比較演算子のオーバーロードを設定しないと、構造体同士の比較ができないため、優先キューに入れることができません。以下の通り比較の定義をします。PartialEq、PartialOrd、Ordの3点セットで定義をします。
deriveの設定忘れがちで、エラー地獄になるので、注意しましょう。また、以下のように、構造体の中にさらにカスタムの構造体をメンバ変数として設定する場合は、比較の定義と関係なくてもderiveの設定が必要です。
以下の例では、scoreという変数で比較を定義しています。posは定義には関係しませんが、Positionの定義の際にderive設定が必要です。
※PartialEqがない実装例もあり、それでも支障はないかと思いますが、いつか使うかも、という意味で実装しています
#[derive(Debug, Clone, Eq, PartialEq)] // 忘れがち
struct Position {
x: usize,
y: usize,
}
impl Position {
fn new() -> Self {
Position { x: 0, y: 0 }
}
}
#[derive(Debug, Clone, Eq)] // 忘れがち
struct State {
pos: Position,
score: usize,
}
impl State {
fn new() -> Self {
State {
pos: Position::new(),
score: 0,
}
}
}
impl std::cmp::PartialEq for State {
fn eq(&self, other: &Self) -> bool {
self.score == other.score
}
}
impl std::cmp::PartialOrd for State {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
if self.score == other.score {
Some(std::cmp::Ordering::Equal)
} else if self.score > other.score {
Some(std::cmp::Ordering::Greater)
} else if self.score < other.score {
Some(std::cmp::Ordering::Less)
} else {
None
}
}
}
impl std::cmp::Ord for State {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
if self.score == other.score {
std::cmp::Ordering::Equal
} else if self.score > other.score {
std::cmp::Ordering::Greater
} else {
std::cmp::Ordering::Less
}
}
}
使用の仕方は以下の通りで、優先キューに入れることができます。
let mut heap = BinaryHeap::new();
let mut state1 = State::new();
let mut state2 = State::new();
heap.push(state1);
heap.push(state2);
もちろん、配列に入れたら、ソートすることが可能ですし、BTreeSetに入れたり、BTreeMapのキーにしたりすることも可能です。
let v mut = vec![];
let mut state1 = State::new();
let mut state2 = State::new();
v.push(state1);
v.push(state2);
v.sort();
その他
入力の一部をグローバル変数
AHCでは、入力の一部も色んな関数で使いまわすことが多いようなので、入力の一部をグローバル変数にして、どこからでも呼び出せるようにしておくと、引数地獄から開放され、実装が楽になる。実装方法は以下参照。
ループラベル
アルゴで使用する機会はあまりありませんが、ヒューリスティックの場合は、重ループを抜けたい場面があります。Rustにはgotoはないですが、ループラベルを使用すると、抜けることができます。
'outer: for i in 0..N{
for j in 0..M {
// 処理
if 式 {
break 'outer;
}
}
}
高速化
- 構造体の変数最小化
構造体で使用する変数を最小化することで、コピーのコストを削減し、試行回数を稼ぐことができます。
定数はわざわざ構造体にもっておく必要はないですし、型もusizeやu64ではなく、u8やu32で十分であれば、そちらを使用することで、大幅に改善できる場合があります。
- with_capacity
配列を宣言する際に、with_capacityを使用して、メモリを確保しておくことで、メモリの再割り当てのコストを抑えられるらしい。。。
らしい、というのは、したのとしてないので、数倍違うということ経験がないので、速度改善しているかどうか分からない。現時点ではとりあえずやっとく。
let v = vec![]; // 通常時
let v = Vec::::with_capacity(N); // メモリ確保。なるべくこっちを使用する。
おまけ
thunder本、鉄則本で上記を使用したコードをGithubにおいているので、参考にしてください。
thunder本
- 3章
- 4章
鉄則本
- a46 (Heuristic 1)
- a49 (Heuristic 2)
Discussion