AtCoder

ABC271 C問題(Manga)を解く

AtCoder_ABC271_C

AtCoder が提供しているABC(AtCoder Beginner Contest)271 のC問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Manga(Difficulty : 842)

問題はリンク先をご覧ください。

ABC271 C問題 Manga

問題として述べられていることを効率よく実装する必要があります。AtCoder Problems による Difficulty は、842 でした。ABC C問題としては、難しい問題です。ひとつ上のD問題と比較できる難易度です。

解答案

問題を解く方針を書きだします。

  • 問題を読み込む。
  • 明らかに売る本を決める。
  • 小さい巻から読んでいく。
  • 足りない本を買う。
  • 売る本を補充する。
  • 売る本がなくなったら、それが解答になる。

もう少し手順を細かく決めていきましょう。

  • 明らかに売る本を決める。売る本の冊数は変数 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;
}

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」と判定されました。

最後に

丁寧に手順を実装していけば、解ける問題にもみえますが、完了している条件を正確に表現するのは、難しい問題と感じました。

D問題は、bit 全検索では明らかに無理な計算量となります。わたしが解説するには理解が浅い DP(動的計画法)を使う必要があるため、今回は、C問題までの解説としました。

引き続き ABC の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA