B - Sorting a Segment ~テストケース生成してナイーブ解と比較 naive~

Quiz

https://atcoder.jp/contests/agc038/tasks/agc038_b

Submission

https://atcoder.jp/contests/agc038/submissions/7654290

解法

  • editorialは読み、解説放送も見たとする
  • まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントしてしまった分を引いていく
  • まず、Kの幅ですでにsortedな箇所がいくつあるか数える。その数をSとすると、S-1回だけ多く数えているので引けばいい
  • 次に、Kの幅ですでにsortedじゃなくても同じ数列になる場合を考える。例えば以下のような場合

f:id:peroon:20190922171120p:plain

  • K+1の幅で見て、左端がmin, 右端がmaxであればi, i+1はequivalentである
  • これはK+1個を入れたsetを作ることで高速にチェックできる。計算量はiを全部動かしてO(N log(K))
    • 最小値 *set.begin()
    • 最大値 *set.rbegin()
  • iをずらすたびにsetから要素削除・要素追加して更新していく
  • i, i+1がequivalentである数を数えた結果Cだったとすると、Cだけ多く数えているので引けばいい
  • まとめると、answer = N-K+1 - (S-1) - C

テストケース生成

  • 考える幅がKだったりK+1だったり、setのrbeginを使ったりで添え字ミスが発生しやすく、サンプルでは通るが提出後ほとんどWAとなった
  • この機会なのでテストケース生成をちゃんとやってみた
  • アルメリアさんの記事に詳しい https://betrue12.hateblo.jp/entry/2019/09/07/171628
  • 用意するものとして
    • 解法.cpp
    • 愚直解.cpp
    • サンプル入力生成.py
    • それを回す.sh
  • これを回すことで、ローカルでWAとなるサンプルが作れ、最終的に無事ACすることができた

naive解のnaive.outを出力

g++ -o naive.out naive.cpp

サンプル入力生成.py

import random
N = random.randint(4, 10)
K = random.randint(2, N)
print(str(N) + ' ' + str(K))
A = range(1, N+1)
A = list(A)
random.shuffle(A)
print(*A)
  • できるだけ小さいNで見つかったほうが検証が楽