2017-12-20

競技プログラミング初めて１年経ちました

その他

競技プログラミング（競プロ）を初めて１年くらい経ったので、１つの区切りとして競プロについて得られた知見や感想を書いておきます。
強くなる方法とか競プロお役立ちテクニックとかそういう話は一切書いてません。

パソコンのプロじゃなくても出来る

何かいきなり馬鹿みたいな話ですが、競プロはパソコンのプロじゃなくても簡単に参加できます。
競技プログラミングやってる人っていうと、日常的にLinuxとか使っててコマンドプロンプトとかめっちゃ使いこなしているスーパーハッカーみたいなイメージでしたが、私みたいにWindowsしか使えない、マウスが無いとまともに操作できない、プログラミングは大学で習った程度のことしかできずアプリとかも作れない……みたいな人でも何とかできます。サンプルコピペするときにカチッペタッカチッペタッてやるのは何かアホっぽいですがそれでもコンテストに参加していくつかの問題を解くことができます。

pythonで競プロ続けていくのはなかなか厳しい

最初半年ぐらいはpythonでやってたんですが、それからはだいたいD言語でやるようになってしまいました。ひねくれ者だったので「pythonで競プロは厳しい」みたいな風潮を見てもいけるとこまでいってやろうとか思ってましたが……散々言われてたことですが、「やっぱりpythonは遅い」です。経験的に、pythonって反復処理が10^6超えるとTLEするかも？って感じなんですよね。10^7だったら絶対TLEします(pypyで出せるならもうちょっとマシになりますが10^7になると相当不安です)。でも競プロの問題って想定解が10^7とか普通にあって、何なら10^8ってこともありました。Atcoderの簡単な問題やyukicoderでやる分にはpypyで提出したりすることで割といけるのですが、こどふぉとかJOIの過去問とかはどうしてもpythonじゃきついなあっていう場面が結構ありました。あと再帰深さの制限を上げても再帰深さのせいで（？）REしたりしたこともありました。いろいろあって辛くなるのでpythonで競プロをやるのは止めました。

こどふぉに参加すると生活リズムが狂う

日本で流行ってる競プロサイトといえば、一番はAtcoder、二番はCodeforces、三番Topcoderって感じっぽいです。私が初めて「競技プログラミング」という存在を知ったころはTopcoderというサイトしか知らなかったので今もそんな感じでTopcoderが一番栄えてるんだろうな～と思っていたんですが、どうやらそうではないらしいです。

それは置いといてCodeforces、通称こどふぉですがこれはロシアの競プロサイトです。「なんでロシア？」と思いますが、ロシアは競プロが一番強い国らしいです。ここのコンテストにも結構日本人が参加しています。問題文はロシア語ではなく、英語なので何とか読めます。コンテストの質（？）は正直あまりよろしくないというのが競プロ界隈での定評です。サイトが重い・つながらない、ジャッジキューが詰まりすぎ、問題の質も悪い（こどふぉはストーリー付きの問題文であるのでそれが邪魔みたいなのとか、考察が軽く実装が重いみたいな問題は嫌われる傾向にあるからかもしれません。あと想定解が誤解法だったとか）などなど。デメリットは多いですが、それでも世界規模で見ると一番栄えている競プロサイトです。こどふぉはSNS的な側面もあって、コンテストが終わるとフォーラムが賑わうので見ていると面白いです。そういう意味ではAtcoderよりお祭り感があって楽しいです。あとはAtcoderにない特徴的なシステムとして、他人のコードを撃墜できるHackというシステムがあってそれも面白いかもしれません。

そんなわけでこどふぉのコンテストに参加するのはなかなか刺激的で楽しいんですが、大きな欠点としてだいたい日本時間で深夜に行われるというのがあります。通常24:00~26:00くらいでそっからシステムテストが終わるのを待ったり、寝ようと思ってもコンテスト後は目が冴えてしまっているのでうだうだやっていると27時とか28時くらいになってしまいます。なので結構な頻度でこどふぉに参加してしまうと完全に昼夜逆転生活になってしまいます。

全探索すればいい

私が競プロ始めた頃によくあったこととして、問題を解こうとしたときに「賢く解こう」としてしまうということがあったなあと思いました。賢く解こうというか数学的に解こうとか、貪欲で解こうとか、そういう感じです。

例えば、yukicoderの「No.90 品物の並び替え」という問題があります。
https://yukicoder.me/problems/no/90

これはある程度慣れた人なら「N <= 9と制約が小さいから、全ての並び順を全探索するO(N! * N^2)の解法でも十分間に合うな」とぱっと分かる問題です。しかし１年前の私のコードを見ると、「各アイテムをどの位置に挿入したら最も点数が高くなるか？」という怪しい貪欲で解こうとしてWAを食らってます。

このエピソードから得られる教訓として「証明できない貪欲は出来るだけ避けよう」という話もありますが、それ以前の問題として「全ての並び順を調べればいい」という全探索の思考が全く無かったからこのようなコードになってしまったのだと思います。

全探索っていうと何となく「頭の悪い解法、非効率的で競プロには向かない」みたいな先入観があったのですが、全然そんなことは無くて基本中の基本でとっても大事なので全探索の心は常に持っておきたいなと思いました。

まとめ

結構飽き症なので競プロ始めた頃はすぐ飽きるかな～と思ってましたが、意外と１年くらい続きました。（２ヶ月くらい飽きてやってない時期ありますが）
競プロって見た目は地味ですが、多種多様な問題が出されるので「またこの問題か……」みたいなのがあんまり無くて毎回凄く考えさせられます。面白いです。パズルとか考えるゲームが好きな人にはおすすめです。

2017-08-08

Educational Codeforces Round 26

codeforces

久しぶりにブログを書きます。
４完でした。D問題のDPを通せたのは個人的になかなか成長したのではないかと思える回でした。

A. Text Volume

問題概要

いくつかの単語で構成される文が与えられる。
各単語の音量はその単語に含まれる大文字の数で決まり、その文の音量はそれらの単語の音量の最大値で決まる。
与えられた文の音量を求めよ。

感想

これはそのままやるだけですね。強いて言うなら、最初大文字判定を'A' <= chみたいに書いててバグらせたのがアレでした。
asciiコードでは大文字が先に割り振られてるので'A' <= chだと小文字も全部カウントしちゃうんですね。
なので書くとしたらch <= 'Z'じゃないとダメでした。そもそも横着せずにちゃんと'A' <= ch && ch <= 'Z'と書いておけばよいですね。

D言語パワーを使ってスマートに書くとこんな感じ。

void main() {
    readln;
    readln.split.map!(w => w.count!(isUpper)).reduce!(max).writeln;
}

そもそもisUpperっていう大文字判定関数みたいなのがありました。

B. Flag of Berland

問題概要

R, G, Bのみで構成される旗が与えられる。
それがロシアとかイタリアみたいな国旗になっているか判定せよ。

感想

場合分けでゴリ押しました。結構めんどくさくて、めんどくさかったです。
丁寧に場合分けしないとコーナーケースとかで落とされて、割とHackで落とされた人が多かったみたいです。
長いだけなのでコードは省略します。

C. Two Seals

問題概要

a * bの土台となる長方形がある。n枚のシールを持ってて、シールiはx[i] * y[i]の長方形である。
この土台に２枚のシールを貼りたい。シールははみ出しちゃダメで、各辺は土台の辺と並行になるように貼らなければならず、２枚のシールが重なってもいけない。
このとき貼れる２枚のシールの面積の総和の最大値を求めよ。貼れる２枚が無いときは0とせよ。

制約

1 <= n, a, b <= 100
1 <= x[i], y[i] <= 100

感想

nが小さいので２つのシールの全ての組合せを試すO(n^2)解で十分間に合うのでそれをやりました。
１つのシールを左上隅に固定して貼ったとすると、２つの長方形を重ねたような多角形が残るので
そのどちらかの長方形に収まるようにもう一方のシールを貼れるか、みたいな判定をするみたいな。

int n, a, b;
int[] x, y;

void main() {
    scan(n, a, b);

    x = new int[](n);
    y = new int[](n);

    foreach (i ; 0 .. n) {
        scan(x[i], y[i]);
    }

    bool check(int U, int V, int u, int v) {
        return (u <= U && v <= V) || (u <= V && v <= U);
    }

    int ans;

    foreach (i ; 0 .. n) {
        foreach (j ; 0 .. n) {
            if (i == j) continue;
            
            if (x[i] <= a && y[i] <= b) {
                if (check(a - x[i], b, x[j], y[j]) || check(a, b - y[i], x[j], y[j])) {
                    ans = max(ans, x[i]*y[i] + x[j]*y[j]);
                }
            }

            if (x[i] <= b && y[i] <= a) {
                if (check(a - y[i], b, x[j], y[j]) || check(a, b - x[i], x[j], y[j])) {
                    ans = max(ans, x[i]*y[i] + x[j]*y[j]);
                }
            }
        }
    }

    writeln(ans);
}

D. Round Subset

問題概要

n個の整数 a_1, ..., a_n が与えられる。
この中からk個選んで全ての積を取ったときの末尾の連続する0の個数を最大化したい。
その最大値を求めよ。

制約

1 <= k <= n <= 200
1 <= a_i <= 10^18

感想

まず、k個選んだときの末尾の0の個数がどうやって決まるかって話ですがこれは10で何回割れるかっていうことなので
各整数が2を何回含むか、5を何回含むかを前処理で求めておいて、選んだk個のそれらの値をそれぞれ足して、最後にminを取ることで求まります。
それで最大値問題ってことで最初は二分探索かなーとか思って考えてました。何か平均最大化問題みたいな感じで基準を定めてうんたらかんたらみたいな。
あれも「n個からk個とるとき」って感じだったのでそういうパターンかなって思ったのですがどうにも上手くいきそうにありませんでした。
それで次に考えたのがDPでした。「n個からk個とるとき」みたいな問題をDPで解いたことあったなあーとか思い出したので。
なんかちょっとぱっと出てこないんですがありますよね。dp[ここまで見た数][ここまでで選んだ数]みたいなDP問題。
ただこのまま
dp[ここまで見た数][ここまでで選んだ数] = (2の数, 5の数)
として、min(2の数, 5の数)が上回るとき更新、みたいにするとちょっとまずそうだなって思います。
例えば
3 2
4 10 25
みたいなケースで上手くいかなくなるはずです。
だからこのままではまずいけど、
dp[ここまで見た数][ここまで選んだ数][ここまでで取った5の数] = (2の数)
にして、2の数が大きくなるとき更新、にすると上手くいきそうっていうのは何となく分かるかなと思います。
別にこうじゃなくて
dp[ここまで見た数][ここまで選んだ数][ここまでで取った2の数] = (5の数)
としてもいいんですけど、状態数はなるべく少なくしたほうが計算量も少なくなるのでこれより上の奴のほうがいいと思います。
それで実際計算量は大丈夫なのでしょうか？
ここまで見た数 = 200,
選んだ数 = 200,
ここまで取った5の数 = 200 * 25
が最大ケースっぽいのでこれを掛け合わせると2 * 10^8くらいになるっぽいです。
Pythonだとまず間違いなくTLEしますが、Dの力を信じてサブミットするとあっさり300msぐらいで通っちゃいました。凄い速い。
実際DPテーブルを2 * 10^8作るとMLEしそうなので、１個目の変数は１個前しか参照しないから2個でいいっていう奴をやってます。

int n, k;
long[] a;

void main() {
    scan(n, k);
    a = readln.split.to!(long[]);

    auto two = new int[](n);
    auto five = new int[](n);

    foreach (i ; 0 .. n) {
        while (a[i] % 2 == 0) {
            a[i] /= 2;
            two[i]++;
        }

        while (a[i] % 5 == 0) {
            a[i] /= 5;
            five[i]++;
        }
    }

    int lim = n * 25;

    auto dp = new int[][][](2, k + 1, lim + 1);
    fillAll(dp, -1);
    dp[0][0][0] = 0;

    foreach (i ; 0 .. n) {
        foreach (j ; 0 .. k + 1) {
            foreach (f ; 0 .. lim + 1) {
                if (dp[i & 1][j][f] == -1) continue;
                dp[(i & 1) ^ 1][j][f] = max(dp[(i & 1) ^ 1][j][f], dp[i & 1][j][f]);

                if (j + 1 <= k) {
                    dp[(i & 1) ^ 1][j + 1][f + five[i]] = max(dp[(i & 1) ^ 1][j + 1][f + five[i]], dp[i & 1][j][f] + two[i]);
                }
            }
        }
    }

    int ans;

    foreach (f ; 0 .. lim + 1) {
        ans = max(ans, min(f, dp[n & 1][k][f]));
    }

    writeln(ans);
}

AOJ/Atcoder-JOI
何かここの難易度5 ~ 6ぐらいに良い感じのDP問題がたくさんあるのでオススメです。
これで少しDPに慣れていたおかげでこの問題が解けたかなと思ってます。

E. Vasya's Function

問題概要

f(a, 0) = 0
f(a, b) = f(a, b - gcd(a,b)) + 1 (b > 0)
という関数がある。f(x, y)の値を求めよ。

制約

1 <= x, y <= 10^12

感想

少し言い換えると「(a, b) -> (a, b - gcd(a, b))という操作がbが0になるまで何回出来るか？」という問題になることが分かります。
最悪実際にシミュレーションするって解がありますがx, yがめちゃくちゃでかくなるので明らかにTLEしそうでやりたくないですよね。
x = 1だったらy回シミュレーションしなきゃいけないわけだし……
それでaが素数のときはf(a, b) = a / b + a % bで～とか考えましたが結局全然分からなかったので答えを見ました。
操作で変化するのはbだけで、古いgcd(a, b)は新しいgcd(a, b)に必ず含まれているってのがポイントらしかったです。
まずaに含まれる互いに異なる素因数を列挙しておいて、
次にg = gcd(a, b)を求めて、このgcdが変化するときっていうのはaに含まれる素因数を新たに巻き込むときってことなので
そこまでにかかるステップ数を求めて、最後にそれらの最小値を取って、答えに加算して、また最初に戻って……
ってのを繰り返すみたいです。難しいですね。
計算量的には上の一回のループがaに含まれる異なる素因数分かかって、ループする回数はgcdが倍倍倍で増えていくからlogぐらいでみたいな感じであんまりかからなさそうです（雑計算）
結局最初にaの素因数分解にかかる時間が一番大きいような気がします。

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;
import std.numeric;

immutable long inf = 10L^^13;
long x, y;

void main() {
    scan(x, y);

    auto xf = factrize(x);

    debug {
        writeln("xf:", xf);
    }

    long ans;

    while (y > 0) {
        long g = gcd(x, y);

        if (g == x) {
            ans += y / g;
            break;
        }
        
        long m = inf;

        foreach (p ; xf) {
            long mp = (y - (y / (p * g)) * p * g) / g;
            if (0 < mp && mp < m) {
                m = mp;
            }
        }

        ans += m;
        y = y - m * g;
    }

    writeln(ans);
}

auto factrize(long x) {
    auto res = new long[](0);

    for (long p = 2; p*p <= x; p++) {
        if (x % p == 0) {
            res ~= p;
            while (x % p == 0) {
                x /= p;
            }
        }
    }

    if (x > 1) {
        res ~= x;
    }

    return res;
}

2017-06-18

Educational Codeforces Round 23

codeforces

参加しました、３完でした。Cはもうちょっと早く解けたかったな、という感想ですがなかなか難しいものです。
Dは結構考えたんですが全然分からず、解説見て勉強になりました。典型問題らしいです。

A.o
B.o
C.xo

そういえば今回はpythonじゃなくて個人的に流行のD言語で参加しました。なので掲載コードもD言語です。
ブログタイトル詐欺みたいになってますが、そんなに見てる人いないだろうしいいかな。
pythonのコード期待してる人がもしいたら申し訳ないですが。

A. Treasure Hunt

問題概要

あなたは２次元座標上で(x1, y1)にいる、(x2, y2)に行きたい。
移動手段は謎のポーションで、それを使うと現在位置から相対位置で(x, y), (-x, y), (x, -y), (-x, -y)ずれたところのいずれかの場所に行ける。
このポーションは無限に使えると仮定してよい。(x1, y1)から(x2, y2)に行けるか判定せよ。

感想

現在位置は(0, 0)と仮定しても一般性を失わないので、(0, 0)から(a, b)に行けるか判定する問題だと思うことにします。

とりあえず、aがxの倍数とか、bがyの倍数じゃないと行けなさそうだなっていうのは分かります。実際そうでないときは行けません。

問題はこの条件が必要十分条件であるか、つまり「aがxの倍数かつbがy倍数ならば行ける、そうでないなら行けない」と言えるかということですが、自信が無いですよね。
実際この問題の例２がそれを否定してくれる例になっています。aがxの倍数でbがyの倍数なのにNOらしいです。

こういうのは考えてても仕方ないのでグラフに書いてみるといいと思います。原点から幅優先探索的にポツポツと行ける点を描いてみると何となく法則が見えてきたり来なかったりします。
ちょっと図を作るのがめんどくさいので省略しますが、適当に作ってみると行ける点が互い違い、というか何か周期２でズレてたりするのが分かるかと思います。
周期２が何となく見えるので偶奇が必要になりそう、という発想ができたら、x/aとy/bの偶奇が一致してないと行けなさそうだということも分かって、これが必要十分条件になることが何となく分かります。

なんで？ってことですが、a/xしてb/yするってことは１つのステップで行けるところが(+1, +1), (+1, -1), (-1, +1), (-1, -1)であると考えることに等しくなって、この移動方法は偶奇を保存しながら進むからです。

って後付で説明するのは簡単（それでもちょっと難しい気がする）ですが、最初のサブミットに17分かかってるのでAの割に難しかったです。

というわけでコードです

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.container, std.math, std.typecons;

int x1, y1, x2, y2;
int x, y;

void main() {
    scan(x1, y1, x2, y2);
    scan(x, y);

    if (abs(x1 - x2) % x || abs(y1 - y2) % y) {
        writeln("NO");
        return;
    }

    int xd = abs(x1 - x2) / x;
    int yd = abs(y1 - y2) / y;

    if ((xd - yd) & 1) {
        writeln("NO");
    }
    else {
        writeln("YES");
    }
}

void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

pythonに慣れているとかっこがいっぱいあるのが若干気になりますが、慣れてくると気にならなくなると思ってます。
ここで定義してるscanってのが結構便利で可変長引数で変数が受け取れて、それらの型に合わせていい感じに標準入力から値を読み込んで保存してくれる奴です。他の人が使ってたのを丸パクリしました。
テンプレートってやつらしいですが、正直あんまり良く分かってません。けど便利です。
他のC++のコードとか見るとマクロだらけだったりしますが、D言語はそんなにマクロとか使わなくてもいいので結構スッキリ書けて良い感じです。

B. Makes And The Product

問題概要

要素数nの配列aが与えられる。a[i]*a[j]*a[k]が最小値となるような３つ組(i, j, k)(i < j < k)が何通りあるかを求めよ。

制約

3 <= n <= 10^5
1 <= a[i] <= 10^9

感想

愚直に全ての３つ組(i, j, k)について試して数え上げようとするとこれはO(n^3)になってしまい明らかに間に合いそうにありません。
でも３つの積a[i]*a[j]*a[k]が最小値になるときってどんなとき？と考えると、a[i] > 0ですから明らかに小さい順に3つ取ってきてそれを掛け合わせたときだな、と分かるとそんなに難しくはなさそうです。計算量に余裕があるのでとりあえずソートしておきます。
ただ、単純に、例えばa[0] < a[1] < a[2] < a[3] < ... みたいになってれば明らかに1通りしかありませんが、a[0] = a[1] = a[2] = a[3] = ... < a[j] < ...みたいになってたりするとちょっとめんどくさそうです。
ここは最小値が何個あるかで場合分けしてしまうのがよさそうです、そんなに数も多くないですから。

ここでaに含まれるa[2]の数をxと置いておきます。理由は見ていけば分かります。

最小値が1個だけのとき

つまりa[0] < a[1] ...のときですがこれは次に小さい要素に依存します。
a[1] < a[2]なら、最後に入るのはa[2]と同じ値であれば組合せとしては何でもよいので答えはxになります。
a[1] = a[2]なら、最後の２つの選び方が何個あるか、ということになり、これは組合せとしてxC2、つまりx * (x - 1) / 2個あります。

最小値が2個だけのとき

このときは、a[0] = a[1] < a[2]となっています、これは最後に入るのがa[2]と同じ値のものであればよいというさっきと同じ論法でx通りになります。

最小値が3個以上あるとき

このとき、a[0] = a[1] = a[2] ...となっています。これは最初の３つの値と同じ値であればどの３つの組合せでもよいので、xC3、つまりx * (x - 1) * (x - 2) / 6通りになります。

というわけで、入力された配列を最初にソートしておいて、次にa[2]の数を数えて、最後は上の場合分けに沿って答えを求めればよい、ということになります。

「最小値を取るのは小さいほうから３つ取ったとき」ということはほぼ明らかですから、後は考えられる全ての場合を考えて答えを求めればよいという感じなので、個人的にはAより簡単かなと思いました。

ソースコードはこんな感じです。

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.container, std.math, std.typecons;

int n;
int[] a;

void main() {
    scan(n);
    a = readln.split.to!(int[]);

    a.sort();

    long ans, x;

    x = a.count(a[2]);

    if (a[0] < a[1]) {
        if (a[1] < a[2]) {
            ans = x;
        }
        else {
            ans = x * (x - 1) / 2;
        }
    }
    else if (a[1] < a[2]) {
        ans = x;
    }
    else {
        ans = x * (x - 1) * (x - 2) / 6;
    }

    writeln(ans);
}

void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

int型ではオーバーフローする可能性があるのでlong型を使わなければいけないことに注意しないといけませんね。
python使ってたら多倍長整数なのでオーバーフローとかほぼ何も考えずにやってたので、その辺は少し慣れないと大変そうです。今はよくオーバーフローさせてバグを生みだして辛い思いをしています。

ちなみにこの問題はソートしなくても小さい方から３つの値だけ分かればよいので、O(N)で解くこともできるんですがちょっとめんどくさいですね。計算量的にO(NlogN)でも余裕なのでO(N)で解こうとしなくてもいいんですが。

そういえばAtcoderで似たような問題を解いたことがありました。ABC057-Dですね。
D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder

C. Really Big Numbers

問題概要

正整数xがx - (xを十進数で表したときの桁和) >= sであるとき、xをほんとに大きい数と呼ぶことにする。正整数n, sが与えられるので、n以下の正整数にほんとに大きい数がいくつあるか答えよ。

制約

1 <= n, s <= 10^18

感想

まず制約を見て総当たりで数え上げはとても無理だということは分かります。

実は最近桁DPというものを覚えたので、それを応用できないかと最初に考えました。18桁の桁和って高々18 * 9程度にしかならないので何かそれを状態に持たせるといいんじゃないか、みたいな。
dp[今まで見た桁数][n未満フラグ][ここまでの桁和]で数え上げるみたいな。でも最終的に桁和がmの整数が～個ありました、みたいな情報だけ分かってもどうしようもないんですよね。元の整数が何だったか分からないと判定できないので。だからこれはダメそうでした。
それで、まあ仕方ないのでとりあえず規則性見つけてみるかと思って、1～30ぐらいで考えると、10増えると(それ - それの桁）が9増えるんですよね。だから(s + 8) / 9 * 10以上の整数は全部オッケーかあ、みたいに考えて適当に出したら不正解でした。
「あれ？」って思ってバグかなあと思ってたんですが、localで適当にpythonで愚直コード書いて見てみると、9増えるのは下1ケタが繰り上がったときだけで、99 -> 100みたいなときは+18でした。さらに999 -> 1000のときは+27だったり。
ここで結構うわーってなってこれを数学的にどう処理したらいいんだ……みたいなこと考えて思考停止して停滞モードになりました。
でも別に数学的に解を求める必要は無いんですよね、これ数学コンテストじゃないから。
（それー桁和）の結果をよく観察してみると、これは単調増加関数になってます。ということは、二分探索が使えるじゃん！って気づくとなんだーって感じで二分探索書いて通しました（ほんとはそっからさらにバグらせてアレな感じでしたけど……）

このとき結構焦ってたので単調性を示せなかったのですが、落ち着いて考えるとそれ自体が+1されたとき、桁上りが無かったら桁和も+1で変化無し、桁上りがあると例えば09->10なら桁和は-8されて、099->100なら桁和が-17されて、となってるので（それー桁和）は桁上りした回数*9増えるので単調増加関数であることが分かりますね。

というわけで無事二分探索で正しく解が求まることが分かりました。

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.container, std.math, std.typecons;

long n, s;

void main() {
    scan(n, s);

    if (calcdif(n) < s) {
        writeln(0);
        return;
    }

    long top, btm, mid;

    top = n;
    btm = 0;

    while (top - btm > 1) {
        mid = btm + (top - btm) / 2;

        if (calcdif(mid) >= s) {
            top = mid;
        }
        else {
            btm = mid;
        }
    }

    long ans = n - top + 1;

    writeln(ans);
}

long calcdif(long x) {
    return x - digitsum(x);
}

unittest {
    assert(calcdif(0) == 0);
    assert(calcdif(1) == 0);
    assert(calcdif(9) == 0);
    assert(calcdif(10) == 9);
    assert(calcdif(13) == 9);
    assert(calcdif(34) == 27);
    assert(calcdif(99) == 81);
    assert(calcdif(100) == 99);
    assert(calcdif(315) == 306);
    assert(calcdif(1000) == 999);
}

long digitsum(long x) {
    return x > 0 ? digitsum(x / 10) + x % 10 : 0;
}

unittest {
    assert(digitsum(123) == 6);
    assert(digitsum(0) == 0);
    assert(digitsum(1) == 1);
    assert(digitsum(100) == 1);
    assert(digitsum(375826) == 31);
    assert(digitsum(98) == 17);
}

void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

D言語はunittestっていうのが書けて、コンパイルするときに

dmd -unittest main.d

みたいにオプションをつけると実行時にunittestでassertチェックしてくれます。
関数作ってそれがバグってるとどの処理でバグったか分からなくなり面倒なことになるので、関数を作ったらunittestを書く、ってのは結構いいと思います。ただtest作るのも面倒なのでどこまでちゃんとやるかはトレードオフですが……
もちろん向こうの環境で実行されるときはオプション無しでコンパイルされるので書いたunittestは消さなくても大丈夫です（ブログとかに乗せるときは消したほうが見やすいと思いますが、ここではD言語の紹介も兼ねて）

あ、そういえば二分探索の書き方もオーバーフローが起こらないような書き方に直してますね。python感覚で普通に

mid = (top + btm) / 2

って書いちゃうとtop側にどんどん収束していくような場合、topの初期値が大きすぎるとオーバーフローすることがあるみたいですね。
なので

mid = btm + (top - btm) / 2

って書いたほうがオーバーフローが確実に起こらずに良い書き方みたいです。

D. Imbalanced Array

問題概要

要素数nの配列aが与えられる。配列内の区間[a[l], a[l+1], ..., a[r]]に対して、（その区間内の最大値 - その区間内の最小値）をその区間のimbalance valueと呼ぶことにする。
aの全ての区間のimbalance valueの総和を求めよ。

制約

1 <= n <= 10^6
1 <= a[i] <= 10^6

感想

愚直に全ての区間のimbalance valueを求めて足しあげようとすると最低でもO(n^2)はかかります、これではTLEしてしまいます。
こういうのを考えるときの定跡（？）として、区間に着目するのではなく点に着目する、つまり各要素が何回足し引きされるのか、を考えて上手い事処理するとO(n)とかO(nlogn)で解けそうです。

区間に着目するのではなく点に着目して計算量を落とすという考え方の類題としては例えばこんなのとか、区間じゃなくて部分集合になってますが点に着目するというのは一緒です
http://codeforces.com/contest/810/problem/C

じゃあ各要素が何回足し引きされるのか考えてみます。
例えば足される回数は何回ぐらいでしょうか？
imbalance valueの定義からして、その要素を含む区間でかつその要素が最大値となる区間の個数であることは分かります。
例えば a = [3, 1, 4, 1, 5, 9, 2, 6, 5] だったとして、a[2] = 4が最大値となる区間は何個あるか数えてみると
[4], [1, 4], [4, 1], [1, 4, 1], [3, 1, 4], [3, 1, 4, 1]
で6通りあるので、a[2]は6回足されることが分かりました。

この個数をなるべく速く求めることが目的です。
もうちょっと考えるとその要素を含む区間の個数は（左端の選び方）×（右端の選び方）で求められることが分かります。
a[2] = 4だったら、左端は0, 1, 2の3通りあり、右端は2, 3の2通りあるので3 * 2 = 6通りで、確かに一致しています。

この（左端の選び方）は要素iから左に動かしていってa[i]が最大値であり続けられる境界が分かれば後は引き算で求められることが分かります。右端ならその逆です。
実際はa[i]と同じ要素が出てきたときどうすればいいか考えなきゃいけませんがimbalance valueを考えるときに「複数個あるときは最も左端の最大値を取る」と暗に定義しておけば、左端に伸ばしていくときはa[i]と等しい要素が出てきた時点でアウト、右端に伸ばしていくときはa[i]と等しい要素が出てきてもまだ伸ばせる、と考えればいいことが分かります。

……とまあ、このあたりまではコンテスト中に考察できたのですが問題はその境界をどうやって速く求めるか？っていう話ですよね。ほんとに愚直に伸ばしていったらO(n^2)かかってしまうので意味がありません。
それで何か累積maxとか取って二分探索すればO(nlogn)でいける？みたいに考えてたんですが、普通に間違っており、どうしようもありませんでした。

考察的にはかなりいいとこまで行ってるのでオーバーしてもちょっと考えたりしたんですが、何かセグ木とか使うのかなあ……とか考えていい感じの答えが分からなかったので解説を見ました。

するとどうやらセグ木とかは全然使う必要が無く、スタックを使うだけでいけるらしいです。
各要素iについてそっから左に伸ばしていって初めてa[i]が最大値で無くなるところを格納する配列をleftmax[i]とします。アルゴリズムは以下のような感じです。スタックは添え字を詰めていくために使うものです。

i = 0, 1, 2, ..., n - 1と左端から順に見ていく
i = 0のとき、空のスタックに0をプッシュして、leftmin[0] = -1とする
i > 0のとき、以下の一連の手順を繰り返す
スタックが空でないとき、そのスタックの一番上に入ってる添え字をjとしてa[j]とa[i]を比較する、もしa[j] <= a[i]ならばスタックからjをポップしてa[j] > a[i]となるかスタックが空になるまで繰り返す
上の操作が終わった後、スタックの状態を見て空ならleftmin[i] = -1とし、そうでないなら、スタックの一番上に入ってる添え字jを対応付ける, leftmin[i] = j
最後にスタックにiをプッシュして、次の要素に移る

とこういう感じになってます。このアルゴリズムで簡単にleftminが求まってしまいます。計算量は各添え字は1回プッシュされ、高々1回ポップされる程度なので、n回ループでO(n)、スタックの操作でもO(n)なので全体でO(n)の計算量となっています。

右端がどこまで伸ばせるかを知りたいなら配列を逆順に読んでいくものに書き換えるだけです（ただしポップする条件の不等号が微妙に変わってa[j] >= a[i]になることに注意してください、これはimbalance valueの定義をするときに「複数の最大値がある場合は最も左端のものを取る」としたからです）

頭の中で考えただけではちょっとこれでなんで求まるのか分かりづらいですが、小さ目のケースを作って試してみると何をやっているのか分かると思います。

import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.container, std.math, std.typecons;

int n;
int[] a;

void main() {
    scan(n);
    a = readln.split.to!(int[]);

    int[] leftmin = new int[](n);
    auto st = Stack!int(n + 10);

    foreach (i ; 0 .. n) {
        while (!st.empty && a[st.top] > a[i]) st.pop;

        leftmin[i] = (st.empty ? -1 : st.top);
        st.push(i);
    }

    st.clear;

    int[] rightmin = new int[](n);

    foreach_reverse (i ; 0 .. n) {
        while (!st.empty && a[st.top] >= a[i]) st.pop;

        rightmin[i] = (st.empty ? n : st.top);
        st.push(i);
    }

    st.clear;

    int[] leftmax = new int[](n);

    foreach (i ; 0 .. n) {
        while (!st.empty && a[st.top] < a[i]) st.pop;

        leftmax[i] = (st.empty ? -1 : st.top);
        st.push(i);
    }

    st.clear;

    int[] rightmax = new int[](n);

    foreach_reverse (i ; 0 .. n) {
        while (!st.empty && a[st.top] <= a[i]) st.pop;

        rightmax[i] = (st.empty ? n : st.top);
        st.push(i);
    }

    long ans;

    foreach (i ; 0 .. n) {
        ans += 1L * (i - leftmax[i]) * (rightmax[i] - i) * a[i];
        ans -= 1L * (i - leftmin[i]) * (rightmin[i] - i) * a[i];
    }

    writeln(ans);
}

void scan(T...)(ref T args) {
    auto line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront;
    }
    assert(line.empty);
}

struct Stack(T) {
private:
    int N, peek;
    T[] data;

public:
    this(int size) 
    {
        N = size;
        data = new T[](N);
    }

    bool empty() @property
    {
        return peek == 0;
    }

    bool full() @property
    {
        return peek == N;
    }

    void push(T x) @property
    {
        assert(!full);
        data[peek++] = x;
    }

    void pop() @property
    {
        assert(!empty);
        --peek;
    }

    T top() @property
    {
        return data[peek - 1];
    }

    void clear() @property
    {
        peek = 0;
    }

    int length() @property
    {
        return peek;
    }

}

同じことを4回やってるのでちょっと長いですね、関数とか使って上手く書ける人は書いたらいいと思います。不等号とか読み順が逆になったりで微妙に関数化しにくい気がするんですがこの辺も何か上手くできるんですかね。分かりません。

これスマートなアルゴリズムだなーって思ったんですが、実はこれは典型問題らしくて、一般的にStock Span Problemというらしいです。他の人のソースコードをちらちら見てたら一番上にStock Span Problemというコメントがありました。
www.geeksforgeeks.org
見てみると確かに全く同じ問題であることが分かります。勉強になりました。

ちなみにD言語でスタックを使いたいときはわざわざ構造体作らなくてもSListってのがあってそれをスタックとして使うのが普通っぽいんですが、何か知らないですけどSListは結構遅くなっちゃうんですよね。キューも同じでDListってのがあるんですけどやっぱりこれも作ったほうが速くなります。何か公式にはDListのinsertはO(logN)って書いてあるんですけどそのせいですかね、普通はO(1)なんじゃないかと思っているんですけど、ど素人なので分かりません。分かる人がいたら教えてください。

久しぶりにブログ更新しました。
なんかこのブログこどふぉの記事の割合が多い気がします。Atcoderは日本語だし解説記事はもちろん解説動画まで上がるのであんまりブログ書くモチベにならないんでしょうかね。
後単純にAtcoderの問題のほうが難しいのでそもそもブログで解説できるほど習熟してないという面もありますね。