たくあんポリポリ

勉強したことを載せていきます。( 主に、C#/ Algorithm / AtCoder / Unity / 最近はKaggleとPython )

【AtCoder】【C#】文字列ソートでパフォーマンスが出ない時の対応

f:id:c_taquna:20200115005201p:plain

AtCoder Beginner Contest 155 のC問題でTLEがどうしても解決できず、終了後に文字列ソートの方法を変えれば通ることがわかったので、メモを残します。

はじめに

本記事のテーマ

下記問題をC#で解こうとするとちょっと工夫をしないとTLEになってしまいます。これを解決する方法について書きます。

atcoder.jp

本題

問題概要

  • N枚目の上には文字列Sが書かれている
  • 最も多く書かれた文字列を辞書順で出力する

今回の実装方針

  1. Dictionaryで文字列と出現回数をまとめる
  2. 出現回数が最大となる値を求める
  3. 出現回数が最大となる文字列をListに格納(Add)
  4. ListをArrayに変えてSortする(Sortする時に、Sort関数の第二引数にStringComparer.OrdinalIgnoreCaseを指定する)

解説

今回ポイントになるのは、4.です。結論からいうと、下記のように実装しなければ通りません。

Array.Sort(array, StringComparer.OrdinalIgnoreCase);

おそらく、通常は下記のように実装すると思います。ただ、これだとTLEしてしまいます。

Array.Sort(array);

これはなぜかというと、Microsoftのベストプラクティスにも記載があるように、StringComparer.OrdinalIgnoreCaseをつけることでカルチャ(ロケール)に依存した処理にならずパフォーマンスが向上しているとのことです。

今回はこの実装が必須でした。

docs.microsoft.com

実装全体は下記です。

実装リンク AtCoder/C.cs at master · chittai/AtCoder · GitHub

感想

非常に悔しいし悲しいのですが、この学びを活かして次につなげたいですね