AtCoder

ABC278 C問題(FF)を解く

AtCoder_ABC278_C

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 でした。ABC C問題として、標準的な問題です。

解答案

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

  • 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 の名前と機能は同じですが、メソッドが異なっています。複数の言語を使っていると、勘違いすることがあるかもしれません。

ABC278 について、引き続き、D問題まで紹介します。

COMMENT

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

CAPTCHA