【競プロ初心者】ストレステストってなんだ？

ABC175に参加し、いつものように敗北感に包まれていた私の目にchokudaiさんのこのつぶやきが飛び込んできた。

「数学問題わかんない」って言ってる人、だいたい適当に計算式を書くガチャとかやってるので、それを書く前にストレステストとか組んでほしいなあ、とは思ってる。昨日のABC-Cとかも、K<100000くらいにすれば愚直シミュレーション解作って比較とか出来るので……。

これを読んだ私は思いました。意味がわからない、と。
なんだストレステストって。その愚直シミュレーション解ってのがあれば、ぼくの考えたゴリラみたいなコードもACするのか？　と。

その後、chokudaiさん直々に解説ツイートを連投され、最後にこう締めくくりました。

この一連のツイート、まぁ流れちゃうので誰かQiitaとかにパクって書いてくれてもいいのよ。

というわけで、勉強もかねて大いにパクらせていただきます。

ABC175-C問題を解く

Walking Takahashi
コンテスト当日にこの問題を読んだ私は悩みに悩んだ末、次のような解答を(2回WAを出した後に)それなりの自信を持って送った。

ABC175_C.py

X,K,D = map(int,input().split())
b = 0
b = abs(X)//D
if b <= K:
    K -= b
else:
    b = K
    K = 0   
if X > 0:
    X -= D*b
elif X < 0:
    X += D*b   
if K == 0:
    print(X)
else:
    if X == 0:
        if K % 2 == 0:
            print(X)
        else:
            print(D)
    elif X > 0:
        if abs(X-D) < abs(X):
            X -= D
            K -= 1
        if K % 2 == 0:
            print(abs(X))
        else:
            print(min(abs(X-D),abs(X+D)))
    elif X < 0:
        if abs(X+D) < abs(X):
            X += D
            K -= 1
        if K % 2 == 0:
            print(abs(X))
        else:
            print(min(abs(X-D),abs(X+D)))

これを見た皆さんは、なんだこのゴリラコードはと思っただろう。
いきなり出てくる変な名前の変数はなんだ。なんかif文で滅茶苦茶になってる。と思っただろう。今回の件とは関係のない部分なのでどうかご容赦いただきたい。

ところでこのコード、WAになる。原因は

if K == 0:
    print(X)

Xの値がマイナスだった時にここでマイナスの値が出てしまうからなのだが、そもそもの方針がおかしかったかと悩みに悩んだ私はここに気づくのに20分くらいかかった。こんな時にストレステストってのがあるといいらしい。

ストレステストってなに？

ストレステストって言ってる人何人か見たからそういう言い方したけど、なんか負荷テスト感あるから言い方変えたほうがいいかも、って気はする。

わりとふわっとした言葉っぽい。
結局のところ愚直シミュレーション解とやらを使って、書いたコードの出力と比較してみることっぽい。

愚直シミュレーション解ってなに？？

要するに絶対間に合わないけど全探索しちゃう解答のことらしい。
今回の場合だとXの絶対値からDをK回引いた値の絶対値が正しい出力になります。
なりますが、Kが最大値だったりすると余裕でTLEする制約なので当然そんなことは考えません。

しかし、提出するとTLEしますがこいつはKが小さい場合で考えると間違いなく正しい出力を弾き出してくれるはず。
そこでこいつの出す出力と、私のゴリラコードの出力を比較して差異を発見しようってわけだ。
つまり、こういうのを書く。

sutoresu.py

def solver1(X, K, D):
    b = 0
    b = abs(X)//D
    if b <= K:
        K -= b
    else:
        b = K
        K = 0   
    if X > 0:
        X -= D*b
    elif X < 0:
        X += D*b   
    if K == 0:
        return X
    else:
        if X == 0:
            if K % 2 == 0:
                return X
            else:
                return D
        elif X > 0:
            if abs(X-D) < abs(X):
                X -= D
                K -= 1
            if K % 2 == 0:
                return abs(X)
            else:
                return min(abs(X-D), abs(X+D))
        elif X < 0:
            if abs(X+D) < abs(X):
                X += D
                K -= 1
            if K % 2 == 0:
                return abs(X)
            else:
                return min(abs(X-D),abs(X+D))

def solver2(X, K, D):
    for i in range(K):
        X = abs(X)-D
    return abs(X)

X,K,D = map(int,input().split())

print(solver1(X,K,D))
print(solver2(X,K,D))

で、怪しい値を適当にいれる。

見つけた！！

見つからないんですけどって時

ランダムな値をぶちこんでみるのも手のようです。
今回の場合だとKが小さい場合で探索します。
さっきのコードの入出力部分を

while True:
    X=random.randint(-10000,10000)
    K=random.randint(1,500)
    D=random.randint(1,10000)

    if solver1(X, K, D) == solver2(X, K, D):
        print("OK:"+str(solver1(X, K, D))+","+str(solver2(X, K, D))+" input:"+str(X)+" "+str(K)+" "+str(D))
    else:
        print("NG!")
        print("input:"+str(X)+" "+str(K)+" "+str(D))
        print("solver1:"+str(solver1(X, K, D)))
        print("solver2:"+str(solver2(X, K, D)))
        break

こんな感じにしてみると

発見！！

見つからないんですけど！！　って時

これで例えばX,Dも小さい範囲で試すと実は動いちゃうんだけど、OKしか出なかった場合は、
・そもそも愚直解の考え方or実装が間違っている
・大きいケースでだけ動かない（＝9割以上オーバーフロー）
のどっちかなので、どちらかを疑えばOK。考えることが減って嬉しくなる感じ。

つまり

あれ～？　解き方はあってると思うんだけどな～。
なんかWAが出るなぁ。どうしてだぁ～？？
って時に使えるテクニックです。ギリ茶コーダーになれてない私にはとっても助かる考え方で非常に勉強になりました。
駆け出しにもわかりやすく解説を投げてくださるchokudaiさんに心より感謝申し上げます。