ferinの競プロ帳

競プロについてのメモ

エクサウィザーズ 2019 C - Snuke the Wizard

問題ページ

考えたこと

  • i番目にいた人が消える条件は何か?で考えるけどまともな形にならない
  • 方針転換して二分探索をすることにする
  • 消える人数を固定したところで何も嬉しくない
  • i番目が左に消えるときi-1番目も左に消えることに気がつく
  • 単調性があるので二分探索ができる
  • 判定にO(Q)かけていいのでこれは解けた

自分の二分探索のlb,ubの境界の決め方
条件が真であるときにlb=midなのかub=midなのか考える
前者なら[lb,ub)、後者なら(lb,ub]として扱う
初期値を区間に入ってる方は有効な値のぎりぎり、入ってない方は有効な値の外側になるようにする
解候補の範囲の外でも判定がちゃんと動くなら入ってない方を適当な値にしても動くので思考がサボれる
答えは前者ならlb,後者ならub

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vector<char> t(q), d(q);
    REP(i, q) cin >> t[i] >> d[i];

    ll a, b;
    {
        auto check = [&](ll mid) {
            ll idx = mid;
            REP(i, q) {
                if(s[idx] == t[i]) {
                    if(d[i]=='L') idx--;
                    else idx++;
                    if(idx < 0) return true;
                }
            }
            return false;
        };

        ll lb=-1, ub=n;
        while(ub-lb > 1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) lb = mid;
            else ub = mid;
        }
        a = lb;
    }

    {
        auto check = [&](ll mid) {
            ll idx = mid;
            REP(i, q) {
                if(s[idx] == t[i]) {
                    if(d[i]=='L') idx--;
                    else idx++;
                    if(idx >= n) return true;
                }
            }
            return false;
        };

        ll lb=-1, ub=n;
        while(ub-lb > 1) {
            ll mid = (lb+ub)/2;
            if(check(mid)) ub = mid;
            else lb = mid;
        }
        b = ub;
    }

    if(b <= a) {
        cout << 0 << endl;
    } else {
        cout << b-a-1 << endl;
    }

    return 0;
}

Codeforces Round #548 (Div. 2) D. Steps to One

問題ページ

考えたこと

  • gcd=gと決め打つと長さの期待値が割と簡単に求まる気がする
  • 長さnの確率は (gの倍数の確率)^(n-1) * (gの倍数以外の確率) っぽい
  • g=2,3 の両方で 6, 6, 6, 6,…, 1みたいなのを重複して数えてる
  • 約数系包除で数えられそう
  • 期待値をちゃんと求める
  • m以下のgの倍数の個数をcntとする
  • 期待値 = sum_{n=1}^{無限} n * (cnt/m)^(n-1) * (1-cnt/m)
  • 公比掛けて引くやつでこのsumは求まる
  • 整理すると期待値 = m/(m-cnt)
  • gの倍数の分を余計に数えてるので dp[g] -= dp[gの倍数] とする
  • 調和級数でO(mlogm)なので間に合いそう
  • sample3が1ずれてる
  • 実装が間違ってるのかと思って手計算するけど手計算もサンプルとずれてる
  • 何が間違ってるのかよくわからない
    -----コンテスト終わり-----
  • 期待値計算でn=1のときの確率が1-cnt/mとなっているが正しくは1/m
  • ここの値をちゃんと直すと通った

この立式のn=1がコーナーになってるの全く気づけませんが… 立式パートでやたら式変形に時間を溶かしたのだめ

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

struct mint {
  ll x;
  mint(): x(0) { }
  mint(ll y) : x(y>=0 ? y%MOD : y%MOD+MOD) {}
  ll get() const { return x; }
  // e乗
  mint pow(ll e) {
    ll a = 1, p = x;
    while(e > 0) {
      if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
      else {a = (a*p) % MOD; e--;}
    }
    return mint(a);
  }
  // Comparators
  bool operator <(mint b) { return x < b.x; }
  bool operator >(mint b) { return x > b.x; }
  bool operator<=(mint b) { return x <= b.x; }
  bool operator>=(mint b) { return x >= b.x; }
  bool operator!=(mint b) { return x != b.x; }
  bool operator==(mint b) { return x == b.x; }
  // increment, decrement
  mint operator++() { x++; return *this; }
  mint operator++(signed) { mint t = *this; x++; return t; }
  mint operator--() { x--; return *this; }
  mint operator--(signed) { mint t = *this; x--; return t; }
  // Basic Operations
  mint &operator+=(mint that) {
    x += that.x;
    if(x >= MOD) x -= MOD;
    return *this;
  }
  mint &operator-=(mint that) {
    x -= that.x;
    if(x < 0) x += MOD;
    return *this;
  }
  mint &operator*=(mint that) {
    x = (ll)x * that.x % MOD;
    return *this;
  }
  mint &operator/=(mint that) {
    x = (ll)x * that.pow(MOD-2).x % MOD;
    return *this;
  }
  mint &operator%=(mint that) {
    x = (ll)x % that.x;
    return *this;
  }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator%(mint that) const { return mint(*this) %= that; }
};
// Input/Output
ostream &operator<<(ostream& os, mint a) { return os << a.x; }
istream &operator>>(istream& is, mint &a) { return is >> a.x; }

ll binpow(ll x, ll e) {
  ll ret = 1, p = x;
  while(e > 0) {
    if(e&1) {(ret *= p) %= MOD; e--;}
    else {(p *= p) %= MOD; e /= 2;} 
  }
  return ret;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll m;
    cin >> m;

    if(m == 1) {
        cout << 1 << endl;
        return 0;
    }

    vector<mint> dp(m+1);
    for(ll i=m; i>=2; --i) {
        ll cnt = m / i;
        dp[i] = mint(m) / (m-cnt);
        dp[i] -= mint(m - cnt) / m;
        for(ll j=2*i; j<=m; j+=i) {
            dp[i] -= dp[j];
        }
    }

    mint ret = mint(1) / m;
    FOR(i, 2, m+1) ret += dp[i];
    cout << ret << endl;

    return 0;
}

FII Code Round #1 Sugarel in Love

問題ページ

解法

dp[i][j] = (頂点i以下の部分木で使用したパスにおいて頂点iの次数がjのときの最大値) としてdpする。(頂点vの部分木において)頂点vを端点とする辺を使用しない場合、子の部分木はどのような選び方をしていたとしても問題ないため遷移は dp[v][0] = sum(max(dp[child[v]][j])) となる。

頂点vの子の頂点aとの辺を利用したとすると頂点aの分の距離はdp[a][1]+(辺v-aの重み)で頂点a以外の他の子bの分はsum(max(dp[b][j]))となる。頂点vに隣接した辺を使わない場合から辺v-aを使った場合に変化させたとき、dpの値の変化はdp[a][1] + (辺v-aの重み) - max(dp[a][i])となる。この変化する値が大きい上位2つを保持することでつなげるべき辺を求めることができdpの更新を行うことができる。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 998244353;

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<vector<PII>> g(n);
    REP(i, n-1) {
        ll x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }

    vector<vector<ll>> dp(n, vector<ll>(3));
    function<void(ll,ll)> dfs = [&](ll v, ll p) {
        ll ma1 = 0, ma2 = 0, su = 0;
        for(auto to: g[v]) {
            if(to.first == p) continue;
            dfs(to.first, v);
            ll mx = max({dp[to.first][0], dp[to.first][1], dp[to.first][2]});
            su += mx;
            if(ma1 < dp[to.first][1] + to.second - mx) {
                ma2 = ma1;
                ma1 = dp[to.first][1] + to.second - mx;
            } else if(ma2 < dp[to.first][1] + to.second - mx) {
                ma2 = dp[to.first][1] + to.second - mx;
            }
        }
        dp[v][0] = su;
        dp[v][1] = ma1 + su;
        dp[v][2] = ma1 + ma2 + su;
    };
    dfs(0, -1);

    cout << max({dp[0][0], dp[0][1], dp[0][2]}) << endl;

    return 0;
}

Educational Codeforces Round 60 D. Magic Gems

問題ページ

解法

dp[i]=(i個分スペースを埋める方法が何通りあるか)としたDPを考える。i個スペースを埋めるためにはmagic gemを一つ置くパターンとmagic gemを分割しnormal gemをM個置くパターンがある。したがってこのDPの遷移は

  • dp[i] = dp[i-m] + dp[i-1] (i >= m)
  • dp[i] = 1 (i < m)

となる。N<=10^18なので普通にDPをすることはできないがこの漸化式は行列累乗を用いることN項目をO(M^3logN)で求めることができ解けた。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a) {
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

using vec = vector<ll>;
using mat = vector<vec>;

// A*Bを計算
mat mul(mat &A, mat &B) {
    mat C(A.size(), vec(B[0].size()));
    for(int i=0; i<(int)A.size(); ++i) {
        for(int k=0; k<(int)B.size(); ++k) {
            for(int j=0; j<(int)B[0].size(); ++j) {
                C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD;
            }
        }
    }
    return C;
}

// A*Bを計算
vec mul(mat &A, vec &B) {
    vec C(A.size());
    for(int i=0; i<(int)A.size(); ++i) {
        for(int j=0; j<(int)B.size(); ++j) {
            C[i] = (C[i] + A[i][j]*B[j]) % MOD;
        }
    }
    return C;
}

// A^nを計算 m*m行列のn乗はO(m^3logn)
mat pow(mat A, ll n) {
    mat B(A.size(), vec(A.size()));
    for(int i=0; i<(int)A.size(); ++i) B[i][i] = 1;
    while(n > 0) {
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

signed main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, m;
    cin >> n >> m;

    if(n == m) {
        cout << 2 << endl;
        return 0;
    }

    if(n < m) {
        cout << 1 << endl;
        return 0;
    }

    mat a(m, vec(m));
    a[0][0] = 1, a[0][m-1] = 1;
    REP(i, m-1) a[i+1][i] = 1;

    vec b(m, 1);
    b[0] = 2;

    a = pow(a, n-m);
    cout << mul(a, b)[0] << endl;

    return 0;
}

Educational Codeforces Round 60 C. Magic Ship

問題ページ

解法

i日目に到達可能な場所がどのようになっているのか考える。(x1,y1)=(0,0)、s="UDRL"のときの例を以下に示す。 f:id:ferin_tech:20190219230025j:plain 風が吹く方向と逆方向に移動すればi日目で到達したマスはi+1日目以降でも到達可能なことがわかる。したがってi日目にはi以下の地点に移動することができる。1日経過するごとにひし形の中心が風の吹く方向に移動しひし形の大きさが1大きくなることがわかる。
i日目で到達したマスがi+1日目以降でも到達できることからゴールのマスにある日数で到達できるか?という判定問題には単調性が存在する。したがって二分探索を行うことができる。n日を1周としてX周したときに到達できるか?の判定はX周でひし形の中心が移動する位置とゴールのマンハッタン距離がn*X以下か?でO(1)で判定できる。何周でゴールに到達できるかを求めその周の何日目にゴールできるかを求めればよい。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a) {
    out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

signed main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll sx, sy, gx, gy, n;
    string s;
    cin >> sx >> sy >> gx >> gy >> n >> s;
    gx -= sx; gy -= sy;

    ll turnx = 0, turny = 0;
    vector<ll> cx(n), cy(n);
    REP(i, n) {
        if(s[i] == 'U') cy[i] = 1, turny++;
        else if(s[i] == 'D') cy[i] = -1, turny--;
        else if(s[i] == 'R') cx[i] = 1, turnx++;
        else if(s[i] == 'L') cx[i] = -1, turnx--;
    }

    auto check = [&](ll mid) {
        ll x = turnx * mid, y = turny * mid, sz = n * mid;
        return abs(gx-x) + abs(gy-y) <= sz;
    };

    if(!check(1LL<<40)) {
        cout << -1 << endl;
        return 0;
    }

    ll lb = 0, ub = 1LL<<40;
    while(ub - lb > 1) {
        ll mid = (lb+ub)/2;
        if(check(mid)) ub = mid;
        else lb = mid;
    }

    ub--;
    ll x = ub * turnx, y = ub * turny, sz = ub * n;
    REP(i, n) {
        x += cx[i], y += cy[i], sz++;
        if(abs(gx-x) + abs(gy-y) <= sz) {
            cout << sz << endl;
            return 0;
        }
    }

    cout << -1 << endl;

    return 0;
}

ARC062 E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題ページ

解法

立方体の上の面と底面を決めると残りの側面に来る面の色配置は一意に定まる。色の配置がvのタイルが何枚あるか?という情報を計算しておけば何通りあるかは求めることができる。C(N,2)通りを全通り試すことで答えが求まる。
ただし、回転等をしっかり考慮してダブらないように数え上げるのが大変。まずタイルを回転することで得られる4通りの色配置に対して辞書順で最小となる並べ方を基準とすることでダブって数えないようにする。各タイルに対して回転で同じ色配置になるようなことがあるかどうかで場合分けしておく。これによって回転で同じ色配置ができるパターンが何通りあるか求められる。

  • 回転して同じ色配置が出てくることがない
  • 180度回転で同じ配置になる(点対称)
  • 90度回転で同じ配置になる(全て同じ色)

上の面のタイルをi番目、底面をj番目に固定する。立方体の上下反転で同じになるものを数えないためi<jと条件をつける。上の面は辞書順最小のもの一つに固定し底面は回転4通りを試す。側面に必要なパネル4枚を列挙し、各色配置に対して何通りの置き方が存在しているのかを求め掛けていく。

N<-400で3乗通るしタイル3枚固定する半分全列挙?とか考えてたけど2枚固定でよかった
細かいところ詰めるのが大変、こういう実装をちゃんとできるようにしていきたい…

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

// 回転の4通りのうち辞書順で最小のものを返す だぶって数えるのを防ぐ
vector<int> getmin(vector<int> v) {
    vector<int> ret(v);
    REP(i, 3) {
        rotate(v.begin(), v.begin()+1, v.end());
        chmin(ret, v);
    }
    return ret;
}

// n0枚、n1枚、n2枚でpanel枚を埋める方法が何通り?
ll dfs(ll panel, ll n0, ll n1, ll n2) {
    if(panel == 0) return 1;
    ll ret = 0;
    if(n0) ret += n0*dfs(panel-1, n0-1, n1, n2);
    if(n1) ret += 2*n1*dfs(panel-1, n0, n1-1, n2);
    if(n2) ret += 4*n2*dfs(panel-1, n0, n1, n2-1);
    return ret;
}

signed main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    // 0→回転して同じになるものはない
    // 1→180度回転で同じになる(対角が同じ)
    // 2→90度回転でも同じ(全部同じ)
    vector<ll> r(n);
    map<vector<int>, int> cnt[3];
    vector<vector<int>> a(n, vector<int>(4));
    REP(i, n) {
        REP(j, 4) cin >> a[i][j];
        a[i] = getmin(a[i]);
        if(a[i][0] == a[i][2] && a[i][1] == a[i][3]) {
            r[i] = 1;
            if(a[i][0] == a[i][1]) r[i] = 2;
        }
        cnt[r[i]][a[i]]++;
    }

    ll ret = 0;
    // 上をi番目のパネルに
    REP(i, n) {
        // i番目のパネルの分を消す これが側面に来るとだぶるので再度足すことはしない
        cnt[r[i]][a[i]]--;
        // 底をj番目のパネルに
        FOR(j, i+1, n) {
            // j番目のパネルの分を消す こっちはループの最後で再度足す
            cnt[r[j]][a[j]]--;
            // 底面を4通りに回転させる
            REP(k, 4) {
                // 側面に必要なパネル4枚を列挙
                map<vector<int>, int> mp;
                mp[getmin({a[i][1], a[i][0], a[j][1], a[j][0]})]++;
                mp[getmin({a[i][2], a[i][1], a[j][0], a[j][3]})]++;
                mp[getmin({a[i][3], a[i][2], a[j][3], a[j][2]})]++;
                mp[getmin({a[i][0], a[i][3], a[j][2], a[j][1]})]++;
                // 側面に置く方法が何通りあるか
                ll t = 1;
                for(auto p: mp) {
                    t *= dfs(p.second, cnt[0][p.first], cnt[1][p.first], cnt[2][p.first]);
                    if(t == 0) break;
                }
                ret += t;
                // 底のパネルを回転
                rotate(a[j].begin(), a[j].begin()+1, a[j].end());
            }
            cnt[r[j]][a[j]]++;
        }
    }
    cout << ret << endl;

    return 0;
}

ARC084 E - Finite Encyclopedia of Integer Sequences

問題ページ

解法

まずKが偶数ならば(K/2, K, …, K)となる数列が答えになることがわかる。よってKが奇数のものについてのみ考える。
ナイーブな解法として答えの数列でi番目で数列のa番目をつくるにはi番目の数字が一意に定まるとして前から決めていくような解法がある。しかしk,nに大きな値がきたときにaの値がまともに持てるような大きさの値ではなくなってしまう。したがって何か別の小さい値を利用して答えを求める必要がある。X/2番目の数列に近そうな数列として ceil(K/2) を並べるものがある。この数列と答えとなる数列が何個ずれているか?というずれであればあまり大きい値ではなさそう。このずれがどの程度の大きさなのか実験してみる。

f:id:ferin_tech:20190216230952p:plain
k=3での実験
実験結果を見ると答えの数列はceil(K/2)を並べた数列とn/2ずれていることがわかる。数列を辞書順で一つ前のものに戻す操作はならしO(1)で可能なので全体でO(N)で解ける。

実験難しい…
ならしO(1)で戻す処理の雰囲気にAGC029 C - Lexicographic constraintsを感じた

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

// 実験
//int n = 5, k = 3;
//vector<vector<ll>> a;
//
//void dfs(vector<ll> v) {
//  if(v.size()) a.push_back(v);
//  if(v.size() == n) return;
//
//  REP(i, k) {
//    vector<ll> u(v);
//    u.push_back(i+1);
//    dfs(u);
//  }
//}

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  // 実験
//  dfs({});
//  sort(ALL(a));
//  ll half = ceil((int)a.size(), 2);
//  cout << "half=" << half << endl;
//  for(int i=max(half-10, 0LL); i<min(half+10, (ll)a.size()); ++i) {
//    cout << i+1 << " " << a[i] << endl;
//  }
//
//  return 0;

  ll n, k;
  cin >> k >> n;

  if(k%2 == 0) {
    cout << k/2;
    REP(i, n-1) cout << " " << k;
    cout << endl;
    return 0;
  }

  vector<ll> ans(n, ceil(k, 2LL));
  REP(i, n/2) {
    if(ans.back() == 1) ans.pop_back();
    else {
      ans[ans.size()-1]--;
      while(ans.size() != n) ans.push_back(k);
    }
  }

  REP(i, ans.size()) cout << ans[i] << " ";
  cout << endl;

  return 0;
}