chokudai サーチ
(marathon/chokudai_search.cpp)

• View this file on GitHub
• Last update: 2025-01-01 23:36:48+09:00

• add_next_states で状態遷移を定義する
  • 状態およびそのターン数が与えられるので、次の状態およびそのターン数を決定し、 register_state を使って状態を登録
• メモリ制約に引っかからないように、各ターンで持つ状態数に上限を設けることが可能
  • set_max_num_states で設定する
  • Interval Heap を使って、あふれた状態を消している

AHC032 で利用実績あり。
https://atcoder.jp/contests/ahc032/submissions/61302590

Depends on

• Interval Heap (marathon/interval_heap.cpp)

Code

/**
 * @brief chokudai サーチ
 * @docs docs/marathon/chokudai_search.md
 */

#include "interval_heap.cpp"

template <class State, class Timer>
class ChokudaiSearch {
   public:
    ChokudaiSearch() : num_iter_(-1) {}
    void init(int max_turns, double search_time, int time_check_iter) {
        states_.resize(max_turns + 1);
        search_time_ = search_time;
        num_iter_ = 0;
        time_check_iter_ = time_check_iter;
        max_num_states_.resize(max_turns, 1 << 30);
    }
    void set_max_num_states(int max_num_state) {
        fill(max_num_states_.begin(), max_num_states_.end(), max_num_state);
    }
    void set_max_num_states(const vector<int> &max_num_states) {
        assert(max_num_states.size() == max_num_states_.size());
        max_num_states_ = max_num_states;
    }
    void register_state(int turns, const State &state) {
        states_[turns].emplace(state);
        while(states_[turns].size() > max_num_states_[turns]) {
            states_[turns].pop_max();
        }
    }
    void search(Timer &timer, const auto &add_next_states) {
        assert(num_iter_ >= 0);
        const double start_time = timer.getTime();
        for(num_iter_ = 0;; num_iter_++) {
            for(int turns = 0; turns + 1 < (int)states_.size(); turns++) {
                if(timer.getTime() - start_time > search_time_) {
                    goto TIME_OVER;
                }
                if(states_[turns].size() == 0) continue;
                State state = states_[turns].top_min();
                states_[turns].pop_min();
                add_next_states(turns, state);
            }
        }
    TIME_OVER:;
        fprintf(stderr, "chokudai search: num_iter = %d\n", num_iter_);
    }
    const State &get_best_state() const { return states_.back().top_min(); }

   private:
    double search_time_;
    int num_iter_;
    int time_check_iter_;
    vector<IntervalHeap<State>> states_;
    vector<int> max_num_states_;
};

#line 1 "marathon/chokudai_search.cpp"
/**
 * @brief chokudai サーチ
 * @docs docs/marathon/chokudai_search.md
 */

#line 1 "marathon/interval_heap.cpp"
template <typename Tp>
class IntervalHeap {
   public:
    template <class Iterator>
    IntervalHeap(Iterator first, Iterator last) : data_(first, last) {
        make_heap();
    }
    IntervalHeap() = default;

    size_t size() const { return data_.size(); }
    void clear() { data_.clear(); }
    void emplace(const Tp& val) {
        data_.push_back(val);
        up(size() - 1);
    }
    void push(const Tp& val) { emplace(val); }
    const Tp& top_min() const { return data_[size() >= 2]; }
    const Tp& top_max() const { return data_[0]; }
    void pop_min() {
        if(size() <= 2) {
            data_.pop_back();
        } else {
            swap(data_[1], data_.back());
            data_.pop_back();
            const size_t k = down(1);
            up(k);
        }
    }
    void pop_max() {
        if(size() <= 1) {
            data_.pop_back();
        } else {
            swap(data_[0], data_.back());
            data_.pop_back();
            const size_t k = down(0);
            up(k);
        }
    }

   private:
    vector<Tp> data_;
    inline size_t to_k_max(size_t k) { return k & ~1; }
    inline size_t to_k_min(size_t k) { return k | 1; }
    inline size_t get_parent(size_t k, bool is_max) { return (((k >> 1) - 1) & ~1) | (is_max ? 0 : 1); }

    size_t down(size_t k) {
        const size_t s = size();
        if(k & 1) {
            // min heap
            while(true) {
                const size_t cl = (k << 1) + 1;
                const size_t cr = (k << 1) + 3;
                if(cl >= s) break;
                const size_t c = (cr >= s || data_[cl] < data_[cr]) ? cl : cr;
                if(data_[c] < data_[k]) {
                    swap(data_[k], data_[c]);
                    k = c;
                } else {
                    break;
                }
            }
        } else {
            // max heap
            while(true) {
                const size_t cl = (k << 1) + 2;
                const size_t cr = (k << 1) + 4;
                if(cl >= s) break;
                const size_t c = (cr >= s || data_[cr] < data_[cl]) ? cl : cr;
                if(data_[k] < data_[c]) {
                    swap(data_[k], data_[c]);
                    k = c;
                } else {
                    break;
                }
            }
        }
        return k;
    }
    void up(size_t k, size_t root = 1) {
        const size_t k_max = to_k_max(k);
        const size_t k_min = to_k_min(k);
        if(k_min < size() && data_[k_max] < data_[k_min]) {
            swap(data_[k_max], data_[k_min]);
            k ^= 1;
        }

        size_t p;
        // max heap
        while(root < k && data_[p = get_parent(k, true)] < data_[k]) {
            swap(data_[k], data_[p]);
            k = p;
        }
        // min heap
        while(root < k && data_[k] < data_[p = get_parent(k, false)]) {
            swap(data_[k], data_[p]);
            k = p;
        }
    }
    void make_heap() {
        for(size_t i = size(); i--;) {
            if((i & 1) && data_[i - 1] < data_[i]) {
                swap(data_[i - 1], data_[i]);
            }
            size_t k = down(i);
            up(k, i);
        }
    }
};
#line 7 "marathon/chokudai_search.cpp"

template <class State, class Timer>
class ChokudaiSearch {
   public:
    ChokudaiSearch() : num_iter_(-1) {}
    void init(int max_turns, double search_time, int time_check_iter) {
        states_.resize(max_turns + 1);
        search_time_ = search_time;
        num_iter_ = 0;
        time_check_iter_ = time_check_iter;
        max_num_states_.resize(max_turns, 1 << 30);
    }
    void set_max_num_states(int max_num_state) {
        fill(max_num_states_.begin(), max_num_states_.end(), max_num_state);
    }
    void set_max_num_states(const vector<int> &max_num_states) {
        assert(max_num_states.size() == max_num_states_.size());
        max_num_states_ = max_num_states;
    }
    void register_state(int turns, const State &state) {
        states_[turns].emplace(state);
        while(states_[turns].size() > max_num_states_[turns]) {
            states_[turns].pop_max();
        }
    }
    void search(Timer &timer, const auto &add_next_states) {
        assert(num_iter_ >= 0);
        const double start_time = timer.getTime();
        for(num_iter_ = 0;; num_iter_++) {
            for(int turns = 0; turns + 1 < (int)states_.size(); turns++) {
                if(timer.getTime() - start_time > search_time_) {
                    goto TIME_OVER;
                }
                if(states_[turns].size() == 0) continue;
                State state = states_[turns].top_min();
                states_[turns].pop_min();
                add_next_states(turns, state);
            }
        }
    TIME_OVER:;
        fprintf(stderr, "chokudai search: num_iter = %d\n", num_iter_);
    }
    const State &get_best_state() const { return states_.back().top_min(); }

   private:
    double search_time_;
    int num_iter_;
    int time_check_iter_;
    vector<IntervalHeap<State>> states_;
    vector<int> max_num_states_;
};

Back to top page