2018の競プロ反省と記憶に残るバグたち

2018年も終わるので,今年の反省など.

戦績

AtCoder

1853 -> 1823(season Highest 1949)

伸び悩み中.黄色になれないことは無いとは思うけど現実は無情である.

f:id:kuuso1:20181231100924p:plain

CodeForces

1870 -> 1918 (season Highest 1962)

今年は結構参加してた.Highestは更新してないけど紫にはちょくちょく戻ってた印象

f:id:kuuso1:20181231100943p:plain

TopCoder SRM

1365 -> 1464 (season Highest 1555)

今年は参加数が減ってる.Highestは更新してない.

f:id:kuuso1:20181231101011p:plain

TopCoder MM

1348 -> 1223 (season Highest 1408)

今年は頻繁に開催されてる割に5回しか出てなかった.時間とMP/HPが確保できなかったね.

f:id:kuuso1:20181231101024p:plain

2018にやってみていたこと

2017年の後半くらいから伸び悩み自体は感じていたので,今年はいろいろやってみようとは思ってました.

ACアカウントを作る.

コンテスト中やコンテスト後に解いた問題数を把握するのに,twitterでAC垢 @kuuso1ac を作って1月からつけてました.アイコンが本家よりかわいいの気に入っています. 効果があったかはわからないですが,反省用にあとから集計すると意外と面白かったので来年以降も続けようかな.

f:id:kuuso1:20181231121851p:plain

トータルで552問解いたようで,数字だけで言えば多くはないが少なくもないよねと言ったところ.簡単な問題も入ってるので次のレベルに上がるには質が足りてないという事かなという気はする.

過去問埋め

上のグラフから見えるように,AtCoderの過去問埋めをやってました.500以上を埋めるのと1月からはStreakキープにもトライ.実際には4月から異動でリアルの方に余裕がなくStreakは105で途切れ,500点以降の問題を中心に進める方についてはいったん500,600は埋めて700があと1/3程度,最近はまたちょっと忙しかったので十分には進められていないですね.もうちょっと何とかしたい.

あと一時twitterのTLで流行?した「いいねの数だけACする」というのもやってみていて(これ),これもまぁまぁ,解いただけツリーにぶら下がっていくのを見る楽しみはあると言えばありますね.ところで進捗どうですか?

反省は?

いろいろあるような気もしますが,伸び悩んでいるときに出るのはおおむね負の感情なので今年は結構つらかったなというのが正直なところ. 自分の思っている理想のラインと現実のギャップが埋まらないというのは往々にしてよくある話だし,それを埋めるためにはどうももうちょっと何かブレイクスルーが要るのかなぁと思ったりもする.がアイデアが「時間と量で殴る」ぐらいしか思いつかなくて,それも確保するのに難があって,行き詰っている感がありますね.MMなんかはそもそも時間確保できずしぬを繰り返しただけの感がある.

今年は上にも書いたように異動があって環境が落ち着かなかったというのももちろんあるとは思ってるんですがそれはさておき,競プロももう5年目だし実力が収束してくるのは仕方ないにしても,愉しみがレートにしか依存しない状況が続くと本来面白いからやっていたはずの趣味が苦痛でしかなくなってくるので,違う楽しみ方をみつけないとなという点が大きな課題.学生のようにICPCやJOI/IOIといった期限付きではないという点は社会人競プロの強みであり弱みであると思うので,特にその強みを生かす方向で解があるだろうとは思う.どうしてもつらいならやめればいいはずだし,他に趣味をみつけるのもいいはず.

(それらを見つけることを大きく阻害している原因の一つに,後から始めた人々に追い抜かれていくのがいまだに辛いという本質的なメンタルバグがあり,どうしても目の前のレートに喜怒哀楽がひきずられている)

話を変えて

あまりネガティブになってもしょうがないので,今年みつけた印象的なバグを4つほど紹介します.ほかの方の参考になる記事が書ければ,今年にも意味があったという気分になるね!

1. UnionFindでStack-overflowする話

まずはコード.C#です.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}

class Sol{
    public void Solve(){
        int N = (int) 3e5;
        var UF = new UnionFind(N);  // Nノードの Union Find のインスタンスを生成
        for(int i=0;i<N-1;i++){
            UF.Unite(i, i+1);    // 隣同士を連結していった
        }
        Console.WriteLine(UF.IsUnited(0, N-1)); // ここでRunTimeError
    }
}

class UnionFind{
    
    int[] parent;
    int N;
    public UnionFind(int n_){
        Initialize(n_);
    }
    
    public void Initialize(int n_){
        N = n_;
        parent = new int[N];
        for(int i=0;i<N;i++){
            parent[i] = i;
        }
    }
    
    public int Parent(int a){
        if(parent[a] == a) return a;
        return parent[a] = Parent(parent[a]);
    }
    
    public bool IsUnited(int a,int b){
        return Parent(a) == Parent(b);
    }
    
    public void Unite(int a,int b){
        a = Parent(a); b = Parent(b);
        if(a == b) return;
        parent[a] = b;
    }
    
}

RankをつかわないUnion Find(これとか)を使っていますが,上のようなシチュエーションでStack-overflowしましたね.今までもありそうなケースだったけど,Rankをつかっていないため再帰深度がO(N)になっていた.

f:id:kuuso1:20181231132514p:plain

みんなもRankを実装しましょう.(これ確かFHCかGCJだったかでローカルテストしていたので,その時はUnite部分で左右をランダマイズするという最悪をして逃げました)

2. CodeForcesでArray.Reverseが使えない

using System;

class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}

class Sol{
    public void Solve(){
        int[] A = new int[]{3,1,4,1,5,9,2,6,5,3,9,8,9,7,9};
        Console.WriteLine(String.Join(" ", A));
        
        Array.Sort(A);
        Console.WriteLine(String.Join(" ", A));
        
        Array.Reverse(A);  // ここでRunTimeErrorになる
        Console.WriteLine(String.Join(" ", A));
    }
}

Monoのバージョンの問題なのか,メソッドが見つからないというRunTimeErrorが投げられます. それコンパイル時に見つけてくれよ...Testcase2とかで見つけないでくれよ...頼むよ...

3. CodeForcesで特定の型のHashSetが使えない

using System;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;

class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}

class Sol{
    public void Solve(){
        
        //TestHashSet((bool) true);
        //TestHashSet((byte) 1);
        //TestHashSet((sbyte) 1);
        TestHashSet((char) 1);
        //TestHashSet((decimal) 1);
        //TestHashSet((double) 1);
        //TestHashSet((float) 1);
        TestHashSet((int) 1);
        TestHashSet((uint) 1);
        //TestHashSet((long) 1);
        TestHashSet((ulong) 1);
        //TestHashSet((short) 1);
        //TestHashSet((ushort) 1);
        //TestHashSet((System.Numerics.BigInteger) 1);
        
    }
    
    void TestHashSet<T> (T addedValue){
        HashSet<T> h = new HashSet<T>();
        try{
            h.Add(addedValue);   // ここでRuntimeErrorになる.
        } catch (Exception e){
            Console.WriteLine(e);
            Console.WriteLine("{0} NG", addedValue.GetType().Name);
            return;
        }
        Console.WriteLine("{0} OK", addedValue.GetType().Name);
    }
    
}

これもMonoのバージョンのせいかわからないですが,ある型のHashSetを作って,そこにその型の値(addedValue)をエントリーすると,型によって動いたり動かなかったりするバグです.

コメントアウトしてあるものが,正常に動かなかった型です.ほとんど動きませんね...(2018/12/31 カスタムテストで確認しました) 最悪なのが,インスタンスは確保できるのにAddしようとするとエラーになるところと,エラーがなんなのか例外に投げられないところです..

(例外キャッチしようとしても中身がなく,Runtime error: exit code is 13131313としか出ない). long (64bit整数)でも起きるのがとてもつらい.

ちなみにO(1) ハッシュをもつ辞書Dictionary<T,U> ではこの問題は起きないので,本番はそれに逃げました.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Numerics;

class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}

class Sol{
    public void Solve(){
        
        TestDictionary((bool) true);
        TestDictionary((byte) 1);
        TestDictionary((sbyte) 1);
        TestDictionary((char) 1);
        TestDictionary((decimal) 1);
        TestDictionary((double) 1);
        TestDictionary((float) 1);
        TestDictionary((int) 1);
        TestDictionary((uint) 1);
        TestDictionary((long) 1);
        TestDictionary((ulong) 1);
        TestDictionary((short) 1);
        TestDictionary((ushort) 1);
        TestDictionary((System.Numerics.BigInteger) 1);
        
    }
    
    void TestDictionary<T> (T addedValue){
        Dictionary<T, T> d = new Dictionary<T, T>();
        try{
            d.Add(addedValue, addedValue);
        } catch (Exception e){
            Console.WriteLine(e);
            Console.WriteLine("{0} NG", addedValue.GetType().Name);
            return;
        }
        Console.WriteLine("{0} OK", addedValue.GetType().Name);
    }
    
}

他のジャッジシステムでどうかは分からないですが,少なくともAtCoderTopCoderではArray.ReverseもHashSetも使えましたね.

4. next permutation

前述のArray.Reverseが使えないバグが発覚して,自分のライブラリにArray.Reverseつかってるやつがあるか調べていたら見つけたバグ(?).C#にはnext_permutationが無いので,自分で実装したものを長らく(4年以上)使っていましたが・・・

using System;
using System.Collections.Generic;

class TEST{
    static public bool NextPermutaion<T>(T[] A)where T:IComparable<T>{
        for(int i = A.Length - 2; i >= 0; i--){
            if(A[i].CompareTo(A[i+1]) < 0){
                int trgt = Array.FindLastIndex(A, x=>A[i].CompareTo(x) < 0);
                Swap(ref A[i], ref A[trgt]);
                Array.Reverse(A, i+1, A.Length - (i + 1));
                return true;
            }
        }
        Array.Reverse(A);
        return false;
    }
    static void Swap<T>(ref T x, ref T y){
        T t=x;x=y;y=t;
    }
    
    static void Main(){
        int[] A=new int[]{0,1,2};
        
        do {
            Console.WriteLine(String.Join(" ",A));
        } while(NextPermutaion(A));
        
        Console.WriteLine("last state:{0}",String.Join(" ",A));
    }
    
}

・・・NextPermutaion ってスペル間違ってるやんけorz...

(ちなみにNextPermutaionで検索すると結構いろんな人がtypoしてツイートしてましたね...)

終わりに

いろいろあるけど来年もgood luck, have funしたいね!