ABC132 F Small Products

令和ABC初期の問題。黄diffだったけど自力できたのでうれしいね。

問題概要

正の整数 個を一列に並べたものであって、隣接して並んでいるどの つの整数の積も 以下であるものの個数を で割った余りを求めてください。

考察

例えば数列のある数が1であったとき、隣接する項の積が以下になるのは、隣接する項が以下の時です。

もし数列のある数が2であれば、隣接する項の積が以下になるのは、隣接する項が以下の時です。

もし数列のある数が3であれば、隣接する項の積が以下になるのは、隣接する項が以下の時です。

みたいな風に考えると、各項についてとりあえずまで見ればまあ解けます。ただし間に合いません。

で、間に合わないのでくらいにならないかな～と考えると、本当にそうなることがわかります。

軽くお気持ち証明をします。示したいことは「隣接する項の積を以下にするために見るべき数はたかだかである」ことです。

とします。は「ある数をとすると、隣の数は以下でなければならない」という意味です。

するとこうなります。やなどが抜けていると思うかもしれません。

例えばですが、右側がになるのは既にで出ているので考えなくて良いです。

上に示したものは、左側の値を変化させていったときに、右側の値が変化する境界です。

これらの値の変化は明らかに単調であるので、これらの境界のみ考えればよく(= 境界の間は必ず全て同じ値になる)、状態を大きく削減することが出来ます。

ここまではすぐできました。ただここから遷移を合わせるパートで大変に手こずりましたね......。

以前から遷移ガチャをせずに、きちんと数式などで考えて機械的に遷移を導いていくことを意識して目指しているんですが、結局よくわからなくなってガチャガチャやってサンプル試して出すをしてしまいました。大反省。

これがキーエンスコンでの大失敗の原因になったので、本当に改善しないといけません。こういうのを速めに詰め切るのってどうしたら良いんでしょうか。

少々手探り感はありますが、まずナイーブな実装をしてみることにします。

最初配るDPで考えていたんですが、区間和更新が必要になって嫌になりました(これでめっちゃ時間を溶かした)。

こういう時のテクとして、配るDPで区間和更新になるやつは、貰うDPにすると区間和取得で対応できることが多いです。
区間に辺が張られたグラフのDPなどで、普通のセグ木を使って処理する典型があったりしますね。

というわけで貰うDPを考えると、以下のような式になります。

この遷移は累積和で処理できるので、前処理さえしていれば十分高速に動作します。

これでナイーブな実装は出来ました。

ここからであることを利用した解法にするのはまあまあ簡単で、遷移式はほぼ変わりません。

ただ先述の通りであることを利用した解法は、境界のみに着目して境界の間にある数をすっ飛ばすことで高速化するものなので、境界の間にある数を補完してあげる必要があります。

よって境界の間にある数をとすると、

と導けます。

以上を実装することでこの問題を解くことが出来ます。

僕の実際のコードは以下です。実質貰うDPの考え方をしているのに、迷走していたので配るDPのままになっています。遷移ガチャで当たりを引けないとこういうちぐはぐなことになりがち......。何で解けたんだ？

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

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; }

template< int mod >
struct ModInt {
    int x;

    ModInt() : x(0) {}

    ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}

    ModInt &operator+=(const ModInt &p) {
        if((x += p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator-=(const ModInt &p) {
        if((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }

    ModInt &operator*=(const ModInt &p) {
        x = (int) (1LL * x * p.x % mod);
        return *this;
    }

    ModInt &operator/=(const ModInt &p) {
        *this *= p.inverse();
        return *this;
    }

    ModInt operator-() const { return ModInt(-x); }

    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }

    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }

    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }

    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }

    bool operator==(const ModInt &p) const { return x == p.x; }

    bool operator!=(const ModInt &p) const { return x != p.x; }

    ModInt inverse() const {
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) {
        t = a / b;
        swap(a -= t * b, b);
        swap(u -= t * v, v);
        }
        return ModInt(u);
    }

    ModInt pow(int64_t n) const {
        ModInt ret(1), mul(x);
        while(n > 0) {
        if(n & 1) ret *= mul;
        mul *= mul;
        n >>= 1;
        }
        return ret;
    }

    friend ostream &operator<<(ostream &os, const ModInt &p) {
        return os << p.x;
    }

    friend istream &operator>>(istream &is, ModInt &a) {
        int64_t t;
        is >> t;
        a = ModInt< mod >(t);
        return (is);
    }

    static int get_mod() { return mod; }
};

using modint = ModInt<MOD>;

int main(int argc, char const *argv[]) {
    ll n,k; cin>>n>>k;
    vector<ll> A;

    // 境界を全列挙する
    for (ll i = 1; i*i <= n; ++i) {
        A.push_back(i);
        if (i!=n/i) A.push_back(n/i);
    }

    int m = A.size();
    sort(A.begin(), A.end());
    vector<modint> a(m);
    rep(i,m) a[i] = A[i];

    // DP初期化
    vector<vector<modint>> dp(k+1, vector<modint>(m+1, 0));
    rep(j,m) {
        if (j == 0) dp[0][j] = 1;
        if (j != 0) dp[0][j] = a[j]-a[j-1];
    }
    modint N = n;

    rep(i,k-1) {
        vector<modint> cost(m+1);
        rep(j,m) cost[j+1] += dp[i][j]+cost[j];
        rep(j,m) {
            modint tmp = 1;
            if (j != 0) tmp = a[j]-a[j-1];
            dp[i+1][j] += cost[m-j]*tmp;
        }
    }

    modint ans = 0;
    for (int j = m-1; j >= 0; --j) {
        ans += dp[k-1][j];
    }

    cout << ans << '\n';
    return 0;
}

ABC193 E Oversleeping

問題文読んでウっとなりかけたけど、単に超丁寧に書いてくれてただけでしたね。ありがとう。

バチャ参加したときは寝不足で頭が回らずとても解ける状況ではなかったので、改めて解き直します。

TwitterでCRTを使うという本質情報を得ていたので自力出来ました。CRTで解けるって聞いてなかったら解けなかったかな...どうだろう。

問題概要

問題文が長くてさすがに面倒なので、リンクだけ貼っておきます。

atcoder.jp

考察

見てとりあえず何か周期をごにょごにょする問題っぽいことがわかります。

とりあえず条件を式で綺麗に表せないと始まらなさそうなので、式をよーく見ます。

かつ

となるを求めます。

とりあえず、 のときを考えてみます。この数式は「B駅に着いた時間にちょうど高橋君が目を覚ました」ということを意味するので、この数式を満たす解が存在するとき、その解が示す時間に高橋君は電車から降りることが出来ます。

そして、は定数です。試しにと置いてみます。

すると

は

と表すことが出来ます。これは4の倍数+1と10の倍数+5が等しいという等式なので、「4で割って1あまり、10で割って5あまる一番小さな数ってなーんだ？」という問題に言い換えられます。

要は

と表すことが出来て、これは拡張ユークリッドの互除法なりで解けることで有名です。

問題は与えられた数式が不等式になっていることですが、よく見るとと制約が小さくなっており、2乗を回しても十分間に合うので、普通に全部の区間を試せば良いです。

地味にサンプルの三つめがめっちゃ優しいですね(最大値がではギリギリ足りないことを教えてくれている)。ありがとうAtCoder。今まで不親切が続いていたのにどうしたんでしょう？今後もこうあってくれると泣いて喜びます。

Educational Codeforces Round 104 E Cheap Dinner

日本語解説無かったから書きます。俺自身が日本語解説になることだ。

地獄みたいな実装で泣きそうになった。一昔前のこどふぉって感じ。こんなんやって楽しいか？

問題設定

コース料理を食べます。

メニューには個の最初の料理、個の二番目の料理、個のドリンク、個のデザートの値段がそれぞれ書かれています。

食べ合わせの相性があって、最初の料理と二番目の料理について、一緒に食べてはいけない組み合わせが個あります。
同様に、二番目の料理とドリンクについて一緒に食べてはいけない組み合わせが個、ドリンクとデザートについて一緒に食べてはいけない組み合わせが個あります。

食べられる組み合わせで、最も安いコースはいくらになるでしょうか。

考察

うーん、補グラフでダイクストラ！w としたいところですが、流石に辺の数がヤバいことになるのでできません。

とりあえずこういう順番が本質でない問題はソートしても困らないので、各メニューの金額をソートしてから考えることにしましょう。

和の最小化は、一番小さい数同士を足したときが明らかに最小なので、ソートした後に食べられる組み合わせの中で一番左のものを選んであげればいいことがわかります。

具体的な手順を示してイメージを補強します。まず、一番目の料理は小さい順に左からソートされているものとして、二番目の料理を見ていきます。

各二番目の料理を一つずつ見ていき、それとの食べ合わせが良い一番目の料理の中で最も左にあるものを選べば、「二番目の各料理まで食べる時の最小コスト」がわかります。

「二番目の各料理まで食べる時の最小コスト」がわかったので、その数列をソートして、同じように各ドリンクについて一つずつ見ていきます。

そうすると「各ドリンクまで食べる時の最小コスト」がわかるので、更にその数列をソートし、各デザートについて一つずつ見れば、「各デザートまで食べる時の最小コスト」を求めることが出来ます。その最小値が答えです。

計算量を考えてみましょう。一番時間がかかりそうなのは「各料理に対して食べ合わせの良いものの中で、最も左にある料理を選ぶ」操作ですが、実はsetなどを利用すれば普通に間に合います。

証明してみます。個の食べ合わせの悪いペアが存在し、ペアの数はです。

i番目の料理が持つ食べ合わせの悪いものの数 とします。

全ての料理について見る際には 回の計算が発生することになります。をしているのは、であっても各料理を一つずつ見ていくという行為は必ず行われるためです。

そして は、

と

に分解できます

ここでsetを使用するため となり

また明らかに です。

よってとなります。

ということで計算が間に合うことはわかりました。

あとは実装を頑張るんですが、この実装が嫌すぎて禿げました。ソートするから添え字の対応を上手くしてやらないと壊れてしまうんですが、まあ上手くできなかったですね。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i].first;
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}


ll x_min_element(const set<int> &x, const vector<P> &val) {
    ll ret = LINF;
    rep(i,x.size()+1) {
        if (!x.count(i)) {
            if (i != val.size()) ret = val[i].first;
            break;
        }
    }
    return ret;
}

void calc_dp(const vector<set<int>> &x, const vector<P> &val, const vector<ll> &b, vector<P> &dp) {
    int n = x.size();
    rep(i,n) {
        ll tmp = x_min_element(x[i], val);
        tmp += b[i];
        chmin(dp[i].first, tmp);
        dp[i].second = i;
    }
    return;
}

int main(int argc, char const *argv[]) {
    input_init();

    int n1,n2,n3,n4; cin>>n1>>n2>>n3>>n4;
    vector<P> a(n1), b(n2), c(n3), d(n4);
    rep(i,n1) cin>>a[i].first, a[i].second = i;
    rep(i,n2) cin>>b[i].first, b[i].second = i;
    rep(i,n3) cin>>c[i].first, c[i].second = i;
    rep(i,n4) cin>>d[i].first, d[i].second = i;

    // 一番目の料理をソート
    sort(a.begin(), a.end());

    vector<int> idx_a(n1), idx_b(n2), idx_c(n3), idx_d(n4);

    // 添え字を対応付ける
    rep(i,n1) idx_a[a[i].second] = i;

    int m1,m2,m3; cin>>m1;
    vector<set<int>> x(n2), y(n3), z(n4);
    rep(i,m1) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_a_index = idx_a[p];
        int cur_b_index = q;
        x[cur_b_index].insert(cur_a_index);
    }

    vector<P> dp0(a);
    vector<P> dp1(n2, {LINF, LINF});
    vector<ll> B, C, D;
    for (auto &&e: b) B.push_back(e.first);
    for (auto &&e: c) C.push_back(e.first);
    for (auto &&e: d) D.push_back(e.first);

    calc_dp(x, dp0, B, dp1);
    
    // 二番目の料理までわかったのでソートする
    sort(dp1.begin(), dp1.end());

    // 添え字を対応付ける
    rep(i,n2) idx_b[dp1[i].second] = i;

    cin>>m2;
    rep(i,m2) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_b_index = idx_b[p];
        int cur_c_index = q;
        y[cur_c_index].insert(cur_b_index);
    }

    vector<P> dp2(n3, {LINF, LINF});
    calc_dp(y, dp1, C, dp2);

    // ドリンクまでわかったのでソートする
    sort(dp2.begin(), dp2.end());

    // 添え字を対応付ける
    rep(i,n3) idx_c[dp2[i].second] = i;

    cin>>m3;
    rep(i,m3) {
        int p,q; cin>>p>>q; --p,--q;
        // pは元のindexなので、ソート後のindexに変換する
        int cur_c_index = idx_c[p];
        int cur_d_index = q;
        z[cur_d_index].insert(cur_c_index);
    }

    vector<P> dp3(n4, {LINF,LINF});

    // デザートまでわかった
    calc_dp(z, dp2, D, dp3);

    ll ans = min_element(dp3.begin(), dp3.end())->first;
    if (ans != LINF) cout << ans << '\n';
    else cout << -1 << '\n';

    return 0;
}

ABC192 反省と感想

Dがいまいちピンと来ず(そもそも題意を完璧に把握しないまま進めたのがまずかった)、Eを解きに行ったのは結果的に良かったですね。

Dの誤読云々については思うところはあれど、そもそも二分探索が出るまでかなりかかったので、誤読しないような問題構成になっていた場合僕のレートは恐らく下がっていたと思います。
まあ、実質的な敗北と言っても差し支えないでしょう。そのことを胸にこれからも頑張ります。

A問題 Star

int ans = 100-(x%100);

B問題 uNrEaDaBlE sTrInG

// 小文字判定
if ('a' <= s[i] && s[i] <= ''z) {

}
// 大文字判定
if ('A' <= s[i] && s[i] <= 'Z') {

}

これ確か仕様的には結構怪しくて、非推奨であるようなことを読んだ覚えがあります。しかしAtCoderで動くのはわかっていたので書きました。C/C++で競プロするならまあ許される程度の小技ですかね。

C問題 Kaprekar Number

ll g1(ll n) {
    vector<int> x;
    while (n > 0) {
        int tmp = n%10;
        x.push_back(tmp);
        n /= 10;
    }
    sort(x.begin(), x.end(), greater<>());
    string s;
    rep(i,x.size()) s.push_back('0'+x[i]);
    ll ret = stoi(s);
    return ret;
}

ll g2(ll n) {
    vector<int> x;
    while (n > 0) {
        int tmp = n%10;
        x.push_back(tmp);
        n /= 10;
    }
    sort(x.begin(), x.end());
    string s;
    rep(i,x.size()) s.push_back('0'+x[i]);
    ll ret = stoll(s);
    return ret;
}

ll f(ll n) {
    if (n == 0) return 0;
    return g1(n)-g2(n);
}

int main(int argc, char const *argv[]) {
    ll n,k; cin>>n>>k;
    ll ans = n;
    rep(i,k) {
        ll cur = f(ans);
        ans = cur;
    }
    cout << ans << '\n';
    return 0;
}

関数を定義してしまうのが楽だと思います。

D問題 Base n

反省点が二点あります。

1. 二分探索であることがわかるまで30分以上かけている
2. 求めるものをきちんと理解していなかった

1の方がヤバいです。誤読云々で他の参加者が失敗していなければ、自分だけが失敗するところでした。

問題を見て、よくわからないながら、とりあえず各進数表現について決め打ってMを超えるかどうか判定する処理を書きました。この処理自体は、1桁目から見ていくことでオーバーフローを回避する工夫を盛り込むなど、及第点だったと思います。

最初は問題の意味がそもそもわからなかった(10進数まで見るだけかと思っていた)ので、とりあえず10進数まで見ればいいのかな～みたいなコードを書き、サンプルに12進数なんかが出てきていたので100進数くらいまで見ればいいかと思うなどしていました。

ここ本当に頭が悪いし、「探索する範囲はそんなに広くないだろう」という意識を持ってしまい、二分探索を思考に乗せるのに時間がかかってしまいました。本当に反省しています。まず問題をしっかりと読んで、最大進数まで見ることが分かっていれば、さっと二分探索が出せただろうに....。大反省です。

結局二分探索に気づいたのはEを通して10分くらい更に考え込んだ後でした。愚かですね。

2についても「題意をしっかりと最初に把握していない」ことが招いた失敗でした。反省します。WAの件数的に、ずっとオーバーフローを疑っていました...。

E問題 Train

見た瞬間「大体やるだけかな～」と思いながらとりあえず半信半疑でダイクストラを書き、サンプルが通るもWA。更新時の式をよく見るとバカなミスをしていたので投げ直すと通りました。

本質はA問題と同じなので、A問題が解ける人でダイクストラ法を知っている人なら通せるんじゃないでしょうか。でもこれが緑diffはおかしいと思うの。

F問題 Potion

流石にD問題よりもずっと通されていなかったのでFは捨てたのですが、この判断はどうだったんでしょうね...。どうせK固定して頑張るタイプの問題でしょという見た目で方針は立ちやすかったので、特攻してもよかったかもしれません。Dを通せなかった結果論ですが。
後からやった感想だと、自力でわりとすんなり通せたので、うーんという気持ち。まあ全体の計算量が4乗でdpを使うという大ヒントを得ていたのでそんなもんかな。

まずぱっと見ですが、時刻を、合成したポーションの値をとして表すと、

関係式は上記のように表すことができ、となります。求めたいのはこれが最小のですから、ポーションの組み合わせを全探索すれば答えを出すことができます。

しかし問題はここからです。当然全ての組み合わせを試すのは時間がかかりすぎるので、高速化したいです。最初に思いつくのは部分和問題的なDPですが、の制約が大きすぎます。ここからもう一つ進展させたいです。

こういうときはとりあえず先ほどの関係式を吟味します。

ということは、はの倍数です。よってと表せて、これは脳死で移項してにできます。

ということは？先ほどの部分和問題的なDPという解法を却下したのは、の制約が大きすぎるためでした。しかしという関係式が導き出せたので、を固定してとが一致するもののみを考えれば良いということがわかったのです。

の範囲は最大でもなので、十分DP出来る制約になりました。

番目の数まで見て、そこまでの和をで割ったあまりがで、それまでに個の数を足している、を超えない範囲で最大の和

と定義します。

memset(dp,-1,sizeof(dp));
dp[0][0][0] = 0;
rep(i,n) {
    rep(j,k) {
        rep(l,k+1) {
            if (dp[i][j][l] == -1) continue;
            ll tmp = dp[i][j][l]+a[i];
            // 今見ている数を加える場合は和がxを超えないかどうかチェック
            if (tmp <= x) chmax(dp[i+1][(j+a[i])%k][l+1], tmp);
            // 今見ている数を加えない場合は何もせず遷移
            chmax(dp[i+1][j][l], dp[i][j][l]);
        }
    }
}

遷移は上のような感じで。

あとはこれををからまで全部回してを求めてやればいいです。dbの初期化は回しましょう！それで答えが合わずに首をかしげていました。

青diffかって言われるとうーん？って感じ。D問題がアレじゃなかったらFも結構通されるような問題に見えます。

Educational Codeforces Round 104 反省とか

1900位とか。もっと速く解けたよね？1000位くらいに入るべきだったなあとめちゃくちゃ反省。

A問題 Arena

最近のこどふぉでは一番良心がある問題。

int mini = *min_element(a.begin(), a.end());
int cnt = 0;
rep(i,n) if (mini == a[i]) cnt++;
cout << n-cnt << '\n';

B問題 Cat Cycle

これに1ペナ30分かかってるの大反省だな？
うーん。綺麗に図は書けて、

1. が偶数の時はそのままを出す
2. が奇数の時は進むごとに1スキップする

ということが分かったにもかかわらず、時間がかかりすぎてしまった。

が奇数の時は進むごとに1スキップするんだと思ってしまったんだよなあ。式変形にしろ図を書くにしろ、考えやすい方策に落とし込めても、正確な情報を読み取れなければ意味がないんですよね。

図から数式に落とし込みたい時、僕の場合いきなり数式を書くのは混乱するので、どういう性質を持つのかを自然言語で表現しながら数式を考えると良いのかもしれない。今度やってみる。

C問題 Minimum Ties

これに2ペナ30分かかってるの反省してもし足りない。寝ぼけてたが言い訳にならないレベル。

Excelで表を書くと奇数の時は引き分けなしで良くて、偶数の時は良い感じに各チーム一回ずつ引き分けをいれるといいことがわかる。

雰囲気で実装したらWAが出た。よく見ると書いてた表とは違うものを出力していてたまげる。

今度こそ表と同じものを実装して提出すると、WA。首をかしげて表をよく見ると、引き分けの入れ方がカスで、全チームの勝ち点が全く等しくなっていないことがわかる。

ちゃんと表を作り直すとAC。これ30分くらい無駄にしてるの意味不明だし、B問題とあわせて50分無駄にしているのを考えると卒倒モノだなあ。

D問題 Pythagorean Triples

C考えるのが面倒だったのでDに行ったけど、これ速かったのえらかったな。

かつとなる以下のを求めよというやつ。

因数分解とか出来るわけないから初手でwolfram alphaに投げると、 となることがわかるので、勝ちです。

特にbがなので、より小さい物しか見なくていい。

よってそのまま実装すれば良いです。

数式ベースで考えようという最近徹底していた意識が活きたぜ。wolfram alpha最高！w
数式ベースで考えることを徹底しようにも、式変形が脳のメモリを圧迫して辛い気持ちになっていたんですが、とりあえずwolfram alphaに投げてもいいかもわからんね。

E問題 Cheap Dinner

普通にわかんなかったな。通れない辺だけが定義されていて、ノードに重みがついているグラフが与えられるので、計算資源が無限にあれば補グラフにダイクストラ流して解けます。

単体の別記事で解法書きます。ググったけど日本語解説がなかった。

Codeforces Round #701 (Div. 2) C. Floor and Mod

限りなく本質に近づいていたのに、そこから40分あっても解けなかった。めっちゃ悔しい。こういうやつを淡々と機械的に詰め切れるようになりたい。

それはそれとしてB問題みたいなこどふぉありがちパズルゲームめっちゃ嫌い。最近気づいたけど、数学ゲーよりパズルゲーの方が時間かかってる気がします。

問題設定

かつのとき、 となるの組の個数を求めよ

解法(自力で行けるところまで)

見た目からしてあからさまに式変形してくださいと言っている問題なので、やる。

とおく。

から、として、

(ただし ) となる。

よって、はの倍数かつ、その係数をとおくと、ということになる。

ここまではまあ来れて、bを一つずつ決め打って全探索してしまえば答えが出ることがわかる。

綺麗に定式化するとこんな感じ。

しかし制約はなので、ナイーブなやり方ではだめ。

ここまで来て解けないのなんだかなあ。

式をよく見ると、となるようなまでは、答えは全部の連番なので、そこまでの計算を省略できる。
めんどくせーとか言いながらにぶたんを書いた。

これでminを考えなくても良くなって、となるようなをとおくと、

の値を後は求めればいい。ここまではコンテスト時間内に来ました。

解説見た

解説見た。そもそもbを固定するのは筋が悪いっぽい。

より、の最大値はとなる。
したがってとなるので、から、である。

要はをまで決め打って求めればいい。

あとは決め打ったときの求め方ですが、頑張って式変形しましょう。

まずの範囲を求めます。

なので、となります。最大値で最小値がなので、の個数はです。

次にの範囲ですが、はとの式で表せます。

からとなるのでの最大値はとなります。

また なのでと置けてとなります。

最大値がで最小値がなので、から求められるの個数はです。

あとはこの小さい方を取れば良く、となるので、解けます。

ABC172 Unfair Nim

これも以前写経して通したけどわからなかったやつ。今度こそ理解するぞ。

問題概要

Nimをする。一つ目の山から二つ目の山に0個以上の石を移し替えることで、後手必勝にできるか判定せよ。
また、必勝にできる場合は移し替える最小の石の個数を求めよ

という問題。

解法

Nimの説明は省略します。Nimで後手必勝 = 全部の石の数のXORが0 という有名事実があるので、「一つ目の山から二つ目の山に0個以上の石を移し替えることで、全ての数のXORを0にできるか判定せよ」という問題になります。

以下、各山の石の数をと置きます。一つ目の山は, 二つ目の山はです。

と以外の値は不変なので、三番目の山からN番目の山までの排他的論理和も不変であることは明らかです。この不変な排他的論理和をと置きます。

すると全ての数のXORを0にするには、とのXORがにする必要があります。

よって、となるような最小のを求める問題に言い換えることが出来ます。

まあここまではNimさえ知っていればすんなり来れますね。問題はここからです。

をナイーブに全探索して試していけば当然解くことが出来ますが、制約がなので、まあ2sec以内に解くことは不可能です。

仕方がないので別の方法を考えます。まず、XORなので2進法に変換して桁ごとに見ていくのが典型です。正直こんなの貪欲か桁DPのどっちかしかないんだよねのお気持ちになります。

僕の実力では貪欲の正当性を自力で示すことは難しいので、まずは桁DPを考えます。そのうち貪欲を理解したらそれも書くかも。

色々試行錯誤した結果、繰り上がりが発生して面倒なことがわかるので、下の桁から値を決めていく方針で行きます。

として、, とします。
すると求めたい値は

という条件を満たす最大のとなります。

の下からi桁目までとの下からi桁目までが一致するようなの最大値

と定義します。最初をそのまま決めようと思ったら繰り下がりなんかも出てきて嫌になったのでやめました。

自力だとここから先に行けずに躓いてしまったのですが、原因は以下です。

1. との二つについて決めていく考え方を持てなかった
2. 下から決めていくとき、未満フラグ(以下フラグ？)をどう管理して遷移していけばいいのかわからなかった

2はほぼ知識で何とか出来るところですし、2さえ分かっていればの試行錯誤もスムーズにいくはずなので、覚えちゃいたいですね。

というわけですぬけさんの解説動画を見ました。

とをそれぞれ桁目まで決めていて、繰り上がりの有無、以下か否かをそれぞれとのフラグで持ったときのの最大値

を考えます。

まず桁目のとの値は]の四つ考えられるので、四通り全部試します。

そのうえで、その桁まで見たときのとの排他的論理和がと等しいか、和がと等しいかをチェックして、両者とも等しいときのみ遷移します。

これはややこしく思えますが、排他的論理和は各桁ごとに完全に独立、和も繰り上がりしているかどうかさえ事前に分かっていれば各桁ごとに独立です。
だから繰り上がりの有無を状態として持っている必要があるんですね。

さて、そこまでの値が以下か否かを持つフラグの遷移は少し考える必要があります。

各桁ごとに見たときに、その桁の値がのそれよりも「大きいか/小さいか/同じか」の三通りで場合分けを考えます。

大きい時

それまでがどんな状態だろうが、「以下ではない」フラグの方に遷移します

小さい時

それまでがどんな状態だろうが、「以下」フラグの方に遷移します

同じとき

それまでの状態と同じフラグの方に遷移します

これで遷移が全部わかったので、実装するとACとなります。ちなみにbit演算でバグり散らかしました。今度から (X >> i) & 1ll って書きます.......。

うーん、見るべき条件が多いので、それらをしっかりと満たしながら遷移できるDPを考えるのに参ってしまいました。要訓練ですね。

maspyさんバージョンのDP

maspyさんの解法を見たらすごくて笑っちゃった。桁DPは総じて添え字地獄になりがちとか思ってたんですが、これなら実装が簡単ですね。

maspypy.com

詳細は↑です。

DPできる問題は再帰的な構造をしているという事実が頭から抜けていました。こんなにシンプルに考えられるの、魔法みたいですね。

何というか、僕は頭が弱いから、DPを難しく考えてしまうのだなと思いました。