ABC226参加しました。

C#の場合, Math.Round( X )と書くとWAとなると思います。
これは、Math.Round(X)だと、Math.Round(X, MidpointRounding.ToEven)の指定となり、これは「直感的な四捨五入」とは異なり、「最も近い偶数への丸め」となります。この方が誤差は少ない丸めになるそうですが、この問題では不適切な答えが返る場合があります。

具体的には、 Math.Round(X, MidpointRounding.ToEven)だと
3.75 => 3.8
3.85 => 3.8
へと丸められます。

より直感的な丸めには、Math.Round(X, MidpointRounding.AwayFromZero)としてあげればいいです。

qiita.com

docs.microsoft.com

B - Counting Arrays

解説 - AtCoder Beginner Contest 226

提出 #27116805 - AtCoder Beginner Contest 226

愚直にやると各行に対して、同一の行があるかどうかを毎回チェックしないといけないので、TLEします。各行をHashsetに突っ込んでしまえば、同じ行はHashsetに突っ込む段階で消えてくれます。

なお、注意点として、自作のScannerクラスなどで空白単位で各数値を読み取ってHashsetに入れていると、
"1 21"
"12 1"
みたいな入力が来たとき、同じ文字列("121")と扱われるので、区切り文字も含めてHashsetに入れる必要があります。なので、一行まとめて、空白も気にせず読み込んでしまえばいいです。

ここからC#の話。というか自分用のC#覚書。コンテスト中は、string型のHash値がstringオブジェクトの参照から計算されるんじゃないかと、うっかり思っていたのですが、違いました。

ここでHash値を計算するGetHashCode()について、参照型(string型以外)とstring型でまとめてみます。

オブジェクトのGetHashCode()で求めた値がHash値としてDictionalyやHashsetで使われます。
参照型の場合、GetHashCode()の結果は(派生クラスでオーバーライドしてない限りは)、オブジェクトの参照情報から計算されます。

docs.microsoft.com

ただしstring型は参照型ですが、ちょっと特殊で、参照が違っても文字列が同じなら、Hash値は一致します。

docs.microsoft.com

まあ、文字列が一致しているかを==で見ることが殆どで、そんなときに参照を見られても困りますからね。

実験してみました。参照も同じで、文字列も一致している場合(s1,s2)は当然trueですが、参照が違っていても、文字列が一致している場合(s1, s3)でもtrueになることがわかります。

var s1 = "ABC";
var s2 = s2;
var c = new char[]{'A', 'B', 'C'};
var s3 = new string(c);
Console.WriteLine($"s1 : {s1}");
Console.WriteLine($"s2 : {s2}");
Console.WriteLine($"s3 : {s3}");

Console.WriteLine($"s1 == s2 : {s1 == s2}");
Console.WriteLine($"s1 == s3 : {s1 == s3}");
Console.WriteLine($"Object.ReferenceEquals(s1, s2) : {Object.ReferenceEquals(s1, s2)}");
Console.WriteLine($"Object.ReferenceEquals(s1, s3) : {Object.ReferenceEquals(s1, s3)}");

Console.WriteLine($"s1.GetHashCode() : {s1.GetHashCode()}");
Console.WriteLine($"s2.GetHashCode() : {s2.GetHashCode()}");
Console.WriteLine($"s3.GetHashCode() : {s3.GetHashCode()}");

// 結果
// s1 : ABC
// s2 : ABC
// s3 : ABC
// s1 == s2 : True
// s1 == s3 : True
// Object.ReferenceEquals(s1, s2) : True
// Object.ReferenceEquals(s1, s3) : False
//s1.GetHashCode() : 1343675547
//s2.GetHashCode() : 1343675547
//s3.GetHashCode() : 1343675547

よって、string型に対しては、参照が違っても文字列が同じなら同じHash値が得られます。
(ただし、Hash値が同じなら同じ文字列とは限らない)

結論から言えば、何も考えずにHashSetに入力の各行を入れていればいい問題でした。いちいちstring型のGetHashCode()をオーバーライドしなくてもよかったわけですね。

なお、2つのstringオブジェクトが一致しているかの内部処理は以下の通り(参考)

        // Determines whether two strings match.
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
        public override bool Equals(Object obj) {
            if (this == null)                        //this is necessary to guard against reverse-pinvokes and
                throw new NullReferenceException();  //other callers who do not use the callvirt instruction
 
            String str = obj as String;
            if (str == null)
                return false;
 
            if (Object.ReferenceEquals(this, obj))
                return true;
 
            if (this.Length != str.Length)
                return false;
 
            return EqualsHelper(this, str);
        }
        // Determines whether two strings match.
        [Pure]
        [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
        public bool Equals(String value) {
            if (this == null)                        //this is necessary to guard against reverse-pinvokes and
                throw new NullReferenceException();  //other callers who do not use the callvirt instruction
 
            if (value == null)
                return false;
 
            if (Object.ReferenceEquals(this, value))
                return true;
            
            if (this.Length != value.Length)
                return false;
 
            return EqualsHelper(this, value);
        }

EqualsHelper()で、文字列の内部の文字が一致しているかを見ています。

感想

久々に参戦したら、爆死してしまった... Bって計算量を意識させるレベルの問題が出る難易度帯だったかな... あと、C#の曖昧だった部分を突かれまくった気がする。

umem0chiの日記

AtCoder ABC226

A - Round decimals

B - Counting Arrays

感想