解法
- editorialは読み、解説放送も見たとする
- まったく被りなしの場合は答えがN-K+1で、これが最大。ここからダブルカウントしてしまった分を引いていく
- まず、Kの幅ですでにsortedな箇所がいくつあるか数える。その数をSとすると、S-1回だけ多く数えているので引けばいい
- 次に、Kの幅ですでにsortedじゃなくても同じ数列になる場合を考える。例えば以下のような場合
- 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
テストケース生成
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)
注意 sh too many arguments
- 出力が複数行の場合、スペースや改行で区切られるが、その比較はうまくいかないようでtoo many argumentsと表示される
- 比較時のみ、改行やスペースを除去すればちゃんと比較できた
- 追記：下のように＄変数をダブルクオーテーションでくくると比較できる(ifの行)
g++ answer.cpp
g++ naive.cpp -o naive.out
while true; do
python3 ./generate.py > input.txt
ans1=$(./a.out < input.txt)
ans2=$(./naive.out < input.txt)
if [ "$ans1" != "$ans2" ]; then
echo "Wrong Answer"
echo "a.out", $ans1
echo "naive", $ans2
exit
fi
done
