AtCoder Beginner Contest 187 C - 1-SAT

最近こたつでよく寝落ちをしてしまいます、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc187/tasks/abc187_c)にて開催されました、AtCoder Beginner Contest 187 C問題「C - 1-SAT」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

N 個の文字列 S 1 , S 2 , … , S N が与えられます。 各文字列は、英小文字からなる空でない文字列の先頭に ! を 0 文字か 1 文字付加したものです。 文字列 T は、 T の先頭に ! を 0 文字付加しても 1 文字付加しても S 1 , S 2 , … , S N のいずれかに一致するとき、不満な文字列であるといいます。 不満な文字列があるかどうか判定し、あれば 1 つ示してください。

2.制約

• 1≤N≤2×10⁵
• 1≤|Si|≤10
• Siは英小文字からなる空でない文字列の先頭に ! を 0文字か 1文字付加したものである。

3.入出力例

• 入力

6
a
!a
b
!c
d
!d

• 出力

a

文字列 a は、先頭に ! を 0 文字付加する場合は S 1 と、 1 文字付加する場合は S 2 と一致するため不満な文字列です。 a の他に、d を出力しても正解になります。

4.初見の感想

• 単純にループを回して各要素を比較する解法でも解けそう

5.学びポイント

• HashSetを利用するとContainsで存在するかを確認できるから便利です

6.コードと簡単な解説

using System;
using System.Collections.Generic;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            HashSet<String> hs = new HashSet<String>();
            for(int i=0;i<N;i++){
                hs.Add(Console.ReadLine());
            }
            foreach(var x in hs){
                if(hs.Contains("!"+x)){Console.WriteLine(x);return;}
            }
          Console.WriteLine("satisfiable");
        }
    }
}

7.最後に

HashSetの使い方を復習できたのでよかったです！