けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 130 D - Enough Array (400 点)

超典型的なしゃくとり法そのものだった!!!

問題へのリンク

問題概要

 N 個の整数  A_1, A_2, \dots, A_N があたえられる。数列の連続した区間であって、その総和が  K 以上となっているものを数え上げよ。

制約

  •  1 \le N \le 10^{5}

考えたこと

しゃくとり法については以前に記事を書いた。

qiita.com

このしゃくとり記事の 2 番目の例題は


連続した区間であって、その総和が  K 以上であるもののうち、区間の長さの最小値を求めよ


という問題であった。今回の問題はこれとほとんど同じ問題である。すなわち「区間の長さの最小値」の代わりに「区間の個数」を求める問題である。

そもそもしゃくとり法を用いることで


区間の左端 left を固定したとき、区間 [left, right) の総和が  K 以上となるような最小の right


が求められるのである。

  • 「条件を満たす区間の長さの最小値」だったら、この right - left が答えの候補で、これを全 left について調べれば良い。

  • 「条件を満たす区間の個数」だったら各左端 left に対して、右端が right, right + 1, ..., N (N - right + 1 個) が条件を満たすので、これを各 left について総和をとればよい。

#include <iostream>
#include <vector>
using namespace std;

int N;
long long K;
vector<long long> a;
 
int main() {
    cin >> N >> K;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
 
    long long res = 0;
        
    /* 区間の左端 left で場合分け */
    int right = 0;
    long long sum = 0;
    for (int left = 0; left < N; ++left) {
        /* [left, right) の総和が K 以上となる最小の right を求める */
        while (right < N && sum < K) {
            sum += a[right];
            ++right;
        }
        if (sum < K) break; // これ以上 left を進めてもダメ

        // 集計
        res += (long long)(N - right + 1);

        if (right == left) ++right;
        else sum -= a[left];
    }
 
    cout << res << endl;
}

AtCoder ABC 130 C - Rectangle Cutting (300 点)

長方形を直線で真っ二つに割る方法について

  • 直線が長方形の対角線の交点を通る
  • 直線が長方形を二等分する

というのは同値だという話。結構、中学受験の算数では定番の話だったりする。

問題へのリンク

問題概要

二次元平面上で  (0, 0), (W, 0), (0, H), (W, H) を頂点とした長方形と、その内部または周上の点  (x, y) があたえられる。

 (x, y) を通る直線で長方形を真っ二つに分割する方法のうち、切り取られた二つの断片のうちの面積の小さい方の面積の最大値を求めよ。

また、その最大を達成するような直線が複数通りありうるかどうかを判定せよ。

制約

  •  1 \le W, H \le 10^{9}

考えたこと

答えは、長方形の面積の半分!!!!!!!!

具体的には、

  •  (x, y)
  •  (\frac{W}{2}, \frac{H}{2})

を通る直線を考えればよい。ここで  x = \frac{W}{2}, y = \frac{H}{2} だったら直線が複数通りありえて、そうでなければ一意である。

なお、 x == \frac{W}{2} といった関係式の判定は誤差をなくすために  2x == W と判定した方が無難。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    long long W, H, x, y;
    cin >> W >> H >> x >> y;
    double res = (double)(W) * H / 2;
    cout << fixed << setprecision(10) << res << " ";

    if (x*2 == W && y * 2 == H) cout << 1 << endl;
    else cout << 0 << endl;
}

diverta 2019_2 F - Diverta City (900 点)

冷静になれば自然な構成ではあるね...企業コンのラス問だと身構えてしまうのがよくない

問題へのリンク

問題概要

 N 頂点からなる重みつき無向単純完全グラフであって、 N! 通り考えられるハミルトンパスに対して始点と終点が同じものを同一視して得られる  \frac{N!}{2} 通りのパスの重みがすべて異なるものを一つ求めよ。

ただし、出来上がるグラフのすべてのハミルトンパスの重みが  10^{11} 以下でなければならない。

制約

  •  2 \le N \le 10

考えたこと

こういう「〜の重みがすべて異なるようなものを構築せよ」という問題の基本方針は大抵は二進数なんだけどとても  10^{11} ではとても無理だね。

というわけなので、帰納法的な構築を考察してみることにする。 N 頂点のグラフ (上記の重みの最大値が  M) に対して新たな一点を加えるとき、

  •  c_1, c_2, \dots, c_N

をそれぞれ

  •  c_i ( i = 1, 2, \dots, N)
  •  c_i + c_j ( i, j)

がすべて異なるように作れたならば、その新たな点から  N 頂点への重みをそれぞれ

  •  (M+1)c_1, (M+1)c_2, \dots, (M+1)c_N

とすることで目的のグラフを作ることができる。具体的には

  •  c = {1, 2, 4, 7, 12, 20, 29, 38, 52, 73}

とかで行ける。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long w[10] = {1, 2, 4, 7, 12, 20, 29, 38, 52, 73};

long long dp[(1<<10)+1][11];
long long calc(vector<vector<long long> > &G, int N) {
    memset(dp, 0, sizeof(dp));
    for (int bit = 0; bit < (1<<N); ++bit) {
        for (int v = 0; v < N; ++v) {
            if (!(bit & (1<<v))) continue;
            for (int nv = 0; nv < N; ++nv) {
                if (bit & (1<<nv)) continue;
                int nbit = bit | (1<<nv);
                chmax(dp[nbit][nv], dp[bit][v] + G[v][nv]);
            }
        }
    }
    long long res = 0;
    for (int v = 0; v < N; ++v) chmax(res, dp[(1<<N)-1][v]);
    return res;
}

int main() {
    int N; cin >> N;
    vector<vector<long long> > G(N, vector<long long>(N, 0));

    G[0][1] = 1; G[1][0] = 1;
    for (int n = 2; n < N; ++n) {
        long long M = calc(G, n);
        for (int v = 0; v < n; ++v) G[v][n] = G[n][v] = (M+1) * w[v];
    }
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) cout << G[i][j] << " ";
        cout << endl;
    }
}

diverta 2019_2 E - Balanced Piles (800 点)

最初は絶望感がヤバイタイプの問題。とても解ける問題には見えない。でも落ち着くと解ける。
こういう問題を作れるのはすごい。

問題へのリンク

問題概要

 N 個のマスに積み木を重ねていく。最初はどのマスも 0 段である。以下の操作を繰り返して、最終的にすべてのマスが  H 段となるようにしたい。

  • 全マスのうち、積み木の段数が最も小さいマスを選ぶ。それが複数あるときは 1 つ選ぶ
  • 全マスの積み木の段数の最大値を  M としたとき、選んだマスの積み木の段数を、 M 以上  M + D にする

操作列として考えられるものが何通りあるか、1000000007 で割ったあまりを求めよ。

制約

  •  1 \le N, H, D \le 10^{6}

考えたこと

一目見たときの絶望感がやばい。DP を立てたいと思っても、一見ありうる状態が  (H+1)^{N} 通りある。対称性とかでちょっと削ってもそう簡単には減らない。

なので考えるべきことは

  • 実は考えるべき状態空間はもっとずっと小さいのではないか
  • そもそも根本的にもっとわかりやすい特徴づけを与えて、それを数えればよいのではないか

といったことだと思う。そんなときに着目したくなるのが

  • 積み木の段数の最大値とか最小値とか
  • それらが何個ずつあるかとか

そういった値だけ持っておけば状態をまとめられるのではないかということ。で、頑張ればそれが上手く行って解けるという筋書きに。

解法 1: 僕の解法 (わかりやすいものに特徴付ける)

僕のやり方は結局出来上がる DP は editorial と同じなのだが、ちょっと違う考察を経た気がするのでメモ。

ほとんどの人は「各ステップの積み木の最大段数」に着目していたが、僕は「最小段数」に着目した。そして最小段数のなす数列が

  • 最初に  0 N
  • それ以降は、「隣り合う2要素の差が  D 以下」「広義単調増加」「同じ値は  N 個以下」という条件を満たす数列
  • 最終項は  H で、 H は 1 個だけ

という風になっていることはすぐにわかる。例えば  N = 3, H = 2, D = 1 のとき、

(0, 0, 0) -> (0, 0, 1) -> (1, 0, 1) -> (1, 2, 1) -> (1, 2, 2) -> (2, 2, 2)

に対応する数列は

0, 0, 0, 1, 1, 2

となる。ここでこの数列に対応する操作が何通りあるかというと実は

  • 数列中に登場する各整数値について、その個数の積をとったもの

になることが言える。まず数列の  i 項目に対応する操作では、最下段を一つ選んで  i+N 項目の値にする必要があって、そうすれば対応する操作が作れることが言える。例えば上の数列の 3 番目の 0 では、6 番目が 2 であることから、0 を 2 に引き上げる必要があって、実際上の例でも (1, 0, 1) -> (1, 2, 1) としている。

なぜなら、その時点で最下段だったやつというのは  N ターン後に再び最下段になるからだ。厳密にはタイがあるのでややこしいが、うまいこと順序を決めたりしてあげるとちゃんと示せる。

また、数列中に値 v が  m 個あるとき「初めて v が最下位になったときには  m 個の v がある」ということを意味していて、それらをどの順序で引き上げていくかには任意性があるので  m! 通りの係数がかかることになる。よって、数列に対応する操作の個数は「数列中に登場する各整数値について、その個数の積をとったもの」になることが示された。

DP へ

ここまでわかれば DP するのみ。

  • dp[ v ] := 数列で値 v までを完遂した段階での対応する操作の個数

とすると、v の手前が u = v-D, v-D+1, ..., v-1 の D 通りを場合分けして

  • dp[ v ] += dp[ u ] × (1! + 2! + ... + N!)

となることがわかる。ここで

  • 1! + 2! + ... + N! の値は予め計算しておける
  • この漸化式は累積和で高速化できる

ということから全体で  O(H) で解くことができる。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) v += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        return is >> x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

// 二項係数ライブラリ
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;
BiCoef<mint> bc;

const int MAX = 2100000;

int N, H, D;
mint dp[MAX], sdp[MAX];

mint solve() {
    bc.init(MAX);
    mint fac = 0;
    for (int i = 1; i <= N; ++i) fac += bc.fact(i);
    memset(dp, 0, sizeof(dp));
    memset(sdp, 0, sizeof(sdp));
    dp[0] = bc.fact(N);
    sdp[1] = bc.fact(N);
    for (int v = 1; v <= H; ++v) {
        int left = max(0, v - D);
        int right = v;
        dp[v] = (sdp[right] - sdp[left]) * fac;
        sdp[v+1] = sdp[v] + dp[v];
    }

    mint res = 0;
    for (int v = max(0, H - D); v <= H-1; ++v) {
        res += dp[v];
    }
    return res;
}

int main() {
    cin >> N >> H >> D;
    cout << solve() << endl;
}

解法 2: DP の状態量を削る考え方

最大要素に着目して解いてみる。まず操作を以下の読み替える。積み木は常にソートされた状態にしておく。そして

  • 積み木の最も左にあるやつの高さが最大になるようにして、後ろの方に配置する
    • 最大のやつと同点になるなら、最大のやつの個数が  a 個あるとしたら、 a + 1 通りの挿入箇所がある
    • 最大のやつより大きくなるなら、最後尾に配置する

という操作と思うことにする。このとき初期状態の並べ方が  N! 通りあることに予め注意しておく。ルールとして重要なのは「最も左にあるやつの高さを最大になるようにする」という部分。これを決めておくことで考えやすくなる。

以上の考察をもとに

  • dp[ v ][ a ] := 最大高さが v で v が a 個ある状態にするまでの操作の個数

とすると

  • dp[ v ][ 1 ] += dp[ v - k ][ b ] (k = 1, 2, ..., D, b = 1, 2, ..., N)
  • dp[ v ][ k ] += dp[ v ][ k - 1 ] × k

という風になることがわかる。このままだと  O(NH) だが式をよく見ると、

  • dp[ v ][ 1 ], dp[ v ][ 2 ], ... の比率は、v の値によらず一定っぽい

ということがわかるので、これをまとめあげることができる。最終的に

  • dp[ v ] := dp[ v ][ 1 ]

とすると、

  • dp[ v ] += (1! + 2! + ... + N!) × dp[ v - k ] (k = 1, 2, ..., D)

という風になる。あとは解法 1 と一緒。

diverta 2019_2 D - Squirrel Merchant (600 点)

操作が複雑な順序性をもつ問題だけど、こういうのは「操作の流れを単純化して、こういうものだけ考えればよい」という考察を狙うのが常だとは思う。

問題へのリンク

問題概要

問題画像そのままを

f:id:drken1215:20190616014523p:plain

解法 1: 自分のやつ

僕が最初に考えたことは、例えば

「最初に A でドングリのいくつかを金 (銀、銅も) にかえた上で、最後に A で金 (銀、銅も) をドングリに変える」というのは意味がない

ということ。よって、金・銀・銅それぞれについて

  • A でドングリを金属に変えて (2 ターン目)、B でドングリに戻す (3 ターン目)
  • B でドングリを金属に変えて (3 ターン目)、A でドングリに戻す (4 ターン目)

のどちらかになることが言える。さらにこのどちらの方がいいかも特定できる。すなわちドングリに戻すときの換算レートが高い方を採用する。

さらにさらに、3 ターン目については、

  • ある金属たちについてドングリに戻す
  • 他の金属たちについて金属に換算する

の両方が行われる可能性があるが、ドングリに戻す方を先に行って損はない。以上から、この問題は「前半」と「後半」に真っ二つにきれいにわかれて、それぞれ


金属が 0〜3 種類あって、例えば 3 種類の場合では、それぞれ金・銀・銅を  x, y, z グラムずつ得るとすると

max: ax + by + cz
s.t. px + qy + rz <= N

みたいな最適化を解く (1 種類、2 種類の場合は変数の数が 1, 2 になる、また a < p, b < q, c < r である)


という問題に帰着される。editorial ではナップサック DP でやっている。僕は  x, y を固定する全探索でやった (でもナップサック DP でやった方がいいと思う...)

 x, y を固定したとき、c < r が保証されているので「残りを目一杯換算した方がいい」という Greedy で OK。よって全体として  O(N^{2}) くらいでできる。

怖いのは後半パートにおける  N は 5000 倍くらいまで大きくなる可能性があるのだが、その場合は後半は高々 2 変数以下なので大丈夫。

#include <iostream>
#include <vector>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long N;
long long a[3], b[3];

long long calc(vector<long long> sei, vector<long long> obj, long long M) {
    if (sei.size() == 0) return M;
    if (sei.size() == 1) {
        long long rem = M;
        long long p = rem / sei[0];
        long long r = rem % sei[0];
        return p * obj[0] + r;
    }
    if (sei.size() == 2) {
        long long res = M;
        for (long long x = 0; x * sei[0] <= M; ++x) {
            long long rem = M - x * sei[0];
            long long p = rem / sei[1];
            long long r = rem % sei[1];
            chmax(res, x * obj[0] + p * obj[1] + r);
        }
        return res;
    }
    if (sei.size() == 3) {
        long long res = M;
        for (long long x = 0; x * sei[0] <= M; ++x) {
            for (long long y = 0; x * sei[0] + y * sei[1] <= M; ++y) {
                long long rem = M - x * sei[0] - y * sei[1];
                long long p = rem / sei[2];
                long long r = rem % sei[2];
                chmax(res, x * obj[0] + y * obj[1] + p * obj[2] + r);
            }
        }
        return res;
    }
    return M;
}

long long solve() {
    // zenhan
    {
        vector<long long> sei, obj;
        for (int i = 0; i < 3; ++i) {
            if (a[i] < b[i]) {
                sei.push_back(a[i]);
                obj.push_back(b[i]);
            }
        }
        N = calc(sei, obj, N);
    }

    // kouhan
    {
        vector<long long> sei, obj;
        for (int i = 0; i < 3; ++i) {
            if (a[i] > b[i]) {
                sei.push_back(b[i]);
                obj.push_back(a[i]);
            }
        }
        N = calc(sei, obj, N);
    }
    return N;
}

int main() {
    while (cin >> N) {
        for (int i = 0; i < 3; ++i) cin >> a[i];
        for (int i = 0; i < 3; ++i) cin >> b[i];
        cout << solve() << endl;
    }
}

解法 2: ナップサック DP

解法 1 では、金銀銅それぞれに応じて前半と後半どちらでドングリにするかを割り振ったけど、本当はそれをする必要はなくて、単に


金属が 0〜3 種類あって、それぞれ金・銀・銅を  x, y, z グラムずつ得るとすると

max: ax + by + cz
s.t. px + qy + rz <= N

みたいな最適化を解く


というのを係数を入れ替えて二回解くだけでも OK。この場合、 c \gt r という保証はない。そしてこれは個数制限なしナップサック問題として解くことができる。

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long N;
vector<long long> a(3), b(3);

const int MAX = 30000000;
long long dp[MAX];

long long calc(vector<long long> sei, vector<long long> obj, long long M) {
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < sei.size(); ++i) {
        for (int v = 0; v + sei[i] <= M; ++v) {
            chmax(dp[v+sei[i]], dp[v] + obj[i]);
        }
    }
    long long res = M;
    for (int v = 0; v <= M; ++v) chmax(res, dp[v] + M-v);
    return res;
}

long long solve() {
    N = calc(a, b, N);
    N = calc(b, a, N);
    return N;
}

int main() {
    cin >> N;
    for (int i = 0; i < 3; ++i) cin >> a[i];
    for (int i = 0; i < 3; ++i) cin >> b[i];
    cout << solve() << endl;
}