ABC278 C問題（FF）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）278 のC問題をC++とPythonで解いてみました。ABC278は、2022年11月19日21:00に実施されました。

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

C問題 FF（Difficulty : 327）

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

ABC278 C問題 FF

set を用いて要素を追加しながら、問われた要素が存在しているか確認していく問題です。AtCoder Problems による Difficulty は、327 でした。

解答案

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

• n と q を読み込む。
• 以下を q 回繰り返す。
  • t、a、b を読み込む。
    • t = 1 の場合、(a, b) を登録する。
    • t = 2 の場合、(a, b) を削除する。
    • t = 3 の場合、(a, b) と (b, a) が登録されていれば、”yes” を、それ以外の場合は、”No” を出力する。

C++ プログラム例（ABC278C）

set コンテナのちょうどよい演習と考えることができます。

• t = 1 の場合は、insert します。
• t = 2 の場合は、erase します。
• t = 3 の場合は、find で要素が存在しているか確認します。

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, q;
	cin >> n >> q;
	set<pair<int, int>> f;
	for (int i = 0; i < q; ++i) {
		int t, a, b;
		cin >> t >> a >> b;
		if (t == 1) {
			f.insert(make_pair(a, b));
		} else if (t == 2) {
			f.erase(make_pair(a, b));
		} else {
			if ((f.find(make_pair(a, b)) != f.end())
			  &&(f.find(make_pair(b, a)) != f.end())) {
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		}
	}

	return 0;
}

私は、set コンテナで要素が存在するか確認するときは、find を使っていますが、count を使っても同じ計算量で判断できます。具体的には、以下のように書きます。

if ((f.count(make_pair(a, b)) > 0)
  &&(f.count(make_pair(b, a)) > 0)) {

AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC278C）

Python も set があるため、同じように実装しますが、メソッド名は異なっています。

• t = 1 の場合は、add します。
• t = 2 の場合は、remove (discard) します。remove は、削除する要素がないとエラーを返します。入力例3をみると、この場合があるようなので、削除する要素がない場合も動作する discard を使います。
• t = 3 の場合は、in で要素が存在しているか確認します。

"""AtCoder Beginner Contest 278 C"""
n, q = map(int, input().split())
f = set()
for i in range(q):
    t, a, b = map(int, input().split())
    if t == 1:
        f.add((a, b))
    elif t == 2:
        f.discard((a, b))
    else:
        print("Yes" if (a, b) in f and (b, a) in f else "No")

こちらも「AC」と判定されました。

最後に

pair（タプル）を要素とする set コンテナを使う典型的な問題です。

C++ と Python で set の名前と機能は同じですが、メソッドが異なっています。複数の言語を使っていると、勘違いすることがあるかもしれません。

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