ABC271 C問題の考え方

ABC271 C - Manga の考え方を書きました。

この記事は思考の流れから（ミスを含め）書いています。
答えにジャンプしたい方は こちらへ

問題の要約

• N個の自然数が与えられる
• 「2つを取り除き、代わりに任意の自然数を1つ追加する」という操作を何回でも行ってよい
  • 例：{1, 3, 4} から3と4を取り除き、代わりに2を加えて {1, 2}
• 「1〜M までの全ての数が存在する」という状態を目指すとき、実現可能なMの最大値を返せ
  • 例：{1 2 4 6 7 271} なら、 [1 2 3 4] は実現可能だが [1 2 3 4 5] は不可能。よって答えは 4
• 1 <= N <= 3*10^5 かつ 与えられる自然数は10^9以下

ちなみに、実際の問題文は “マンガを1巻からどこまで読めるか” というストーリーになっていました。
全(10^9)巻のマンガということで、

• 1分で1冊ペースでも読み終わるのに1900年以上かかる
• そもそも最適ケースでも全体の1%も読めない

など、楽しい設定になっています。

印象：「大きい数、不要そう」

入力例1は以下の通りです。

6
1 2 4 6 7 271

この例では、6と271、または7と271を取り除く（売る）ことになります。また、どちらの場合でも4までしか使えません（読めません）。
これを見ていると、「大きい数ほど、要らないんじゃない？」という気がしてきました。
一旦、この考え方でよいか確かめてみましょう。

方針は以下の通りです。

1. 入力を昇順ソートし、dequeに格納する。
2. dequeの先頭が、次に読む巻か？
   • Yes : 取り出す（読んだことにする）。
   • No : dequeの末尾から2つ取り除く（売る）。そして、次に読む巻をdequeの先頭に格納する（購入して本棚へ）

入力例1なら、以下のような動作となります。

ここまで読んだ:0 / 本棚:[1 2 4 6 7 271]
ここまで読んだ:1 / 本棚:[2 4 6 7 271]
ここまで読んだ:2 / 本棚:[4 6 7 271]
ここまで読んだ:2 / 本棚:[4 6] / 売却:(7 271)
ここまで読んだ:2 / 本棚:[4 6] / 購入:(3)
ここまで読んだ:2 / 本棚:[3 4 6]
ここまで読んだ:3 / 本棚:[4 6]
ここまで読んだ:4 / 本棚:[6]

重複があったらどうする？

入力例2を見ると… 1がたくさんありました。

10
1 1 1 1 1 1 1 1 1 1

この問題には、”重複なし”という制約はありません。同じ数字（同じ巻）を複数持っている可能性があります。
これではキューが詰まってしまいます。

ここまで読んだ:1 / 本棚:[1 1 1 1 1 1 1 1 1]

既に読んだ巻が本棚にあった場合は、売ることにしましょう。 売る時点では、次にどの巻を買うべきか判断することができません。 なので、1冊1円で売って財布にしまうことにします。

ここまで読んだ:1 / 本棚:[1 1 1 1 1 1 1 1 1]
ここまで読んだ:1 / 本棚:[1 1 1 1 1 1 1 1] / 財布:1円
ここまで読んだ:1 / 本棚:[1 1 1 1 1 1 1] / 財布:2円
...
ここまで読んだ:1 / 本棚:[] / 財布:9円

そして、本棚が空でも、財布に2円以上あるならば、2円を支払って次に読む本を1冊購入することにします。

ここまで読んだ:1 / 本棚:[]  / 財布:9円
ここまで読んだ:1 / 本棚:[2] / 財布:7円
ここまで読んだ:2 / 本棚:[]  / 財布:7円
ここまで読んだ:2 / 本棚:[3] / 財布:5円
ここまで読んだ:3 / 本棚:[]  / 財布:5円
ここまで読んだ:3 / 本棚:[4] / 財布:3円
ここまで読んだ:4 / 本棚:[]  / 財布:3円
ここまで読んだ:4 / 本棚:[5] / 財布:1円
ここまで読んだ:5 / 本棚:[]  / 財布:1円

少なくともサンプル入出力については、すべて正解することができるようになりました。
これでACできるでしょうか…？

WAケースがある

読んでいない巻が重複所持しているケースとして、次の入力を考えてみます。

5
1 3 3 4 9

上で考えたアルゴリズムを適用します。

ここまで読んだ:0 / 本棚:[1 3 3 4 9]
ここまで読んだ:1 / 本棚:[3 3 4 9]
ここまで読んだ:1 / 本棚:[3 3] / 売却:(4 9)
ここまで読んだ:1 / 本棚:[3 3] / 購入:2
ここまで読んだ:1 / 本棚:[2 3 3]
ここまで読んだ:2 / 本棚:[3 3]
ここまで読んだ:3 / 本棚:[3]
ここまで読んだ:3 / 本棚:[] / 財布:1円

しかし、よく考えてみると、 4 9 を売る代わりに 3 9 を売れば、 4巻まで読むことができるのです。

ここまで読んだ:0 / 本棚:[1 3 3 4 9]
ここまで読んだ:1 / 本棚:[3 3 4 9]
ここまで読んだ:1 / 本棚:[3 4] / 売却:(3 9) # ここで3と9を売る
ここまで読んだ:1 / 本棚:[3 4] / 購入:2
ここまで読んだ:1 / 本棚:[2 3 4]
ここまで読んだ:2 / 本棚:[3 4]
ここまで読んだ:3 / 本棚:[4]
ここまで読んだ:4 / 本棚:[] # 4まで読めた

先に重複の対処をする

「大きい数、不要そう」という印象は間違ってはいませんが、「どれくらい大きいと不要なのか」が曖昧でした。

例えば N=6 のとき、最大で読める巻数は 1 2 3 4 5 6 より 6 です。
7巻以降はどう頑張っても読めないので、一般に、Nより大きい巻は全て不要と言えます。 一方で、N以下の巻は、他の本の状況によって不要だったり必要だったりします。

ところで、N以下の巻でも、初期状態で不要と確定できるものがあります。
重複している巻です。

同じ巻を複数所持している場合、まず最初に、1冊のみを残して他を売ってしまいましょう。

後はこれまでの方針の通り、大きい数（後ろの巻）から売って不足している巻を買うという戦略を取ります。

アルゴリズム

1. まず、重複している巻をすべて売却する。
2. 残った巻を昇順ソートし、dequeに格納する。
3. 以下を、”dequeが空かつ所持金が2円未満”となるまでループする。
   • dequeの先頭が次に読む巻？
     • それを取り出し、読んだことにする。次のループへ
   • 所持金が2円以上？
     • 所持金から2円を引き、次の巻を購入して読んだことにする。次のループへ
   • それ以外の場合
     • dequeの末尾から1つ取り除き、売却したことにする（所持金に1円を足す）。次のループへ

動作例

本棚:[1 3 3 4 9]
本棚:[1 3 4 9] / 財布:1円
# ここからループ
ここまで読んだ:0 / 本棚:[1 3 4 9] / 財布:1円
ここまで読んだ:1 / 本棚:[3 4 9] / 財布:1円
ここまで読んだ:1 / 本棚:[3 4] / 財布:2円 # 9を売却
ここまで読んだ:1 / 本棚:[2 3 4] / 財布:0円 # 2を購入
ここまで読んだ:2 / 本棚:[3 4] / 財布:0円
ここまで読んだ:3 / 本棚:[4] / 財布:0円
ここまで読んだ:4 / 本棚:[] / 財布:0円

サンプルコード

Pythonの場合

from collections import deque

N = int(input())
A = list(set(map(int, input().split()))) # 重複排除済みリスト
A.sort()
A = deque(A)

# 所持金の初期値 = 売却した冊数 = 最初に持っていた冊数 - 現在持っている冊数
wallet = N - len(A)

c = 0 # ここまで読んだ
while True:
    if A and A[0] == c + 1:
        c = A.popleft()
    elif wallet >= 2:
        wallet -= 2
        c += 1
    elif A:
        A.pop()
        wallet += 1
    else:
        break

print(c)

Rubyの場合

N = gets.to_i
A = gets.split.map(&:to_i).uniq.sort # 重複排除済みリスト

# 所持金の初期値 = 売却した冊数 = 最初に持っていた冊数 - 現在持っている冊数
wallet = N - A.size

c = 0 # ここまで読んだ
loop do
  if A[0] == c + 1
    c = A.shift
  elsif wallet >= 2
    wallet -= 2
    c += 1
  elsif A.size > 0
    A.pop
    wallet += 1
  else
    break
  end
end

puts c

回答例

• Python : 実行時間 257 ms
  • https://atcoder.jp/contests/abc271/submissions/35384802
• Ruby : 実行時間 224 ms
  • https://atcoder.jp/contests/abc271/submissions/36172799