Monge 性・anti-Monge 性の判定 (in O(HW))
(Optimization/monge_checker.hpp)

• View this file on GitHub
• Last update: 2026-11-12 11:56:29+09:00
• Include: #include "Optimization/monge_checker.hpp"

概要

Monge 性・anti-Monge 性を判定する。

仕様

template<class FUNC> bool is_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true)

• 関数 $f(l, r)$ は、$0 \le l < N$, $0 \le r < M$ に対して定義されるとする
  • upper_triangular = true のときは、$0 \le l < r \le N$ を満たす $l, r$ についてのみ調べる
• $f$ が Monge であるかどうかを判定する
• output_detail = true のときは、Monge 性を満たさない箇所を具体的に出力する

template<class FUNC> bool is_anti_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true)

• 関数 $f(l, r)$ は、$0 \le l < N$, $0 \le r < M$ に対して定義されるとする
  • upper_triangular = true のときは、$0 \le l < r \le N$ を満たす $l, r$ についてのみ調べる
• $f$ が anti-Monge であるかどうかを判定する
• output_detail = true のときは、Monge 性を満たさない箇所を具体的に出力する

問題例

• AtCoder ABC 224 B - Mongeness

参考文献

• tatyam: Monge の手引き書

Required by

• Monge 全部乗せ (Optimization/monge_all.hpp)

Verified with

• tests/AtCoder/ABC_224_B_monge_checker.cpp (manual)

Code

#pragma once
#include <bits/stdc++.h>
#include <cassert>
using namespace std;

// check whether N x M matrix f is Monge or not, in O(NM)
template<class FUNC> bool is_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 > f10 + f01) {
                if (output_detail) {
                    cout << "Not Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}

// check whether N x M matrix f is anti-Monge or not, in O(NM)
template<class FUNC> bool is_anti_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 < f10 + f01) {
                if (output_detail) {
                    cout << "Not anti-Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}

#line 2 "Optimization/monge_checker.hpp"
#include <bits/stdc++.h>
#line 4 "Optimization/monge_checker.hpp"
using namespace std;

// check whether N x M matrix f is Monge or not, in O(NM)
template<class FUNC> bool is_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 > f10 + f01) {
                if (output_detail) {
                    cout << "Not Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}

// check whether N x M matrix f is anti-Monge or not, in O(NM)
template<class FUNC> bool is_anti_monge
(int N, int M, const FUNC &f, bool upper_triangular = false, bool output_detail = true) {
    assert(N > 0 && M > 0);
    for (int i = 0; i + 1 < N; i++) {
        for (int j = (upper_triangular ? i+2 : 0); j + 1 < M; j++) {
            auto f00 = f(i, j), f01 = f(i, j + 1), f10 = f(i + 1, j), f11 = f(i + 1, j + 1);
            if (f00 + f11 < f10 + f01) {
                if (output_detail) {
                    cout << "Not anti-Monge! " << endl;
                    cout << "f(" << i << ", " << j << ") = " << f(i, j) << ", ";
                    cout << "f(" << i << ", " << j + 1 << ") = " << f(i, j + 1) << endl;
                    cout << "f(" << i + 1 << ", " << j << ") = " << f(i + 1, j) << ", ";
                    cout << "f(" << i + 1 << ", " << j + 1 << ") = " << f(i + 1, j + 1) << endl;
                }
                return false;
            }
        }
    }
    return true;
}

Back to top page