TopCoderで使用する言語をC++からC#に替えた時のメモ

背景

以前、TopCoderで使用するコンパイラのバージョンが上がりました。
http://apps.topcoder.com/forums/?module=Thread&threadID=792643で通知があり、実際のSRMで適用されたのは7/19からだったようです(https://twitter.com/rng_58/status/358179775543644160)。

この更新で、C#及びVBではコンパイラのバージョンが.NET Framework4.0になりました。
私は今まで競技プログラミングではC++を使っていましたが、次の理由からC#に替えてみることにしました。

• AOJやっている内にC++のSTLやの使い方を覚えたので、C#のコレクション関連もやってるうちに覚えられるだろう
• LINQでコレクションの操作が簡単に行える、begin()とend()の対を何度も書かずに済む
• C++だとテンプレの先頭に大量のinclude文(人によっては更にtypedefやマクロ)が必要になるがC#だと数個のusingで済む

単純にC#を触っていたい、というのが本音です。

作業内容

TopCoderではプラグインは、以前はmoj(http://apps.topcoder.com/forums/?module=Thread&threadID=597911&start=0)を使っていました。しかし、mojはC#に対応していないらしいので別のプラグインを導入することにしました。

Greedというプラグインがある、と以前聞いたことを思い出したのでそれを導入することにしました。
C#に対応しており、「テンプレート・テストコードの自動生成」「現在の提出スコアの表示」などの機能があります。
この記事の執筆地点では、Greed-1.5.jarが最新です。

Greedの導入及び設定

http://vexorian.blogspot.jp/2013/09/getting-started-with-topcoder-greed.html にアクセスし、.jarファイルを導入してArenaで設定します。
この段階で、ArenaでProblemを開くと"${WorkSpaceDir}/${ContestName}/${ProblemName}.cs"が自動生成されるはずです。

Greedのコンフィグ

Greedのコンフィグは、ワークスペースディレクトリにgreed.confを作成しそれを編集することで行います。
コンフィグによって、「テンプレートを生成するフォルダパス」「テンプレートの内容」などを変更できます。
Greedのjarファイルを解凍するとdefault.confやTemplate.csがあるので、それらをコピペしつつ編集すると簡単です。
詳しくは http://vexorian.blogspot.jp/2013/09/customizing-topcoder-greed-plugin.html を参照してください。

最後に、TopCoderのArenaの「Optionメニュー」→「Setup User Preferencesサブメニュー」で出てくるApplet Display Perefencesダイアログの「Editor」タブでDefault Langueageを変更して完了です。

現状の制約

• https://twitter.com/EmKjp/status/385208660005101569
• https://twitter.com/EmKjp/status/385383509574946817
• https://twitter.com/EmKjp/status/385384912984887296

で言及されているように、.NET Frameworkのいくつかのクラス/メソッドがProhibited Class/Methodと扱われ、コンパイルできません。
次のコードをArenaでコンパイルして確認しました。コメントアウトしている箇所がProhibited Class/Methodと扱われる箇所です。

public class LittleElephantAndBooks {
    // IEnumerable CountUp(){ for(int i=0; ; ++i) yield return i; }
    public int getNumber(int[] pages, int number) {
        // var t1 = Tuple.Create(1);
        // var t2 = Tuple.Create(1, "abc");
        // var t3 = Tuple.Create(1, "abc", 0.0);

        var list = Enumerable.Range(0,100);
        // var lookup = list.ToLookup(a=>a);
        // var groupby = list.GroupBy(a=>a);

        // Action a0 = ()=>{};
        Action<int> a1 = (a)=>{};
        // Action<int,int> a2 = (a,b)=>{};
        Predicate<int> p1 = (a)=>true;
        Func<int> f0 = ()=>0;
        Func<int,int> f1 = (a)=>0;
        Func<int,int,int> f2 = (a,b)=>0;
        return 0;
    }
}

ライブラリの追加

C++には標準で存在しますがC#には存在しないものに、next_permutationやpriority_queueがあります。
実装してテストしてライブラリとして持っておきましょう。

その際、http://ksksts.blogspot.jp/2009/11/list-ilist-dont-use-ilist-s-indexer.htmlで言及されているように、IListで実装するのではなく、TとListでオーバーロードして実装したほうが良いでしょう。
要素数10,000のint配列arrに対してarr[i]=i*iする処理で確かめた所、intのまま処理する場合とIListにキャストした後処理する場合で10倍以上の速度差がありました。

余談

C#のpropertyはrefで取れないため、万能なSwapを実装することが出来ません。
C++のマクロ/テンプレートの強力さが身にしみます。