TopCoder Marathon Match Local Tester

Marathon Matchのローカルテスターを作った。

TopCoderのサーバーでテストすることは出来るのだが、

• 2時間に1回しかサーバーでテストできない。（Example testの場合は、15分に1回）
• queueに人が溜まっていると待たないといけない
• 採点されるテストケースは、Full Submit Testのテストケースより多い

の理由からローカルで自動テストスクリプトを作って走らせる人が多いようだ。

昨年のTCOで作ったはずだが、どこかに行ってしまったので今日作った。今度はどこかに行ってしまわないようにブログにあげておく。

テストを走らせる処理は、windowsのバッチスクリプト

テスト結果のパースはperlで書きました。

ローカルマシンよりTopcoderサーバーの方が断然早いのでTime Limitについては何らかの補正が必要か？？

@ECHO OFF

echo System Test Starts..

:: set variables
SET MAX_SEED=100
SET SEED=0
SET OUTPUT=%1.txt

:: solve problems
:LOOP
echo Solving #%SEED% ....
IF %SEED%==0 echo SEED = %SEED% > %OUTPUT%
IF NOT %SEED%==0 echo SEED = %SEED% >> %OUTPUT%

java -jar hogehogeVis.jar -exec "hogehoge.exe" -seed %SEED% -novis >> %OUTPUT%

SET /A SEED=%SEED%+1
IF %SEED%==%MAX_SEED% GOTO LOOPEND
GOTO LOOP

:LOOPEND
echo System Test Ends!
echo -----------------------
echo [Overall Result]
perl parse.pl %1

open(INPUT, "<" . $ARGV[0] . ".txt");

@list = <INPUT>;

$pointSum = 0;
$timeOver = 0;

foreach $line( @list ) {
    if ($line =~ /(^Time)/) {
        $line =~ /([0-9\.]+)/;
        $time = $1;
        if ($time > 10) {
            $timeOver++ ;
        }
    }
    elsif ($line =~ /^Score/) {
        $line =~ /([0-9\.]+)/;
        $point = $1;
       
        $pointSum += $point
    }
}

print "Point: " . $pointSum . "\n";
print "Time Over: " . $timeOver . "\n";

MAX_SEEDは、TopCoder上のFull Submissionでは100、System Testでは1000くらいだと思う。

Haskell勉強記（5）

またまたまたHaskell。

今日はモナドについて書こうと思う。

1. モナドの概念
2. 物理的には（実体は）何なの？
3. 代表的なモナド

という切り口でモナドについてまとめてみる。

モナドの概念

　モナドでやりたいことは、”複数の演算をつなぐこと”である。具体的には、

• まず○○をして、そのあと××をしたい。（処理の順序付けをする）
• ○○をして、失敗したら××はしない。（Cのforループのbreakのような処理）

とかである。

　”参照透過性を保ちつつ、副作用を導入する”のがモナドという内容をよく見るが、これはモナドの概念とは異なる。上記は、IOモナドの機能であって、一般的なモナドの機能ではない。

物理的には（実体は）何なの？

　モナドとは、モナド型クラスのインスタンスである。モナド型クラスは、

• return
• >>=

のクラスメソッドをもっていて、この２つの演算は”モナド則”を満たす。

つまり、return、>>=が実装されていて、その実装がモナド則と呼ばれる法則を見てしていれば、それはモナド。

　難しい話は置いといて、モナドは一言でいうと”モナド型クラスが持つ機能を実装した型”のこと。

　演算子（>>=）の型は以下のとおり。

>>= :: m a -> (a -> m b) -> m b

①モナドの型に入ったaが与えられる。

②そこから、aを取り出して、aをbに変換。モナドで包む。

というイメージ。これは、入れ子のalistに対して関数lookupを適用する例を見ると分かりやすい。

代表的なモナド

　以下に代表的なモナドをあげる。

• Maybeモナド
• IOモナド
• リストモナド

　Maybeは、alistの検索など、データが存在するか、存在しないか分からない処理を格納する。

　IOは、putStrとかgetContentsとか。アクションとは、IOモナドの別名らしい。参照透明性を確保しつつ、副作用を持たせたい場合は、IOモナドが使われます。標準入出力の他にも乱数とかシステム日時取得など。

　リストモナドは、リストを扱うためのモナド。リストモナドの目的は、”適用するたびに値の数が増減する関数を連結すること。”

参考文献に分かりやすいサンプルコードがたくさん載ってるので、「モナドって何？」ていう最低レベルのことは理解できると思います。

参考文献：

『ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門』

memset()の有効活用

前にも書いたが、memset()は初期化時に重宝する。

今日、ある問題を解いていたときに、3次元配列の初期化に遭遇した。

しかも、0ではなく、INF（比較的大きな数字）に初期化したい。

どうしたものか。。

　まず、やったのが、fill()。

int main() {
 int x[10][10][10];

 fill(x, x+10, INF);
 cout << x[0][0][0] << endl;
}

ダメだった。なぜ。。3次元だけど、メモリは縦に連続して展開されるんじゃないの？？

同様にfill_n()も撃沈。

int main() {
  int x[10][10][10];

  fill_n(x, 10*10*10, INF);
  cout << x[0][0][0] << endl;
}

ま、マジか。。。

　仕方ないので、愚直にループを書く。

int main() {
 int x[10][10][10];

 REP(i, 10) REP(j, 10) REP(k, 10) x[i][j][k] = INF;
 cout << x[0][0][0] << endl;
}

んー、ちょっとダサいなー。

ちょっと考えてmemset()で行けるのではと気付く。

memset()は2進数・byte単位で初期化するので、大きな数にセットしようとして、

int main() {
  int x[10][10][10];

  memset(x, 0xFF, sizeof(x));
  cout << x[0][0][0] << endl;
}

とするのはNG。これでは、すべての要素が-1にセットされます。（2の補数ですね。）

大きい数なら、0x7Fがいいでしょう。

しかし、INF + INF < INT_MAX（アルゴリズムコンテストの問題を解いていると、こういう条件を満たしたいことがしばしばありますよね！）を満たす範囲でなるべく大きいINFにセットしたい場合は、

0x3Fが妥当でしょう。

int main() {
   int x[10][10][10];

   memset(x, 0x3F, sizeof(x));
   cout << x[0][0][0] << endl;
}

ちなみに、上記の値は、十進数で”1061109567”です。

Haskell勉強記（4）

またまたHaskell。

今日のテーマは以下。

1. guard
2. case expression

これが使えれば、それっぽいHaskellのコードが書ける（気がする。）

まずは、guardから。

guardは、パターンマッチに似ていますが、パターンマッチとは異なり任意の形で関数のマッチングができます。以下にguardを利用したfizz buzzを書きます。

main = putStr $ unlines $ map fizzBuzz [1..100]
        where fizzBuzz x
                   | x `mod` 3 == 0 && x `mod` 5 == 0 = "fizz buzz"
                   | x `mod` 3 == 0                   = "fizz"
                   | x `mod` 5 == 0                   = "buzz"
                   | otherwise                           = show x

|と=の間がguardです。ここに条件式を書きます。上から順に操作され、trueとなったら式が対応する評価されます。otherwiseは、Preludeで定義されている式で、その値Trueだそうです。

次にcase expression。guardを使うと任意の式でパターンマッチができますが、引数に対する条件式（上の場合はx）に対する条件式しか書けません。

case expressionを使用すると、引数を成形したものに対してマッチングをかけることができます。fizz buzzを書くと下のようになります。

main = putStr $ unlines $ map fizzBuzz [1..100]
        where fizzBuzz x = case [x `mod` 3, x `mod` 5] of
                            [0, 0]      -> "fizz buzz"
                            [0, _]    -> "fizz"
                            [_, 0]    -> "buzz"
                            otherwise -> show x

最後に、以上をふまえて、3の倍数と3が付く数字のときだけアホになる関数を書きましょう。

main = putStr $ unlines $ map nabeatsu [1 .. 100]
        where  hasThree x = any (== '3') $ show x
               nabeatsu x
                | x `mod` 3 == 0     = "aho" ++ " (" ++ (show x) ++ ")"
                | hasThree x         = "aho" ++ " (" ++ (show x) ++ ")"
                | otherwise            = show x

今日はここまで。

SRM 503（div2） 参戦記

[結果]

Easy ：　やるだけ。

Middle: 頭の柔らかさが必要な問題。greedyかDPだろって思いこんで突き進んだ結果解けず。

Hard : MST。やるだけ。本番は開かず。。。

[反省]

1. 固定概念は捨てる。greedyかDPだろって思いこんだのが敗因。
2. 全体像を考える前に、まず例外パターンは捨てる。middleでいきなり汎用的な解法を考えようとしたが、例外パターン（-1となるパターン）を始めに切り捨てておけば、それ以外の答えが{1, 2}のどちらかしかないというのに気付けたはず。プログラムで深いネストをしないためには、例外を一番最初にcontinueすればいいが、同じようにアルゴリズムを考える上でも例外は最初に排除すべき。例外を排除することで見えてくる規則性があるのだから。
3. 次回からはHardも開くようにしよう。今回みたいに簡単な問題もあるので。。

[Rating]

1088 -> 1061

次回こそdiv1に返り咲く！うまく行かなかった回からは学ぶべきものが多いはずなので、しっかり分析して次に活かす。後はひたすら練習。

Haskell勉強記（3）

またまたHaskell。書きすぎ！？

今日は、

1. function composition
2. where clause
3. cons

について。

　function compositionは、その名のとおり合成関数です。f, g, hという関数がある場合、

　　　　f (g(h(x)))

は、Haskellでは、

　　　　f $ g $ h x

と書けます。また、function compositionを使用すれば、

(f . g . h ) x

と書けます。使いどころとしては、mapの第一引数に合成関数を使用したい場合でしょう。

　次にwhere 節について。where節は、関数の中で有効なローカル変数、関数を定義します。

以上をふまえて、まず、sin (x^2)を計算するプログラムを書きます。

main = print $ map (sin . sq) [1..10]
      where sq x = x * x

まあ、そのままですね。。

最後に、consについて。consは":"（コロン）のことです。パターンマッチの説明のときに出てきました。

a : x

とすると、要素aをリストxの先頭に追加することができます。

例えば、リスト[1,2,3,4,5]は、

　1:2:3:4:5:[]

と書けるわけです。（最後に[]が必要なことに注意！）

では、最後に自前のzip関数を定義してみます。奇数リストと偶数リストを生成してzipしてみましょう。

main = print $ myZip [1, 3 .. 10] [2,4 .. 10]
     where myZip         [] [] = []
           myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

今日はここまで。

Haskell勉強記（2）

今日もHaskell。

今日は、昨日の復習とlambda expressionについて。

まず、昨日の復習として、

• map
• filter
• reduce

を自分で実装してみます。これを実現するためには、

1. Pattern match
2. tuple

を使えばいいです。

myReduce     f [] = 0
myReduce f (x:xs) = f x (myReduce f xs)

myMap f []     = []
myMap f (x:xs) = [f x] ++ (myMap f xs)

myFilter f []    = []
myFilter f (x:xs) = if f x
                   then [x] ++ (myFilter f xs)
                   else myFilter f xs

まぁこんな感じでしょう。

そして、上記自前関数の引数にlambda式を使ってみましょう。

Haskellでは、lambda expressionは"\"(バックスラッシュ)と"->"(ハイフンと大なり記号)を用いて表されます。

a = [1 .. 10]
main = do print $ myMap (\x -> x*x) a
         print $ myFilter (\x -> x `mod` 2 /= 0) a
         print $ myReduce (\x y -> x+y) a

なんか、意味不明な記号が多くて若干pe○lみたいで嫌ですが。。

今日はここまで。