こんにちは、はーさかです。

初めて AtCoder の解説記事書きます。

突然解説記事を書き始めた理由()

こないだ ABC の公式解説が行間多くて難解がちであることにお気持ち表明してたら chokudai さんからリプ飛んできてアワアワしてました。
曰く、今のABCの開催頻度を維持するため公式解説にはそこまで突っ込まないで(てか色んな人が後発で解説記事書いてくれるからその辺参照して><)って感じでした。────反論の余地、無し。
頭冷やした結果、無料コンテンツなのにクレーム入れてごめんなさいという気持ち一色になりました。AtCoder 最高！chokudai さん、いつもありがとうございます。

ということで、解説が不満なら自分で解説すればいいじゃないということでこれから暇があればちまちまやってこうかなと思います。よろしくお願いします。

問題

F - Sugoroku

・ $[0,\ N$ ] の $(N + 1)$ マス上で双六をする。¹
・ $0$ から出発し $N$ を目指す。
・サイコロの目は $[1,\ M$ ]。出た目のマスだけ移動する。
・踏めないマスがある。
・移動回数を最小化しつつ、移動マス数を並べると辞書順最小となる移動方法を出力せよ。
・移動不可能のとき $-1$ を出力せよ。

解法

まず、入力例2のように $1$ が $M$ コ以上連続する区間が存在するとき移動不可能です。
以下移動可能な場合を考えます。
辞書順最小化を行うことから、後ろの方で大きな賽の目を出した方が良さそうなので盤面を reverse します。
各ターン、できるだけ多く移動した方が以後の移動距離を小さくできるので移動回数を減らせて損しないことが分かります。これで移動回数最小化が実現できています。

すなわち、盤面を反転してから今いるマス目を $cur$ としたときに出すべき賽の目 $dice$ はmin( $M,\ (N - cur)$ ) から $1$ まで降順にチェックして初めて $S(cur + dice)==0$ となるところと定めます。

実はこの方針を0, 1それぞれの連続数のメモも二分探索もせず愚直に実装するだけでACが取れてしまいます。²

実装

#include "bits/stdc++.h"
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;

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

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

    ll n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    reverse(ALL(s));

    // mem : '1'の最大連続数
    ll mem = 0, b = 0;
    vll a(n + 1);
    REP(i, n + 1) {
        a[i] = int(s[i] - '0');
        if (a[i] == 1) b++;
        else {
            chmax(mem, b);
            b = 0;
        }
    }

    // 到達不可能
    if (mem >= m) {
        cout << -1 << endl;
        return 0;
    }

    // res : 各ターンで出すべき目
    // cur : 現在地
    vll res;
    ll cur = 0;

    while (cur != n) {
        // dice : このターン出すべき目
        ll dice = min(m, n - cur);
        while (a[cur + dice] != 0) dice--;
        cur += dice;
        res.push_back(dice);
    }
    reverse(ALL(res));
    for (auto x : res) {
        cout << x << " ";
    }
    return 0;
}

計算量

公式解説や強い人のブログでは区間min を考えるみたいないかにも600点という内容が書かれていますが³、この問題はこのように350点程度の実装で解けてしまいます。
上述の解法が最小手数、辞書順最小の要件を満たすことは問題ないと思うので、 $O(N)$ であることの証明を行います。

出目を決定するパートの計算量について考えます。
最悪1マスしか進めなかった場合、その決定に $M - 1$ 回 $dice$ を更新しているので一見トータル $O(NM)$ かと思いきやそんなことはありません。
実際、毎回1マス進めるなら踏めないマスが存在しないのでほぼ毎回 $M$ マス進めるハズです(最後だけ調整が入るけど)。
極端な例を考えましたが、より強い主張として以下が成立します。

最適ムーブにおいて、連続する2回の賽の目の和は $M$ より大きい。

$t$ ターン目と $t + 1$ ターン目における出目を $d_t,\ d_{t+1}$ と置きます。
いま $d_t+d_{t+1}\leq M$ と仮定すると、 $t$ ターン目で $d_t+d_{t+1}$ の目を出すことで移動回数を真に少なくできます。よって仮定のムーブは最適ではありません。

以上より2ターンあれば必ず $M$ マス以上進むので、問題個所トータルの最悪計算量は $\frac{N}{\frac{M}{2}} \times M$ で抑えられ $O(N)$ であることが示されました。めでたし。

おわりに

いや、これで600が解けて良いのか？という気持ちが強いのでどこか hackable なんじゃないかという疑念を込めて解説記事を投稿しました(は？)。間違ってるところ等あればバシバシ指摘してください、お願いします。「合ってそう」という御意見もお待ちしております。

ほぼほぼ初めて Markdown 記法で書いてるんですけど tex: みたいなの使ってちまちま書いてたら大カッコが衝突してるせいかうまく表示されなくて発狂寸前。↩
Markdown、文字色指定にhtml埋める必要があって発狂かと思いきやはてブロの標準機能にショートカットがあったおかげで耐えました。↩
公式解説の後半では降順走査とあるので近い考えを利用してそうですが、どのみち最小手数をメモ化しているので本解法より複雑そうです(まだイマイチ読みこめていません)(あとで別解でも解きなおします)。↩

倒錯思索ステイルメイト

愚問愚答観察。

AtCoder ABC148 F - Sugoroku

問題

解法

実装

計算量

おわりに