データ構造ってとても大事・・・・

先日開催された日本レジストリサービス（JPRS）プログラミングコンテスト2025#1（AtCoder Beginner Contest 392)にバーチャル参加しました。
C問題で問題文を理解するのに時間がかかってしまいました.....。10分くらい考えた後に、「こうなれば簡単に実装できるのになぁ」というデータ構造の形を見つけて実装を行ったのですがTLEになってしまいました。
計算量を見積もる癖は最近出来てきたところだったので、なぜTLEになってしまったのか少し疑問だったのですがよく調べてみると答えが分かりました。

SortedList<int, int> bibHolder = new SortedList<int, int>();

私が使用したのはSortedListです。
SortedListは内部で配列を使用し、データを管理しています。そのため、データを挿入したり削除したりするときは内部の配列の要素をシフトする必要があり、この操作には最悪O(n)の計算量が必要とのことでした。
今回の問題では、最初にこのようなSortedListを定義してしまうと、その後にn回データを挿入しなければならないのでO(n ^2 )になってしまい、TLEということですね。

これに対して、以下のようにデータ構造を定義するとTLEを回避できました。

SortedDictionary<int, int> bibHolder = new SortedDictionary<int, int>();

SortedDictionaryです。
こちらでは二分探索木を用いてデータを管理しています。SortedDictionaryではキーを指定しての検索・挿入・削除はすべて O(log n) の時間計算量で実現されるため、今回のような問題ではn回のデータの挿入を行っても、O(nlogn)となってTLEにならずに実行できたというわけですね。

例えば最初に一気に配列に入れてしまった後にその配列をソートすればListでもTLEにはなりませんし、私のコードが少し特殊だったのかなと思いますが、計算量の見積もりをする時は単にfor文を見るだけではだめだという事を痛感しました。データ構造だけで正解か不正解が変わってしまう競プロの世界面白い・・・！

プログラミングにおいて「型」は常に意識しなければなりません。
今回のABCでは、用途に応じてどのようなデータ構造を使用するかを取捨選択しなければならないと改めて再認識できました。