lst[i + 1] = i とならないようにする手順

Question

#問題

AtCoder ABC72 D問題より

#方針
① lst[i + 1] = i を満たしてしまっているような i (0 <= i <= N - 1) を探索し、lst[i] += 1 とする。

② 0が出現する区間に用はなく、1が出現する区間を、その区間の長さとともに data に格納する。

③ 区間の長さが1の時は、1回隣の要素とswapを行えば良いので、1を。区間の長さが2以上の時は、一番左の最小の要素を一番右まで持ってくる回数であるlen(list(v)) - 1を求める（[..., 3,4,5, ...]となっているなら、[3,4,5]→[4,3,5]→[4,5,3]（3 - 1 = 2回）のように）。

④ 以上を全ての1で出来た区間で行い、要したswapの回数を答えとして出力する。

#ソースコード

from itertools import groupby

N = int(input())
p = list(map(int, input().split()))

lst = [0] * N
for i in range(N):
    if i + 1 == p[i]:
        lst[i] += 1

data = []
for k, v in groupby(lst):
    data.append([k, len(list(v))])

data = [el for el in data if el[0] == 1]

cnt = 0
for el in data:
    if el[1] == 1:
        cnt += 1
    elif el[1] > 1:
        cnt += el[1] - 1

print(cnt)

#質問
サンプル入力や、手元で行った実験では全てうまくいったのですが、コードを提出するとごく一部のテストケースでバツを食らいます。古いコンテスト故にそのテストケースが公開されておらず、自分でも上の考え方のどこがどう間違っているのかが見えずにいます。いささか雑な形の質問となり恐縮ですが、お力添え頂ける箇所がございましたら、ご指摘のほどよろしくお願い申し上げます。

Answer 1

例えば、このような入力では誤答になります。

4
1 2 3 4

正解は2ですが、質問文のコードでは3になります。
(1-2、3-4の2回のswapで済みます）
③の長さ2以上の区間を処理する方法が誤っています。上の例の様に、1回swapすると1が連続する区間が2減るのに気づいてください。

なお、解説資料にはもっと簡潔に解法が書かれています。詰まったらそちらを読んでみるのも良いでしょう。

Comments

[kay_ventris4]

ご丁寧な回答ありがとうございます。
cnt = 0
for el in data:
　　cnt += math.ceil(el[1] / 2)
として通りました。

実際のところは貪欲法を使えばO(N)で難なくいけたみたいですね。
これからも精度をあげていきたいと思います。ありがとうございました。

[hope_mucci]

ACできて何よりです。
今回の様に、入力例では出てこない特殊なケースを見極めることも競技プログラミングは重要です。
ランダムな値だけでなく、入力境界値ややたら綺麗に並んだデータがWAやLTEを誘発する問題もあります。そのようなテストケースをぱっとおもいつけるのも1つの能力だと思います。

[kay_ventris4]

確かにその通りですね。
特に詰まった時は原点に帰ってそうしたところもくまなく調査するように心がけたいと思います。

Answer 2

例えば[..., 3, 4, 5, 6, ....]の場合、3と4、5と6を入れ替えて[..., 4, 3, 6, 5, ....]になればOKなので、2回でできます。

③ 区間の長さが1の時は、1回隣の要素とswapを行えば良いので、1を。区間の長さが2以上の時は、一番左の最小の要素を一番右まで持ってくる回数であるlen(list(v)) - 1を求める

が間違ってますね。

同様にいくつかのパターンで考えると、len(list(v)) - 1 ではなく、何が正しいか気づくと思います。

Comments

[kay_ventris4]

cnt = 0
for el in data:
　　cnt += math.ceil(el[1] / 2)
とすることでコードが通りました。
ありもしないルールを勝手に自分の中で作っていました。今後気をつけたいと思います。
ご丁寧にありがとうございました。