以下の内容はhttps://eiya5498513.hatenablog.jp/より取得しました。

ICPC 2021 国内予選参加記

 

KyopRo-jinで出場していました。5完20位、学内3位なので、今年は通過出来ていそうです。良かった。

 

まずCを見る。
30分くらい考えたが回転操作の扱いが何も分からない。根が動かなければ木DP（というかDFS）で終わりなんだが...
気が付くとAが通っているのでACが出ているDを見てもらうことにする。B書き終わったので提出してくれと言われる。残り二人とも大きいデータを入力できる環境が無いらしい。ちょっと手こずりながらもBもAC。ここまで25分くらい。

気合を入れなおす。回転操作の後に入れ替え操作をする手順は、入れ替え操作を先にやったことにしても良いので、入れ替え操作=>回転操作の順だけ考えれば良いと考える。
この結論自体は役に立たないけど、入れ替え操作を先にやったことにしても良いので任意の頂点を根にできることに気が付く。

これは全方位木DPなので頑張って再帰関数を書きまくると通る。ここまでで75分くらい。

https://atcoder.jp/contests/chokudai_S001/submissions/27049817 （履歴から復元したので微妙に不完全かもしれない）

 


この段階でBも通っていてDを二人がかりで考察しているが、嘘貪欲でWAを出しただけで進展が無いらしい。問題の説明を受けるも僕も分からない。Dは他のチームが解けている問題なので焦る。

分からないって言ったらEは実装が面倒だけど解けてそうなので書いてと言われる。残り二人には引き続きDを見てもらう。
Eはタクシーを使う数で場合分けすると良いらしい。なるほど。
サンプルにタクシー沢山使わないといけないケースが無いの悪意がないか？って言いながら書き終わる。提出しようと思ったら出力にINFが残っていることに提出前に気が付く。ここまで120分くらい。

このあたりでDが通って、順位表も見て3人でデバッグ。
タクシー使用回数が0でゴールに行けるはずなのに使用回数50回以内で到達できないことになっていて、使用回数50回以内でのダイクストラの部分を見るがバグっているように見えない。
サンプルを抽出しようとしたものの、入力テキストが大きいので苦戦。デバッグ出力を入れたとき、ついでにワーニングを思考停止で潰したらその直す操作で未定義動作踏んでしまい悪戦苦闘。

なんとかサンプルを抽出すると、「タクシー使用回数が0でゴールに行けるはず」の方が間違っていることが判明。

直して提出したらWA。
タクシー沢山使わないといけないケースの方の計算で、(1<<taxi)のつもりでpow(1,taxi)を書いていた(提出の434行目)。サンプル強くしてくれ～～
直してAC。ここまで160分。

本番ではすんなり解いたつもりだったけど、振り返ると時間かけすぎかもしれない。関係ない未定義動作踏むくだりとpowのWAのくだりは完全に要らなかった。
https://atcoder.jp/contests/chokudai_S001/submissions/27039170


この段階で5完20位、学内3位でギリギリ通過圏。ABDのペナが他と比べて大きくEも時間かかっているので、学内4位がもう一問解いてきたらペナ差でギリギリ負け、学内4位になって落ちそうという話をしていた。
残りはもう解けないだろうと祈祷フェーズのつもりでFを考えていたら、意外と考察が進んでしまった。解ききれはしなかっただろうけどちょっと悔しい。

 

 

 

 

 

 

 

 

手続き型プログラミング基礎レポート

巡回セールスマン問題 TSP C89 C

大学の授業で書いたレポートです。
5000頂点程度の三角不等式が成り立つ巡回セールスマン問題を、C89で3sec制限で解くコードを含んでいます(15～60ページ)
引用する際は、 eiya@大学垢 (@eiya5497313) | Twitter に連絡していただければ本名を教えます。

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

CTF 競プロ解説 writeup

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°さんに自分のコードの状況を説明したところ、注目していた行の下に原因が書いてあるのに気が付く。 「関数の引数が一致しません」 これやんけ！ｗとなって交代して修正。

実行したら初期化ミスとかしてたのでそこは直したがまだ無限ループっぽい挙動。 模擬予選ならここで冷えるものの今回はデバッガがあるので一時停止からのステップ実行で洗うと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 競プロ一般

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

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 - 建物 を解いたという日記

atcoder 競プロ一般

問題：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)から出ることにするか！ｗ

・通ったら暫定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;
}


以上の内容はhttps://eiya5498513.hatenablog.jp/より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14