【writeup】nitac_mini_ctf、PPC問題のACコード

Pathway and Street

Bの道(コスト101333)を通りたく無い。(が、やむを得ず通らないといけない場合もある) そこで、コストを「firstをBの回数、secondをAの距離」となるpairで持つとそのままダイクストラ出来て良いです。 (段階的に渡れるBの数を増やす解法もあり得るけど面倒だと思う)

前半ライブラリ張ったので長い

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>
#include <fstream>

std::ifstream in("input.txt");
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;


int32_t N,A,B;


#include <queue>
#include <vector>
#include <functional>
#include <utility>
#include <algorithm>
#include <iterator>

using COST_T = std::pair<int32_t, uint64_t>;
constexpr uint32_t N_MAX = 100000;
constexpr COST_T INF{ 1000000, 1000000000000000 };//std::numeric_limits<double>::infinity()

#if defined(_MSC_VER) && defined(_DEBUG)
//static_assert(false, "リリースでコンパイルしないと遅いよ!!");
#endif

struct edge {
    uint32_t to;
    COST_T cost;
    edge() {}
    edge(uint32_t to_, COST_T cost_)
        :to(to_), cost(cost_) {}
};
std::vector<edge> graph[N_MAX];

//ダイクストラ
COST_T D[N_MAX];
void Dijkstra(uint32_t s)
{
    using P = std::pair<COST_T, uint32_t>;//cost pos
    std::priority_queue<P, std::vector<P>, std::greater<>> que;
    std::fill(std::begin(D), std::end(D), INF);

    D[s].first = 0;
    D[s].second = 0;
    que.emplace(COST_T{ 0 ,0}, s);
    while (!que.empty())
    {
        auto p = que.top(); que.pop();
        const auto& nowpos = p.second;
        const auto& nowcost = p.first;
        if (D[nowpos] < nowcost) { continue; }

        //for (int32_t to = 0; to < N; ++to)
        //{
        // auto cost = nowcost + graph[nowpos][to];
        // if (cost < D[to]) {
        //     D[to] = cost;
        //     que.emplace(D[to], to);
        // }
        //}

        for (const auto& e : graph[nowpos])
        {
            auto cost = nowcost ;
            cost.first += e.cost.first;
            cost.second += e.cost.second;
            if (cost < D[e.to]) {
                D[e.to] = cost;
                que.emplace(cost, e.to);
            }
        }

    }
}

template<typename Arithmetic, typename Integral>
Arithmetic
ipow(Arithmetic bace, Integral n)
{
    //繰り返し二条法
    auto res = (Arithmetic)(1);
    while (n > 0) {
        if (n & 1) res *= bace;
        bace *= bace;
        n >>= 1;
    }
    return res;
}
constexpr bool is_prime(uint32_t N)
{
    if (N <= 1) {
        return false;
    }
    for (size_t i = 2; i*i <= N; ++i)
    {
        if (N%i == 0) {
            return false;
        }
    }
    return true;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
    static constexpr auto MOD = MOD_;
    static_assert(!(MOD <= 2), "MOD cannot be below 2.");
    static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
    static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
    constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v += other;
    }
    constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v -= other;
    }
    constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v *= other;
    }
    constexpr auto operator/(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v /= other;
    }
    constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
    {
        a += other.a;
        if (MOD <= a) { a -= MOD; };
        return *this;
    }
    constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
    {
        if (a >= other.a) {
            a -= other.a;
        }
        else {
            a = (a + MOD) - other.a;
        }
        return *this;
    }
    constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
    {
#if 1
        a *= other.a;
        a %= MOD;
#else
       //MOD <= (MAXUINT64 / 2)条件下
       uint64_t b = other.a, v = 0;
       while (b > 0) {
           if (b & 1) {
               v += a;
               if (v >= MOD)v -= MOD;
           }
           a += a;
           if (MOD <= a)a -= MOD;
           b >>= 1;
       }
       a = v;
#endif
        return *this;
    }
    constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept
    {
        return *this *= ~other;
    }
    constexpr mint_base<MOD> operator+()const noexcept { return *this; }
    constexpr mint_base<MOD> operator-()const noexcept
    {
        return{ MOD - a, mod_value_tag{} };
    }
    constexpr mint_base<MOD>& operator++() noexcept
    {
        if (MOD <= ++a) { a = 0; };
        return *this;
    }
    constexpr mint_base<MOD>& operator--() noexcept
    {
        if (a <= 0) { a = MOD; };
        --a;
        return *this;
    }
    constexpr mint_base<MOD> operator++(int) noexcept
    {
        auto tmp = *this;
        ++*this;
        return tmp;
    }
    constexpr mint_base<MOD> operator--(int) noexcept
    {
        auto tmp = *this;
        --*this;
        return tmp;
    }
    constexpr mint_base<MOD> operator~()const noexcept
    {
        return ipow(*this, e_phi - 1);
    }
    constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
    {
        a = other.a;
        return *this;
    }
    constexpr explicit operator uint64_t()const noexcept
    {
        return a;
    }
    constexpr explicit operator unsigned()const noexcept
    {
        return (unsigned)a;
    }
    static constexpr uint64_t getmod() noexcept
    {
        return MOD;
    }
    constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
    constexpr mint_base()noexcept : a(0) {}
    struct mod_value_tag {};
    constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
    static constexpr uint64_t get_e_phi()noexcept {
        //オイラー値の導出
        uint64_t temp = MOD;
        uint64_t m_ = MOD;
        for (uint64_t i = 2; i * i <= m_; ++i)
        {
            if (m_ % i == 0)
            {
                temp = temp / i * (i - 1);
                for (; m_ % i == 0; m_ /= i);
            }
        }
        if (m_ != 1)temp = temp / m_ * (m_ - 1);
        return temp;
    }
    static constexpr uint64_t e_phi = get_e_phi();//オイラー値
    uint64_t a;
};
//mint_base型用の累乗関数
template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept
{
    mint_base<MOD> res = 1;
    while (n > 0)
    {
        if (n & 1)res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
//mint_baseの階乗計算
//O(x)時間が必要のため、fact_set関数を推奨する。
template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept
{
    mint_base<MOD> res(1);
    for (uint64_t i = 1; i <= (uint64_t)x; ++i)
    {
        res *= i;
    }
    return res;
}
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(x)時間が必要
template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1))
{
    mint_base<MOD> res(1);
    std::vector<mint_base<MOD>> set((uint64_t)(x)+1);
    set[0] = 1;
    for (uint64_t i = 1; i <= (uint64_t)x; ++i)
    {
        res *= i;
        set[i] = res;
    }
    return res;
}
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
    os << (uint64_t)i;
    return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
    uint64_t tmp;
    is >> tmp;
    i = tmp;
    return is;
}
typedef mint_base<1000000007> mint;
namespace mint_literal {
    constexpr mint operator""_mi(unsigned long long x)noexcept {
        return mint(x);
    }
}
using namespace mint_literal;
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(N)
template<int32_t X, uint64_t MOD = mint::MOD>
/*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c()
{
    mint_base<MOD> res(1);
    std::array<mint_base<MOD>, X + 1> set;
    set[0] = 1;
    for (int32_t i = 1; i <= X; ++i)
    {
        res *= i;
        set[i] = res;
    }
    return set;
}
template<typename RET = mint, typename Integral>
RET combination(Integral all, Integral get)
{
    assert(all >= get);
    get = std::min(all - get, get);
#if 1
    //時間計算量O(1)+初期化O(NlogMOD)
    static_assert(false, "");
    static const auto fact_v = fact_set_c<要素数 + 1>();
    static const auto fact_div_v = [&]() {
        auto tmp = fact_v;
        for (auto& i : tmp) { i = ~i; }
        return tmp;
    }();
    //return fact_v[all] / (fact_v[get] * fact_v[all - get]);
    return fact_v[all] * fact_div_v[get] * fact_div_v[all - get];
#elif 0
   //時間計算量O(1)
   //空間計算量、初期化時間計算量O(N^2)
   constexpr int32_t ALL_MAX = 要素数;// 10'000;
   static std::vector<RET> DP_comb[ALL_MAX + 1];
   if (!DP_comb[all].empty())
   {
       return DP_comb[all][get];
   }

   if (DP_comb[0].empty())
   {
       DP_comb[0].resize(1);
       DP_comb[0][0] = (RET)1;
       DP_comb[1].resize(1);
       DP_comb[1][0] = (RET)1;
   }
   for (int32_t i = 2; i <= all; i++)
   {
       if (DP_comb[i].empty())
       {
           int32_t size = i / 2 + 1;
           DP_comb[i].resize(size);
           DP_comb[i][0] = (RET)1;
           for (int32_t j = 1; j < size - 1; j++)
           {
               DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j];
           }
           DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)];
       }
   }
   return DP_comb[all][get];
#else
   //時間計算量O(get * logMOD)
   RET ret = (RET)1;
   for (Integral i = 1; i <= get; ++i)
   {
       ret *= all + 1 - i;
       ret /= i;
   }
   return ret;
#endif
}

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    in >> N>>A>>B;

    for (int32_t i = 0; i < A; i++)
    {
        int64_t a, b, c;
        in >> a >> b >> c; --a; --b;
        graph[a].emplace_back((int32_t)b, COST_T{ 0, (uint64_t)c });
        graph[b].emplace_back((int32_t)a, COST_T{ 0, c });
    }
    for (int32_t i = 0; i < B; i++)
    {
        int64_t a, b;
        in >> a >> b; --a; --b;
        graph[a].emplace_back(b, COST_T{ 1, 0 });
        graph[b].emplace_back(a, COST_T{ 1, 0 });
    }

    Dijkstra(0);

    mint b = 10;
    b = ipow(b, 1333);

    mint sum = 0;
    for (size_t i = 0; i < N; i++)
    {
        sum += mint(D[i].first)*b + D[i].second;
    }

    out << sum << endl;




    return 0;
}
#endif

scramble

相変わらず前半ライブラリのみです。 部分文字列の接頭文字列の個数を貪欲に数えたら何故か通ってしまった。(証明してない)

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

std::ifstream in("input.txt");
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

template<typename Arithmetic, typename Integral>
std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic>
ipow(Arithmetic bace, Integral n)
{
    //繰り返し二条法
    auto res = (Arithmetic)(1);
    while (n > 0) {
        if (n & 1) res *= bace;
        bace *= bace;
        n >>= 1;
    }
    return res;
}
constexpr bool is_prime(uint32_t N)
{
    if (N <= 1) {
        return false;
    }
    for (size_t i = 2; i*i <= N; ++i)
    {
        if (N%i == 0) {
            return false;
        }
    }
    return true;
}
template <uint64_t MOD> class mint_base;
//mint_base_base型用の累乗関数
template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept;
//mod計算を自動で行う整数テンプレートクラス
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
    static constexpr auto MOD = MOD_;
    static_assert(!(MOD <= 2), "MOD cannot be below 2.");
    static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
    static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
    constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v += other;
    }
    constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v -= other;
    }
    constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v *= other;
    }
    constexpr auto operator/(const mint_base<MOD> &other)const noexcept
    {
        auto v = *this;
        return v /= other;
    }
    constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
    {
        a += other.a;
        if (MOD <= a) { a -= MOD; };
        return *this;
    }
    constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
    {
        if (a >= other.a) {
            a -= other.a;
        }
        else {
            a = (a + MOD) - other.a;
        }
        return *this;
    }
    constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
    {
#if 1
        a *= other.a;
        a %= MOD;
#else
       //MOD <= (MAXUINT64 / 2)条件下
       uint64_t b = other.a, v = 0;
       while (b > 0) {
           if (b & 1) {
               v += a;
               if (v >= MOD)v -= MOD;
           }
           a += a;
           if (MOD <= a)a -= MOD;
           b >>= 1;
       }
       a = v;
#endif
        return *this;
    }
    constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept
    {
        return *this *= ~other;
    }
    constexpr mint_base<MOD> operator+()const noexcept { return *this; }
    constexpr mint_base<MOD> operator-()const noexcept
    {
        return{ MOD - a, mod_value_tag{} };
    }
    constexpr mint_base<MOD>& operator++() noexcept
    {
        if (MOD <= ++a) { a = 0; };
        return *this;
    }
    constexpr mint_base<MOD>& operator--() noexcept
    {
        if (a <= 0) { a = MOD; };
        --a;
        return *this;
    }
    constexpr mint_base<MOD> operator++(int) noexcept
    {
        auto tmp = *this;
        ++*this;
        return tmp;
    }
    constexpr mint_base<MOD> operator--(int) noexcept
    {
        auto tmp = *this;
        --*this;
        return tmp;
    }
    constexpr mint_base<MOD> operator~()const noexcept
    {
        return ipow(*this, e_phi - 1);
    }
    constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
    {
        a = other.a;
        return *this;
    }
    constexpr explicit operator uint64_t()const noexcept
    {
        return a;
    }
    constexpr explicit operator unsigned()const noexcept
    {
        return (unsigned)a;
    }
    static constexpr uint64_t getmod() noexcept
    {
        return MOD;
    }
    constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
    constexpr mint_base()noexcept : a(0) {}
    struct mod_value_tag {};
    constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
    static constexpr uint64_t get_e_phi()noexcept {
        //オイラー値の導出
        uint64_t temp = MOD;
        uint64_t m_ = MOD;
        for (uint64_t i = 2; i * i <= m_; ++i)
        {
            if (m_ % i == 0)
            {
                temp = temp / i * (i - 1);
                for (; m_ % i == 0; m_ /= i);
            }
        }
        if (m_ != 1)temp = temp / m_ * (m_ - 1);
        return temp;
    }
    static constexpr uint64_t e_phi = get_e_phi();//オイラー値
    uint64_t a;
};
//mint_base型用の累乗関数
template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept
{
    mint_base<MOD> res = 1;
    while (n > 0)
    {
        if (n & 1)res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}
//mint_baseの階乗計算
//O(x)時間が必要のため、fact_set関数を推奨する。
template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept
{
    mint_base<MOD> res(1);
    for (uint64_t i = 1; i <= (uint64_t)x; ++i)
    {
        res *= i;
    }
    return res;
}
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(x)時間が必要
template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1))
{
    mint_base<MOD> res(1);
    std::vector<mint_base<MOD>> set((uint64_t)(x)+1);
    set[0] = 1;
    for (uint64_t i = 1; i <= (uint64_t)x; ++i)
    {
        res *= i;
        set[i] = res;
    }
    return res;
}
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{
    os << (uint64_t)i;
    return os;
}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{
    uint64_t tmp;
    is >> tmp;
    i = tmp;
    return is;
}
typedef mint_base<1000000007> mint;
namespace mint_literal {
    constexpr mint operator""_mi(unsigned long long x)noexcept {
        return mint(x);
    }
}
using namespace mint_literal;
//mint_baseの階乗計算
//0からxまでの階乗を返す
//O(N)
template<int32_t X, uint64_t MOD = mint::MOD>
/*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c()
{
    mint_base<MOD> res(1);
    std::array<mint_base<MOD>, X + 1> set;
    set[0] = 1;
    for (int32_t i = 1; i <= X; ++i)
    {
        res *= i;
        set[i] = res;
    }
    return set;
}
template<typename RET = mint, typename Integral>
RET combination(Integral all, Integral get)
{
    assert(all >= get);
    get = std::min(all - get, get);
#if 1
    //時間計算量O(1)+初期化O(NlogMOD)
    static_assert(false, "");
    static const auto fact_v = fact_set_c<要素数 + 1>();
    static const auto fact_div_v = [&]() {
        auto tmp = fact_v;
        for (auto& i : tmp) { i = ~i; }
        return tmp;
    }();
    //return fact_v[all] / (fact_v[get] * fact_v[all - get]);
    return fact_v[all] * fact_div_v[get] * fact_div_v[all - get];
#elif 0
   //時間計算量O(1)
   //空間計算量、初期化時間計算量O(N^2)
   constexpr int32_t ALL_MAX = 要素数;// 10'000;
   static std::vector<RET> DP_comb[ALL_MAX + 1];
   if (!DP_comb[all].empty())
   {
       return DP_comb[all][get];
   }

   if (DP_comb[0].empty())
   {
       DP_comb[0].resize(1);
       DP_comb[0][0] = (RET)1;
       DP_comb[1].resize(1);
       DP_comb[1][0] = (RET)1;
   }
   for (int32_t i = 2; i <= all; i++)
   {
       if (DP_comb[i].empty())
       {
           int32_t size = i / 2 + 1;
           DP_comb[i].resize(size);
           DP_comb[i][0] = (RET)1;
           for (int32_t j = 1; j < size - 1; j++)
           {
               DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j];
           }
           DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)];
       }
   }
   return DP_comb[all][get];
#else
   //時間計算量O(get * logMOD)
   RET ret = (RET)1;
   for (Integral i = 1; i <= get; ++i)
   {
       ret *= all + 1 - i;
       ret /= i;
   }
   return ret;
#endif
}

int32_t num[256][100010];
std::string s;

int main()
{
    using std::endl;
    in.sync_with_stdio(false);
    out.sync_with_stdio(false);
    in.tie(nullptr);
    out.tie(nullptr);

    in >> s;
    //for (size_t i = 0; i < s.size(); i++)
    //{
    // num[s[i]][i+1]++;
    //}
    //for (size_t i = 0; i < 256; i++)
    //{
    // for (size_t j = 1; j <= 100000; j++)
    // {
    //     num[i][j] += num[i][j-1];
    // }
    //}

    mint m = 0;
    mint mi = 0;
    mint min = 0;
    mint mini = 0;
    mint minic = 0;
    mint minict = 0;
    mint minictf = 0;

    for (size_t i = 0; i < s.size(); i++)
    {
        if (s[i] == 'm') {
            m += 1;
        }
        if (s[i] == 'i') {
            mi += m;
            mini += min;
        }
        if (s[i] == 'n') {
            min += mi;
        }
        if (s[i] == 'c') {
            minic += mini;
        }
        if (s[i] == 't') {
            minict += minic;
        }
        if (s[i] == 'f') {
            minictf += minict;
        }
    }
    out << minictf << endl;

    return 0;
}
#endif

ICPC2018国内予選参加記(仮原稿)

ICPC2018国内予選参加記(仮原稿)

ICPC2018国内予選の参加記です。本当は別の場所にまともなのを書こうと思っていたんですが、どうも時間が無さそうなのでここで雑に書いてしまいます。

60°(sixty_deg)さん、baton(goodbaton)さんとeiyaで60odnightとして参加しました。

当日までの様子

traP(デジタル創作同好会)と言うサークルに所属しているので、サークル内でチームを組んでもらいました。 どうもその段階でチームが決まっていなかった人の中で上から3人選んだっぽい?

模擬予選の前後に一回ずつ集まってバチャコンをやりました。

一回目は僕がバグらせたのを何とか直して5完+F惜しい 模擬予選は僕が盛大にDをバグらせて4完(ちなみにこれだと学内予選落ち)2018/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni Group 二回目は三人が三人ともバグらせて遅解き5完+F証明出来ないので書かなかったんですが解説を見たら正解だった+H制約見落としで解けなくなってた

チームの動きは、始めに60°さんがAを、僕がDEを、batonさんが全体を読み、A(60°さん)->C(batonさん)->B(60°さん)->D(eiya)という動きがなんとなく出来上がっていました。

当日の様子

僕の目標は(練習のときにバグらせまくっていたので)「バグらせない」ということでした。 本番機にはVisualStudioもマイスニペットも入っていないのでなかなか落ち着かない。 水曜日の練習でbatonさんからVSCodeでデバッガが使えるという事を聞いて設定したので模擬予選での失態を繰り返さないようにと意気込む。 (普段の環境がVisualStudioなのでデバッガが無いと生きていけない) 以下回想なんですが、記憶が無いので時系列が入れ替わってたり飛んでたりしそう。

まず予定通りeiyaがDを読むんですが、解けない(は?) 仕方が無いのでEを見る。 解けない。愚直に足すとTLEするのでダブリングが必要となりそうとなる。 この時点でbatonさんが圧倒的目力でBがヤバそうと見抜き、batonさんがBを解き、60°さんにCを解いてもらうことに。 僕はEもDも解けないのでDを考察。

60°さんが順当にAを通し(有難い)、batonさんのBの実装に取り掛かる。 とりあえずDPをしようとして計算量を確認する。
8C4* 7C4以下 * 6C3以下 * ... *1C1以下
8C4==70だしこれギリギリ行けるのでは???(今計算したら17640000なので普通に間に合う)

この段階でBの実装が変っぽいので交代してDを書いていく。 そのままいい感じに再帰を書こうとしていると、普通に書くと計算量がCじゃなくてPになることに気が付き冷える(後で話を聞くにどうもPでも刈れるので通るらしい) 僕が冷えたのでBの誤読に気が付いたbatonさんに交代。確かこのころ60°さんもCの考察が終わっていた気がするので暫く二人にコンピュータを預けて紙コーディング。 BC通る。凄い。batonさんがE,F,G、60°さんがFを読む。

紙コーディングが終わったので計算量をCにする為の三関数経由の闇再帰を書くとCE(は?) 「lamdaうんちゃらは有効な型ではありません」(みたいな感じだった気がする) 印刷してbatonさんにEを書いてもらう。 ミス一か所見つけたので一旦代わってもらって修正するもまだエラー。テンプレート関数特有の長ったらしいエラーに悪態をついてコードの末尾にエラーメッセージをコピペして再印刷という†悪魔的行為†

batonさんがEの実装の続きをしている間に60°さんに自分のコードの状況を説明したところ、注目していた行の下に原因が書いてあるのに気が付く。 「関数の引数が一致しません」 これやんけ!wとなって交代して修正。

実行したら初期化ミスとかしてたのでそこは直したがまだ無限ループっぽい挙動。 模擬予選ならここで冷えるものの今回はデバッガがあるので一時停止からのステップ実行で洗うとforを無限に回していることが分かる。 原因がオーバーフローなのは明らかなんですが、そもそもオーバーフローするはずが無いので他の個所がヤバそうと主張して印刷して交代。

印刷したコードを睨むとオーバーフローするはずなので該当箇所がやばい(完) batonさんが順調に書いていたのでそのまま紙デバッグ。ちゃんと睡眠をとった頭だったので脳内ステップ実行が出来てバグがめっちゃ見つかる。

一通り紙デバッグが終わって自信を持ったところで交代してもらって書き終わる。 通った!!

batonさんがEを解けそうなので60°さんとFを解くことに。とりあえず今まで出来たFの考察を聞くと三角形の底辺は木を含んでいるはずとのこと。なんかDPっぽいなとか検討違いの事を言いながら考察したところ3辺全て木を含んでいるはずということに気が付く。 これ二辺決めればあと一辺はO(logN)で求められるしギリギリ109で勝ちでは。

batonさんがEを通して(プロ)、コンピュータが空いたのでeiyaが書く。 書き終わるんですがサンプルが通らない。 ここでbatonさんが僕の実装だと三角形の二辺の外の木もカウントしていることに気が付く。(悲しい) 上下は底辺をスライドさせて消していけば良いとして、もう一辺は削除と二分探索を両方やらないといけない。険しい。この時点で残り30~45分くらいだった気がするのでGの実装を諦めてFの実装を続けることにする。 間に合わないとは思いつつもbatonさんに書いてもらい、最後書き終わるもバグらせててサンプルが合わない。悲しい。

コンテスト終了

結果

順位表:LiveSite

全体13位、学内3位でした。 公式な発表は出ていないけれども恐らくアジア地区予選に行けそう!嬉しい! 層が厚すぎるうちの大学で勝ち残れるか微妙だったのでとても良かった。 当日までに黄色復帰にとどまらず橙までもっていきたいなぁ...

今は構築,構文解析,データ構造,アルゴリズムを全部batonさんに投げているのでどれかは出来るようにならないとないけない。 せめてダイクストラ,ワーシャルフロイド,二分探索,BITくらいは空で書けるようになりたい。

AtCoder Regular Contest 098参加記

部内での共有用に久々に書いてみようと思います。
まあ参加記であって解説では無いんですが...

AtCoder Regular Contest 098 - AtCoder

C - Attention

リーダーを決めると、後は他の人がどちらを向いているか数えるだけになって嬉しいです。
が、よく見るとN<=10^5なので解けません。難しい。
「範囲和を取るときは累積和」の一般的なテクが使えるのでこれを使いましょう。
-1参照しそうになったり+-1で結構悩んでしまった。
Submission #2562951 - AtCoder Regular Contest 098

※ところでpythonのstr.count関数とかCのstrlen関数とかはO(|S|)かかるので気を付けましょう。

D - Xor Sum 2

D - Xor Sumという配点の割に正解者がかなり少なかったことで有名な問題(僕にとっては難しい問題、強い人にとっては割と典型らしい)があるのでちょっと身構えました。
が、名前が似た問題は往々にして全然違う問題なので、先入観を捨てて取り掛かりましょう。

まずは問題整理
xorとsumはかなり似た演算ですが、少しだけ違いがあります。

xor sum
0,0 0 0
0,1 1 1
1,0 1 1
1,1 0 10

これを見るとAl...Arでの演算に(bit単位で)1,1を含むとき(bit&を使うとAl&...&Ar!=0)だけが、不等号が成り立つ可能性がある事が分かります。
そこで、これが不等号が成り立つ必要十分条件であるとエスパーします。(これは僕が証明をしていないという意味)

そうすると、(l,r)のとき等号が成り立つならば(l+1,r)のとき等号が成り立つ事がわかります
つまり、とりあえず出来るだけ長めのものを数え上げれば数え上げの総数が減って嬉しい感じになりそうです。
こういう時に重複を省きながら数え上げる一般的なテクとして、「末尾(or先頭)がiのとき」を数え上げるというものがあります。(たぶんこのテクに名前は無い)

また、(l,r)のとき等号が成り立たないならば(l-1,r)のとき等号は成り立たない事もわかります
言い換えると、短いもので成り立たないならば、より長いものでは成り立たないということです。

これは
区間の先頭を1ずつ右にずらす
区間長が変わる
のでこういうときの一般的なテクの「尺取り法」を試してみたくなります。

実際に考えてみると
・左側は縮む一方で、伸びることは無い
・伸びる方は今までの累積和/xorに加算/xorすることで構築可能
・縮む方は今までの累積和/xorに減算/xorすることで構築可能
であるので尺取り法が使えることが分かります。

この方針でO(N)なので解くことが出来ます。
Submission #2564186 - AtCoder Regular Contest 098

E - Range Minimum Queries

X−Yをできるだけ小さくしたい問題ときたら決め打ち+二分探索みたいな先入観で突っ込んでいって大当たりしました。


まあそれだけでは解けないんですが。
ここまででO(NlogN)使ってるけどN<=2000なのでまだO(N)使える

範囲内の値を
・Y以下の値を避けながら
・Q 回取り除かないといけない
ので少し考えます。
Y以下の値が無ければ貪欲に端から取り除いて良いのは明らか(本番ではこれ証明してなかった)
Y単調増加させればY以下の値が範囲内に存在するかはBIT使って求められるなぁ(使わない考察)
値を取り除く操作をしたい=>区間のN番目の最小値を求めたい=>尺取りmultisetで行けそう

書く。
Submission #2565822 - AtCoder Regular Contest 098
TLEしたなんで

良く考えるとO(N^2 * (logN)^2)
logNは1では無くて10(重要)
10^8だね悲しい。

しょうがないので対策を考える。
取り除くやついちいち識別しているからlogかかるので、差異を無視したい。
出来るね。
書く。コードが闇。特にdeleted_useable (Qに含められるものの内、既に操作をして取り除いたやつの個数)
Submission #2567510 - AtCoder Regular Contest 098
通った

TLEに気が付いてればもうちょいタイムロス少なく出来そう

余談
言れて気が付いた

F - Donation

まだACしてないですが、結構惜しいとこまで行った気がする(気のせいかもしれない)
始めよりも終わりの方が制約が大きいのでとりあえず遡りを考えてみる。
行けるところ適当に行って損しないので、適当に全部行くことが出来る。これは良い。
始点O(N) * 全部行けるかどうか試すO(NlogN)
600点分くらい解いた気がするけどまだ間に合わない。
始めに持っておく余剰資金分を決めてやると走査を同時に走らせることが出来るので始点O(N)が消滅してO(NlogN)で間に合う
出会ったらマージ出来るので計算量をO(NlogN)で頭打ちに出来る。
まあ識別番号としてUFtree使ったりとかする必要はありますが。

実装は間に合わない
2018-05-26 22:39:59の提出:
Submission #2570788 - AtCoder Regular Contest 098
テストも何もしてなかったので、まず出力部が正しくなくて、本当は

out << std::accumulate(all_range(B),(int64_t)0)+ok_range << endl;

って書きたかった。
ところでこれ直してもまだ通らないんですが何処が間違ってるんでしょうね。

SoundHound Inc. Programming Contest 2018 (春):D - 建物 を解いたという日記

問題:D - 建物

 

・DP(H,W)っぽい

・bitDPをしたいけど、制約的に不可能

・「部屋 (1,j) からスタートして(H,任意)から建物を出るときの最大利益」と誤読

・入室回数を出来るだけ減らしたいので、通過or往復で、解説の図のような通行しかしない

f:id:eiya5498513:20180128081800p:plain<=解説の図

・往復部分は独立に求められそう(本当か?本当だね)

・Tの位置全探索すれば良いけど全探索したくないね(TLE)=>DPの漸化式の中のforをならす一般的なテク

typo酷いね(基本的にwと2とsが打てなかった)

・Pの処理間違えて悲しいね

・誤読してて悲しいね=>うーん。明らかに逆にたどっても変わらないし(H,j)からスタートして(1,1)から出ることにするか!w

・通ったら暫定8位でウケる(その後落ちた)

Submission #2022867 - SoundHound Inc. Programming Contest 2018 (春)

 

ところでこれテク的にはDP二回+forならしなのでAGCだと800~1000点くらいで出そう。(サンプル数0)

2buttonsのeiya解

https://hoj.hamako-ths.ed.jp/onlinejudge/contest/121/problems/5
提出しても見られないみたいなのではるだけはっておきます。

ところで通常問題の方のURLをはりたかったのですが、なんかidがずれるみたいなのではりません。
現時点(2017/12/2)ではidは869です。

部分点(20点)

#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;

int32_t H,W;
int32_t ah,aw,bh,bw;
int32_t map[1000][1000];
int32_t distA(int32_t h, int32_t w) { return std::abs(h - ah) + std::abs(w - aw); }
int32_t distB(int32_t h, int32_t w) { return std::abs(h - bh) + std::abs(w - bw); }

int64_t func(int32_t i, int32_t j, bool myturn)//Aがtrue、先行がtrue
{
	bool finish = true;
	for (int32_t h = 0; h < H; h++)
		for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) >= j) {
			finish = false;
		}
	}
	if (finish) {
		return 0;
	}

	auto pattA = func(i + 1, j, !myturn);
	if(myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) == i && distB(h, w) >= j) {
			pattA += map[h][w];
		}
	}

	auto pattB = func(i, j + 1, !myturn);
	if (myturn)
		for (int32_t h = 0; h < H; h++)
			for (int32_t w = 0; w < W; w++)
	{
		if (distA(h, w) >= i && distB(h, w) == j) {
			pattB += map[h][w];
		}
	}

	if (myturn == (pattA>pattB)) {
		return pattA;
	}
	else {
		return pattB;
	}
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> H>>W;
	in >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		in >> map[h][w];
	}

	out << func(0, 0, true) << endl;;

	return 0;
}
#endif

満点

#include <iostream>
#include <cstdint>
#include <algorithm>


int32_t H, W;
int32_t ah, aw;
int32_t bh, bw;
int32_t map[1000][1000];

const int32_t DIST_MAX = 2000;
int64_t scoreA[DIST_MAX+2][DIST_MAX+2];//自分、相手
int64_t scoreB[DIST_MAX+2][DIST_MAX+2];//自分、相手

const int64_t INF = 100010002000000000;
int64_t dp[DIST_MAX + 2][DIST_MAX + 2];
int64_t func(int32_t a, int32_t b)
{
	if (a == DIST_MAX+1 && b == DIST_MAX+1)
	{
		return 0;
	}
	if (a > DIST_MAX+1 || b > DIST_MAX+1) {
		return INF;
	}
	if (dp[a][b] != INF) { return dp[a][b]; }
	return dp[a][b] = std::max(
		-func(a + 1, b) + scoreA[a][b],
		-func(a, b + 1) + scoreB[b][a]
	);
}

int main()
{
	using std::cin;
	using std::cout;
	using std::endl;
	for (auto& arr : dp)for (auto& i : arr) { i = INF; }
	cin >> H >> W;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		cin >> map[h][w];
	}
	cin >> ah >> aw >> bh >> bw; --ah; --aw; --bh; --bw;

	int64_t sum = 0;
	for (int32_t h = 0; h < H; ++h) for (int32_t w = 0; w < W; ++w) {
		int32_t dist_a = std::abs(h - ah) + std::abs(w - aw);
		int32_t dist_b = std::abs(h - bh) + std::abs(w - bw);
		scoreA[dist_a][dist_b] += map[h][w];
		scoreB[dist_b][dist_a] += map[h][w];
		sum += map[h][w];
	}
	for (int32_t distme = 0; distme <= DIST_MAX; ++distme) {
		for (int32_t distopp = DIST_MAX-1; distopp >= 0; --distopp) {
			scoreA[distme][distopp] += scoreA[distme][distopp + 1];
			scoreB[distme][distopp] += scoreB[distme][distopp + 1];
		}
	}

	cout << (func(0, 0)+ sum)/2 << endl;
}

F - Three Gluttons(CODE FESTIVAL 2017 qual C)

この問題です。
F - Three Gluttons


というわけで解説と考察の道筋を書きます。

実際にした考察

「AとBの残っている寿司」と「あと何個食べるか」を引数にDPが出来そう

  • 「状態」が2^Nになるなぁ...。状態をNで表せるとO(N^3)で解けそう。
  • でも表せたとしてDPの遷移を思いつかないな...

...色々試します...
始めは必ず取らないといけないとか、最後二つは絶対に取れないとか考えましたが、そこから派生出来ない...
(真隣に依存する操作が無い為、端が決まっても嬉しくないなぁ...)

そのうち「逆順をやってみるか」と思います。
逆順で状態をNで表せるように頑張ります。
...そもそもこの問題の場合の逆順ってなんだ???(しばらく混乱)
(ちなみに考察中は逆順に「食べる」という用語で考察したんですが、書いてみたら紛らわしかったので「吐き出す」と書いておきます)

  1. けんかしないで最後まで取る=>0個のこる
  2. そこから一個取る前の状態に戻す
  3. ああ、後ろ二つは絶対に取れないんだっけ。後ろから三つ目に吐き出すか?
  4. なんで後ろから三つ目でないといけないんだ??<=ここ詰めよう
  5. DPみたいにしたいので、今吐き出したものの順位をa,b(0<=a,b<N)と置くか

Aさんが一個目にxを吐き出すとき、他の人はxを食べられないので、Bさんがxをb以上の順位にしていると困るな...
(補足:Bさんがxをbよりも上の順位にしている場合、xもB[b]も残っている状況ではBさんはxを取りたいのでけんかが起こります)
=>逆に言えば、Aさんが吐き出せるのはBさんにとってbよりも下の順位のものだけだな???
ということは...
Aにとってaより上の順位のもの:必ず吐き出すことが可能、下の順位のもの:後からは絶対に吐き出せない
(補足:a<jについてAさんはA[j]よりもA[a]を先に食べる<=>A[j]よりもA[a]を後に吐き出す)
Bも同じ
=>これなら「AとBの残っている(吐き出せる寿司)寿司」をa,bという境界を持ってやることでN^2通りで表せる!
=>よしO(N^3)DP出来た!!!

...これは罠で、DPの状態(引数)は決めることが出来ましたが、まだ遷移が出来ていません。
考えます。

吐き出せるやつを全部試すとN^2かかって間に合わないし...
...思いつかないですね。

仕方がないので「吐き出せるやつを全部試す」の方針をもう一度考えます。
...そういえばこれって、前の方のやつを全部足す形だな...
=>累積和が使えるパターンでは!??(ここは一般的なテクとして知識を持っておかないと辛い)

こういう問題の場合、僕はコードを実際に書いて、それを無理やり整形して解くことが多いので、出来そうという方針が立ったこの段階でコードを書き始めます。

DPの説明

後半にコードが書いてあるので、そちらと見比べながら見てください。

DPの定義式を考えます。
本番中僕は言語化せずに感覚的にやってしまったのですが、頑張って言語化します。

DP[a][b][taberu]を

  • 「Aはa、Bはbを直前に吐き出した」つまり「Aはaより好きなものを、Bはbより好きなものを吐き出すことが出来る」
  • 「A,B,Cはあとtaberu個吐き出す」

の条件を満たすようにCを作ったとき、作れるCの通り数
とします。
A,Bの先頭を吐き出すまでCの構成を続けるので、完成した場合であるa=0,b=0のときCの通り数は1です。
つまり
DP[0][0][0] = 1
です。

例えば、
入力例 3

6
1 2 3 4 5 6
2 1 4 3 6 5

の時は
DP[2][2][1]=20
みたいになります。
a,b,は0-indexed、taberuは個数(0個1個2個...N個)であることに注意してください。
(計算方法は後述)


「次にA,Bが吐き出すものの順位」をnext_a,next_bとします。(これは二重ループで決め打ちします)
A[i],B[i]を問題文通りに、i番目に好きな寿司とします。(コードでは0-indexed)
Aがxが何番目に好きかをN_EATED_A[x]、Bがxが何番目に好きかをN_EATED_B[x]とします。(変数の命名は突っ込まない約束です)
AがA[next_a]を吐き出す為には、BがB[next_b]よりもA[next_a]が嫌いである、つまりnext_b < N_EATED_B[A[next_a]]である必要があります。
同様にBがB[next_b]を吐き出す為にはnext_a < N_EATED_A[B[next_b]]である必要があります。
これを満たしているとき、AはA[next_a]、BはB[next_b]を吐き出します。
この時のCの通り数を計算します。

Cは自由に決められるので、吐き出すごとに生まれる制約を使ってCを少しずつ決めてやるイメージでやります。

Cが吐き出すものをA,Bと同じようにC[next_c]と仮置きします。あとN_EATED_C[x]も同じように仮置きします。
まず、A,Bの時と同じ理由で、next_c < N_EATED_C[A[next_a]] かつ next_c < N_EATED_C[B[next_b]]である必要が有ります。
なので、next_cの前にA[next_a]とB[next_b]を好きな順番で入れます。
また、これまたA,Bのときと同じ理由で、next_a < N_EATED_A[C[next_c]] かつnext_b < N_EATED_B[C[next_c]]である必要が有ります。
これを満たす為に、C[next_c]は上の条件を満たす寿司から一つ選んで吐き出します。
f:id:eiya5498513:20171023103858j:plain
この通り数が、コードの

*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3)

に相当します。
tabetaは「今までに吐き出した数」です。(コードは本番のものなので、「吐き出す」が「食べる」になっています)
始め二つが、「A[next_a]とB[next_b]を好きな順番で入れる」の通り数です。Cの中で順番が確定しているのは「今までにA,B,Cが吐き出した総数」個です。そこに好きな順番でA[next_a]とB[next_b]を入れるのでこうなります。
最後は、C[next_c]の選び方の通り数です。C_tori[a_next][b_next]は「next_a < N_EATED_A[x] かつnext_b < N_EATED_B[x]」を満たすxの数です。このうち、「今までにA,B,Cが吐き出した総数」個は既に吐き出されているので、Cが新たに吐き出せるのは(C_tori[a_next][b_next]- tabeta*3)個です。

a_next,b_nextが決まっているときの遷移は、Cを適当に決める=>次の状態に移るという動作をし、これがCの構成の一つのパターンです。
これで遷移を書くと↓のようになります。(言語での説明ができなかった人の顔)

mint res = 0;
int32_t tabeta = eat_all - taberu;
for (int32_t a_next = a-1; a_next >= 0; --a_next)
for (int32_t b_next = b-1; b_next >= 0; --b_next)
{
	//↓つまり、「AがA[a_next],BがB[b_next]を食べる」というのが可能ならば
	if (b_next &lt; N_EATED_B[A[a_next]] && a_next &lt; N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		//Cを適当に決める=>次の状態に移るという動作をするので
		//通り数を数えるDPと同じようにしてやった後、Cの選び方をかける
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
}

↓考察ノート(本番に実際使ったもの)
f:id:eiya5498513:20171023000702j:plain

↓この段階でのコード(メモ化していないので、O(N^5)よりもさらに遅いです)
本番で使ったコードのバグを少し直しただけなので、「吐き出す」が「食べる」になっています。
mintの定義は省略してありますが、要はmodを勝手にとるintです。詳しくはこちら:C++14用mod_int - 永夜の記録

int32_t eat_all;
int32_t N_EATED_A[400];
int32_t N_EATED_B[400];
int32_t C_tori[400][400];//a,b
int32_t N;
int32_t A[400];
int32_t B[400];
mint func(int a, int b, int taberu)
{
	if (a == 0 || b == 0) {
		if (a == 0 && b == 0 && taberu == 0) {
			return 1_mi;
		}
		else {
			return 0_mi;
		}
	}
	if (taberu == 0) {
		assert(false);
		return 0_mi;
	}

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
	for (int32_t a_next = a-1; a_next >= 0; --a_next)
	for (int32_t b_next = b-1; b_next >= 0; --b_next)
	{
		if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
			res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
		}
	}
	return func3(a, b, taberu);
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N; eat_all = N / 3;
	for (int32_t i = 0; i < N; i++)
	{
		in >> A[i]; --A[i];
		N_EATED_A[A[i]] = i;
	}
	for (int32_t i = 0; i < N; i++)
	{
		in >> B[i]; --B[i];
		N_EATED_B[B[i]] = i;
	}


	for (int32_t a = N - 1; a >= 0; --a)
		for (int32_t b = N - 1; b >= 0; --b)
		{
			if (b == N - 1) {
				C_tori[a][b] = 0;
			}
			else {
				C_tori[a][b] = C_tori[a][b + 1];
				//B[b+1]が使えるようになる
				if (a < N_EATED_A[B[b + 1]]) {
					++C_tori[a][b];
				}
			}
			//for (int32_t i = 0; i < N; i++)
			//{
			//	if(a<N_EATED_A[i] && b<N_EATED_B[i])
			//		++C_tori[a][b];
			//}
		}

//Nよりも順位が良い全てのもの、つまり全ての寿司を吐き出せます

	out << func(N, N, eat_all) << endl;

	return 0;
}

オーダーを減らす

この段階で、O(N^5)の解法が出来たので、オーダーを減らします。
先ほども書きましたが、

for (int32_t a_next = a-1; a_next >= 0; --a_next)
for (int32_t b_next = b-1; b_next >= 0; --b_next)
{
	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
}

が累積和っぽいテクを使うことで減らせます。(ここは発想ではなく知識です)
ここでeiya流雑なDPを使ってまずbのループを消していきます。

for (int32_t a_next = a-1; a_next >= 0; --a_next)
	res += func2(a_next,b,taberu);

になるようにfunc2を書きます。
とりあえずコピペしてメモ化します。

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
 
	for (int32_t b_next = b-1; b_next >= 0; --b_next)
	{
		if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
			res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
		}
	}
	return DP2[a_next][b][taberu] = res;
}

func2は[0,b)の

if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
	res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
}

の和なので、こうします。

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if(b==0){return 0_mi;}//0_miはmint(0)と同じ意味です。
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;
 	
 	//b_next==b-1の処理
	int b_next = b-1;
 	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta*3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next]- tabeta*3);
	}
	//b_nextが[0,b-1)の処理
	res += func2(a_next, b-1, taberu);
	return DP2[a_next][b][taberu] = res;
}

これでfunc2の一回当たりの実行時間はO(1)になりました。

なのでfuncの

for (int32_t a_next = a-1; a_next >= 0; --a_next)
	res += func2(a_next,b,taberu);

はこの時点でO(N)です。

同じようにfuncのaのループも消すとこうなります。
実際に書いたコードはこっち:
Submission #1705609 - CODE FESTIVAL 2017 qual C

int32_t eat_all;
int32_t N_EATED_A[400];
int32_t N_EATED_B[400];
int32_t C_tori[400][400];//a,b
int32_t N;
int32_t A[400];
int32_t B[400];
mint func(int a, int b, int taberu);

bool DP2_u[400][400][400];
mint DP2[400][400][400];
mint func2(int32_t a_next, int32_t b, int32_t taberu)
{
	if (b == 0) { return 0_mi; }//0_miはmint(0)と同じ意味です。
	if (DP2_u[a_next][b][taberu]) {
		return DP2[a_next][b][taberu];
	}
	DP2_u[a_next][b][taberu] = true;

	mint res = 0;
	int32_t tabeta = eat_all - taberu;

	//b_next==b-1の処理
	int b_next = b - 1;
	if (b_next < N_EATED_B[A[a_next]] && a_next < N_EATED_A[B[b_next]] && (C_tori[a_next][b_next] > tabeta * 3)) {
		res += func(a_next, b_next, taberu - 1)*(3 * tabeta + 1)*(3 * tabeta + 2)*(C_tori[a_next][b_next] - tabeta * 3);
	}
	//b_nextが[0,b-1)の処理
	res += func2(a_next, b - 1, taberu);
	return DP2[a_next][b][taberu] = res;
}

bool DP3_u[400][400][400];
mint DP3[400][400][400];
mint func(int a, int b, int taberu)
{
	if (a == 0 || b == 0) {
		if (a == 0 && b == 0 && taberu == 0) {
			return 1_mi;
		}
		else {
			return 0_mi;
		}
	}
	if (taberu == 0) {
		return 0_mi;
	}

	if (DP3_u[a][b][taberu]) {
		return DP3[a][b][taberu];
	}
	DP3_u[a][b][taberu] = true;

	auto a_next = a - 1;
	DP3[a][b][taberu] += func2(a_next, b, taberu);
	DP3[a][b][taberu] += func(a - 1, b, taberu);
	return DP3[a][b][taberu];
}

int main() {
//先ほどと同じなので省略
}

この時点でO(N^3)で、MLEです。

メモリ節約

DPのメモリを節約する一般的なテク、DP配列の使いまわしをします。(ここも知識)

DPが二つに分かれているので分かりにくいですが、再帰の起点であるfuncから処理を追っていくと、
taberu==tのときの更新の際、直接呼び出しているのは(つまり、漸化式に入っているのは)

  • a,bがより低くtaberu==tのfunc又はfunc2
  • taberu==t-1のfunc又はfunc2

のみであることが分かります。
よって、taberuを0~Nまで増やしていく方向にforDPをすると、taberuを節約できることが分かります。
この方針で再帰をforDPに書き直すとMLEを解決出来て、ACできます。

実際に書いたコード:Submission #1705841 - CODE FESTIVAL 2017 qual C
解説用に書き直したコード:Submission #1707527 - CODE FESTIVAL 2017 qual C

解いた経緯


(注:9時から19時まで模試でした)

旧AtCoderからbetaAtCoderに移るスクリプト(未完)

AtCoderからbetaAtCoderに移るtampermonkey用スクリプトです。
上の方に変なのが見えるようになります。
使えればよし精神を大事にしていこうな(逃げ)
僕にはこれが限界なので、もっと良いのを誰か作って。

追記>Luzhiledさんが作ってくれた。ありがとうございます。
Luzhiled's page


↓僕の (Luzhiledさんのを使うのがおススメですが、一応残しておきます)

// ==UserScript==
// @name         old atcoder to new atcoder
// @namespace    https://twitter.com/eiya5498513
// @version      1.0
// @description  ja
// @author       eiya
// @match        http://*.contest.atcoder.jp/*
// @match        https://*.contest.atcoder.jp/*
// @grant        none
// ==/UserScript==

(function() {
  'use strict';
  const url = location.href.replace(/\/&/, "");
  const contest_name = url.replace(/^https?:\/\//,'').split('.')[0];
  const end_name = url.replace(/^https?:\/\/.+\.contest\.atcoder\.jp\/?/,'');
  const beta_url = "https://beta.atcoder.jp/contests/"+contest_name + "\/" + end_name;
  const style = /font-family:Helvetica Neue, Helvetica, Arial,sans-serif;font-size:200%;/;
  const beta_html_text = "<div style=\"" + style + "\"><a href=\""+ beta_url + "\">beta版</a></div>";

  $('div.container').append(beta_html_text);
})();

動作図
f:id:eiya5498513:20171019231501j:plain