問題を読んで、最初は二分探索木を実装しようかと思ったのですが、問題データを見ると、そのまま実装するとバランスが悪くなりそうだったので、平衡二分探索木よりも実装が簡単そうなスキップリストを利用してみました。ひとつのノードを表すことができないため、データ構造としては非効率な方法になってしまいました。テストデータを使って計算したところ、今回書いたプログラムよりも、単純に連想配列を用いて計算した場合のほうが数十倍も速いことがわかりましたが、単純な連結リストに比べれば十分な速度が得られました。データ構造について制約があるという環境でのプログラムはあまり書いたことがなかったため、新鮮な感じがしました。データがちゃんと連結されているかどうか不安があったので一通りのテストも書きました。iimurae-mail。