AtCoder が提供しているABC（AtCoder Beginner Contest）271 のC問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
C問題 Manga（Difficulty : 842）
問題はリンク先をご覧ください。
問題として述べられていることを効率よく実装する必要があります。AtCoder Problems による Difficulty は、842 でした。
解答案
問題を解く方針を書きだします。
- 問題を読み込む。
- 明らかに売る本を決める。
- 小さい巻から読んでいく。
- 足りない本を買う。
- 売る本を補充する。
- 売る本がなくなったら、それが解答になる。
もう少し手順を細かく決めていきましょう。
- 明らかに売る本を決める。売る本の冊数は変数 for_sale に記憶する。
- もっとも多く読めても N 冊しか読めない。N + 1 巻以上の巻はすべて売る。
- 重複している巻もすべて売る。
- 小さい巻から読んでいき、次巻がないときに以下を行う。
- 売る本が2冊以上ある場合に、それを売り、次巻を買う。
- 読んでいない一番巻数が多い巻を売る。
- 次巻のチェックを行う。
- 読むべき次巻が、いまある巻の一番大きい巻を超えたら、そこまで読んだ巻が解答になる。
C++ プログラム例（ABC271C）
ある巻が存在するかしないかを bool 型の配列で管理します。N 巻より大きなものは、売ってしまいますが、N + 1 巻までアクセスする可能性があるため、配列の大きさは、N + 2 となります（添え字 N ＋ 1 の要素は、必ず false になり、門番になります）。
以下の変数を使います。
- 次の読むべき巻を表す left、left より小さい巻はすべて読んでいる。
- 持っている巻で一番大きい巻を表す right、売ることにより right は小さくなる。
- left ＞ right となった時点で、left – 1が解答となる。
以下は、C++ の実装です。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<bool> book(n + 2, false);
int for_sale = 0;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
if (a > n) {
++for_sale;
} else if (book[a]) {
++for_sale;
} else {
book[a] = true;
}
}
int left = 1;
int right = n;
while (true) {
if (left > right) {
break;
}
while (book[left]) {
++left;
}
if (for_sale >= 2) {
for_sale -= 2;
book[left] = true;
++left;
} else {
while ((right != 0)&& !book[right]) {
--right;
}
if (left <= right) {
++for_sale;
book[right] = false;
--right;
}
}
}
cout << left - 1 << endl;
return 0;
}2024年4月27日追記
解の二分探索を使ったプログラムも紹介します。
前準備として、重複した本の冊数を変数 for_sale に、配列 book に本の巻数を格納してソートしておきます。ある巻まで読めるのか読めないのか関数 is_ok で判定しながら二分探索します。この場合、for_sale と book への値の格納と、判定関数 is_ok を書くことに集中できるため、間違いにくいと考えています。
#include <bits/stdc++.h>
using namespace std;
vector<int> book;
int for_sale = 0;
bool is_OK(int mid)
{
int have = upper_bound(book.begin(), book.end(), mid) - book.begin();
int remain = book.size() - have + for_sale;
return (mid - have <= remain / 2);
}
int main()
{
int n;
cin >> n;
set<int> dup;
for (int i = 0; i < n; ++i) {
int a;
cin >> a;
if (dup.find(a) == dup.end()) {
dup.insert(a);
book.push_back(a);
} else {
++for_sale;
}
}
sort(book.begin(), book.end());
int ng = n + 1;
int ok = 0;
while (abs(ok - ng) > 1) {
int mid = (ok + ng) / 2;
if (is_OK(mid)) {
ok = mid;
} else {
ng = mid;
}
}
cout << ok << endl;
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC271C）
C++ 版をベースに Python 版をプログラムしました。Python らしいプログラムになっていないかもしれません。
"""AtCoder Beginner Contest 271 C"""
n = int(input())
book = [False] * (n + 2)
for_sale = 0
for a in map(int, input().split()):
if a > n:
for_sale += 1
elif book[a]:
for_sale += 1
else:
book[a] = True
left = 1
right = n
while True:
if left > right:
break
while book[left]:
left += 1
if for_sale >= 2:
for_sale -= 2
book[left] = True
left += 1
else:
while right != 0 and not book[right]:
right -= 1
if left <= right:
for_sale += 1
book[right] = False
right -= 1
print(left - 1)Python 版も「AC」と判定されました。
最後に
丁寧に手順を実装していけば、解ける問題にもみえますが、完了している条件を正確に表現するのは、難しい問題と感じました。
引き続き ABC の問題を紹介していきます。
