Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-05-09

Google Code Jam 2010 Qualification Round

| 18:37 | はてなブックマーク -  Google Code Jam 2010 Qualification Round - cafelier@SRM

スコア・ソース (ID は kinaba) はこちら。AC/AC/AC/RE/AC/AC : かっこわる…

  • さすがにQualification Roundはいくら遊んでも落ちないだろう…
  • ということで、全部違う言語で解く遊びをしていました。
  • 今年のテーマは
    • 「A-Small を .as、B-Small を .bs、… C-Large を .cl という拡張子の言語で解く」
  • と思ったんですけど、全部はみつからなかったのでところどころ妥協しました。

  • どの言語も書き慣れてないので変なところがあると思います。
  • 「この言語なら普通はこう書くよ」的突っ込み大歓迎


C-Small .cs C#

  • 紹介する必要もないと思いますが C# です。

  • 愚直に1つ1つシミュレーションする。
  • 何かC#っぽいことしなくちゃ、と思って意味もなくLINQを使ってみたけど本当意味ないな…
using System;
using System.Linq;

class C
{
   static void Main()
   {
      long[] Ts = readLongArray();
      long   T  = Ts[0];

      for(long C=1; C<=T; ++C)
      {
         long[] RkN = readLongArray();
         long   R = RkN[0];
         long   k = RkN[1];
         long   N = RkN[2];
         long[] g = readLongArray();

         Console.WriteLine("Case #{0}: {1}", C, solveSmall(R,k,N,g));
      }
   }

   static long[] readLongArray()
   {
      return (from s in Console.ReadLine().Split(' ') select long.Parse(s)).ToArray();
   }

   static long solveSmall(long R, long k, long N, long[] g)
   {
      long totalEarn = 0;

      for(int i=0; i<R; ++i)
      {
         long ride = 0;
         for(int q=0; q<g.Length; ++q)
            if( ride + g[q] > k )
            {
               g = rotate(g, q);
               break;
            }
            else
            {
               ride += g[q];
            }
         totalEarn += ride;
      }

      return totalEarn;
   }

   static long[] rotate(long[] g, int s)
   {
      long[] g2 = new long[g.Length];
      for(int i=s; i<g.Length; ++i)
         g2[i-s] = g[i];
      for(int i=0; i<s; ++i)
         g2[i+g.Length-s] = g[i];
      return g2;
   }
}

C-Large .cl Claire

  • Claire
  • などが目立つところですが、いたって普通のコードしか出番がありませんでした…

  • どのグループから始まったら(どのグループまで乗れる&何人乗れる)の情報を最初に前計算しておく
  • あとは愚直にシミュレーションなんだけど状態がループしたらループをすっ飛ばす

  • それだけかと思いきや、
  • この言語には30bit整数(実装は32bitだけど下2bitをフラグに使うとかだと思う)と64bit浮動小数点数しかない
  • ので、64bit整数が必要なこの問題では
  • それを自分で実装しなければ…
    • そもそも30bit整数を使って簡単に実装できるのは58bitまでのような
    • 足りるか?足りるか。よし。

  • しかし結構こういう(intとdoubleしかない)言語って多いんじゃないかと思うんですけど、Bのbigint問題以前にlong long前提って時点で結構言語を選ぶよな…
D :: 1000000000

long <: ephemeral_object(hi:integer, lo:integer)

[long!(x: integer) : long ->
   long(hi = x / D, lo = x mod D)
]

[+(x:long, y:long) : long ->
   let lolo := x.lo - D + y.lo in
   (
      if ( lolo < 0 )
         long(hi = x.hi + y.hi,     lo = lolo + D)
      else
         long(hi = x.hi + y.hi + 1, lo = lolo)
   )
]

[-(x:long, y:long) : long ->
   let lolo := x.lo - y.lo in
   (
      if ( lolo < 0 )
         long(hi = x.hi - y.hi - 1, lo = lolo + D)
      else
         long(hi = x.hi - y.hi,     lo = lolo)
   )
]

[*(x:long, y:integer) : long ->
   let r := long!(0) in
   let c := x in
      (while (y > 0) (
         (if (y mod 2 = 1) r :+ c),
         c := c + c,
         y :/ 2
      ),
      r)
]

[+(x:long, y:integer) : long ->
   x + long!(y)
]

[<(x:long, y:long) : boolean ->
   if (x.hi < y.hi)
      true
   else if (x.hi > y.hi)
      false
   else
      x.lo < y.lo
]
[>=(x:long, y:long) : boolean -> not(x < y)]
[<=(x:long, y:long) : boolean -> not(y < x)]
[>(x:long, y:long) : boolean -> (y < x)]

[>=(x:long, y:integer) : boolean -> not(x < long!(y))]
[<=(x:long, y:integer) : boolean -> not(long!(y) < x)]
[<(x:long, y:integer) : boolean -> (x < long!(y))]
[>(x:long, y:integer) : boolean -> (long!(y) < x)]

[>=(x:integer, y:long) : boolean -> not(long!(x) < y)]
[<=(x:integer, y:long) : boolean -> not(y < long!(x))]
[<(x:integer, y:long) : boolean -> (long!(x) < y)]
[>(x:integer, y:long) : boolean -> (y < long!(x))]


[string!(x: long) : string ->
   if (x.hi > 0)
      let los := string!(x.lo) in
         string!(x.hi) /+ make_string(9 - length(los), '0') /+ los
   else
      string!(x.lo)
]

/////////////////////////////////////////////////////////////////////////////

[readLine() : list<integer> ->
   list<integer>{integer!(s) | s in explode(freadline(stdin), " ")}
]

[solve(R:integer, k:integer, N:integer, g:list<integer>) ->
   let dest := make_list(N, 0) in
   let earn := make_list(N, long!(0)) in
   (
      for s in (0 .. N - 1) (
         let ride := long!(0) in
         let i    := 0        in
         (
            while (i < N)
            (
               let ride2 := ride + g[((s + i) mod N) + 1] in
               (if (ride2 > k)
                  break()
               else
                  (ride := ride2, i :+ 1))
            ),
            earn[s + 1] := ride,
            dest[s + 1] := ((s + i) mod N) + 1
         )
      ),
      let firstVisitTime := make_list(N,       -1) in
      let firstVisitEarn := make_list(N, long!(0)) in
      let q         := 1        in
      let totalEarn := long!(0) in
      let i         := 0        in
      (
         (while (i < R) (
            if (firstVisitTime[q] = -1)
            (
               firstVisitTime[q] := i,
               firstVisitEarn[q] := totalEarn,
               totalEarn         :+ earn[q],
               q                 := dest[q],
               i                 :+ 1
            )
            else
            (
               let loopSize := i - firstVisitTime[q] in
               let loopEarn := totalEarn - firstVisitEarn[q] in
               let rest     := R - i in
               (
                  totalEarn :+ loopEarn * (rest / loopSize),
                  // clear
                  firstVisitTime := make_list(N, -1),
                  i              := R - (rest mod loopSize)
               )
            )
         )),
         princ(string!(totalEarn))
      )
   )
]

[main() ->
   let T := readLine()[1] in
      for C in (1 .. T)
      (
         printf("Case #~A: ", C),
         let RkN := readLine() in solve(RkN[1], RkN[2], RkN[3], readLine()),
         princ("\n")
      )
]

(main())
  • 「型=値の集合」的発想に基づいて、デフォルトでは「型を指定するとその型のオブジェクト全部を取ってくる」機能があって、これがあると作ったオブジェクトがいつまでも生存し続けるので "ephemeral_object" クラスを継承してこの機能を切らないと大変なことになるのでそうした、という辺りだけ Claire 独特かも。

B-Small .vbs VBScript

  • .bs の言語が見つかりませんでした。
  • Bjarne Stroustrup 言語こと C++ というネタもありだった

  • 最大公約数を求めるだけの問題
  • 負の数がでないように最初に入力をソートしておこう…
  • と思ってググったら「VBScriptに標準のソート関数はありません」って記事ばっかりひっかかるんだけどマジですか
Function ReadLine()
   Dim s
   s = Split(WScript.StdIn.ReadLine, " ")
   For i = LBound(s) To UBound(s)
      s(i) = CLng(s(i))
   Next
   ReadLine = s
End Function

Function Gcd(a, b)
   If a = 0 Then
      Gcd = b
   Else
      Gcd = Gcd(b mod a, a)
   End If
End Function

Function Solve(T)
   Dim g, r
   g = Abs(T(1) - T(2))
   For i = 2 To UBound(T)
      g = Gcd(g, Abs(T(1) - T(i)))
   Next
   r = T(1) mod g
   If r = 0 Then
      Solve = 0
   Else
      Solve = g - r
   End If
End Function

C = ReadLine()(0)
For CaseID = 1 To C
   WScript.StdOut.WriteLine "Case #" & CaseID & ": " & Solve(ReadLine)
Next

B-Large : .bl : Blue


  • Largeは単に64bit整数でもあふれるくらい数が大きいだけなので、bigint を使えばよいのです
  • が…
  • そんなものはない。

  • 仕方ない、実装するか…
  • 足し算引き算掛け算まではいいけど、割り算というかmodの実装って結構めんどくないか…?
  • 再帰と足し算と大小比較を使って…
  • x % y =
    • if x < y then x else
    • let z = x % (y+y) in
      • if z < y then z else z-y
  • あ、結構綺麗にできた。
  • 計算量的に最適ではないだろうけど、便利だ。これは覚えておこう。収穫収穫。
global FROM_STRING = func {
   arg s;

   a = [];
   i = 0;
   loop {
      a = a.append( s.substr(i,i+1).num() );
      (i=i+1) >= s.length() ? return;
   };
   return a;
};

global TO_STRING = func {
   arg x;
   lexical s = "";
   x.map( func{ s = s + this; } );
   return s;
};

global LESS = func {
   arg x;
   arg y;

   xl = x.length();
   yl = y.length();
   (xl < yl) ? return 1;
   (xl > yl) ? return 0;
   i = 0;
   return loop {
      (i == xl)     ? return 0;
      (x[i] < y[i]) ? return 1;
      (x[i] > y[i]) ? return 0;
      i = i+1;
   };
};

global SUB = func {
   arg x;
   arg y;

   x.length() > y.length() ? (y = [].resize(x.length()-y.length(),0).merge(y));
   z = [].resize(x.length(), 0);
   i = x.length()-1;
   carry = 0;
   loop {
      z[i]  = x[i] - y[i] - carry;
      carry = z[i] < 0 ? (z[i]=z[i]+10; 1) : 0;
      (i=i-1) < 0 ? return;
   };
   head = 0;
   loop {
      head == z.length()-1 ? return;
      z[head] != 0 ? return;
      head = head + 1;
   };
   return z.slice(head, z.length());
};

global DBL = func {
   arg x;

   z = [].resize(x.length(), 0);
   i = x.length()-1;
   carry = 0;
   loop {
      z[i]  = x[i] + x[i] + carry;
      carry = z[i] > 9 ? (z[i]=z[i]-10; 1) : 0;
      ((i=i-1) < 0) ? return;
   };
   return (carry==1 ? [1].merge(z) : z);
};

global DIF = func {
   arg x;
   arg y;
   return LESS(x, y) ? SUB(y, x) : SUB(x, y);
};

global MOD = func {
   arg x;
   arg y;

   LESS(x,y) ? return x;
   z = MOD(x, DBL(y));
   LESS(z,y) ? return z;
   return SUB(z,y);
};

global ISZERO = func {
   arg x;
   return x[0] == 0;
};

global GCD = func {
   arg x;
   arg y;
   return ISZERO(x) ? y : GCD(MOD(y,x),x);
};

#############################################################################

solve = func {
   arg N;
   arg t;
   t = t.map( func{return FROM_STRING(this);} );

   lexical t0 = t[0];
   lexical g  = DIF(t0, t[1]);
   t.slice(2, t.length()).map(func{
      g = GCD(g, DIF(t0, this));
   });
   r = MOD(t[0], g);
   return TO_STRING( ISZERO(r) ? r : DIF(g,r) );
};

input = sys.library("streams").stdio().read(1000000000).split("\n").map(func{return this.split(" ");});
C = input[0][0].num();

CaseID = (args.length() >= 2 ? args[1].num() : 1);
loop {
   "Case #".print();
   CaseID.print();
   ": ".print();
   solve( input[CaseID][0].num(), input[CaseID].slice(1,input[CaseID].length()) ).print();
   "\n".print();
   ((CaseID = CaseID+1) > C) ? return;
};
  • Smallは全部通るので合ってると信じてるんですが
  • Largeを喰わせてみたらインタプリタが強制終了した
  • こういうハプニングもマイナ言語を使う醍醐味だよね!

A-Small .as ActionScript


  • 普段はSmallはSmallっぽくマジメにシミュレーションするコードを書くんですが
  • 今回はLarge的解法の方が楽すぎる
  • ビット演算するだけ
    • と思いきやちょっと間違えて1 wrong
      • ランプが"ON"状態なら明るくなってると思って k&(1<<(N-1)) を返したんですが
      • そこまでのスイッチも全部ONじゃないとダメですね

  • 入力を読み込む処理作るのが面倒だったのでコード中にコピペするという酷い実装
    • 後で試しにLargeのデータ貼り付けてみたらコンパイラにそんな長い文字列はダメですって怒られた。危なかった…
class A
{
   static function main(mc)
   {
      var input_string = "<paste the input data here>";
      var input = input_string.split("\n");
      var T = Number(input[0]);

      var output_string = ""
      for(var C=1; C<=T; ++C)
      {
         var theCase = input[C].split(" ");
         var N = Number(theCase[0]);
         var K = Number(theCase[1]);
         output_string += "Case #" + C + ": " + (solve(N,K)?"ON":"OFF") + "\n"
      }

      _root.createTextField("tf",0,0,0,800,600);
      _root.tf.text = output_string;
   }

   static function solve(N, K)
   {
      var mask = (1<<N) - 1;
      return (K & mask) == mask;
   }
}

A-Large .aml Alice


  • Largeもやはりビット演算するだけ
  • SMLのお作法を知らなすぎたので、ちょっと勉強して、下のコードは提出後に書き直したもの
fun solve (n : int, k : int) : bool =
   let
      open Word
      infix 5 << andb
      val mask = (0wx1 << fromInt n) - 0wx1
   in
      (fromInt k) andb mask = mask
   end

fun main () =
   let
      fun readLine () =
         case TextIO.inputLine TextIO.stdIn of
         | NONE    => []
         | SOME(s) => map Int.fromString (String.tokens (fn x => x = #" ") s)

      fun parseOne c =
         case readLine() of
         | [SOME n, SOME k] => (c, (n, k))
         | _                => assert false

      fun spawn solveOne (c, inp) =
         (c, solve inp)

      fun printOne (c, ans) =
         print ("Case #" ^ Int.toString (c+1) ^ ": " ^ (if ans then "ON" else "OFF") ^ "\n")
   in
      case readLine () of
      | [SOME t] => List.app printOne (List.map solveOne (List.tabulate (t, parseOne)))
      | _        => assert false
   end

do main ()
do OS.Process.exit 0
  • fun spawn solveOne (c, inp) がポイントで、spawn って書いてある関数や式は、そこだけ別スレッドでの実行になります。
  • これがよく言語と統一されているのがキモで、たとえば
    • [spawn fib 10, spawn fib 20, spawn fib 30]
  • というコードは、普通に int の list という型がつく
  • で、メインスレッドが、まだ計算が終わっていないspawn式にアクセスしようとしたら、そこでブロック

  • まったく同じ形で遅延評価が統一されていて
    • [lazy fib 10, lazy fib 20, lazy fib 30]
  • とするとやはり同じ int の list という型になる
  • 各要素の値にアクセスしようとしたら、その時点で実行を始める

  • もう一つ、論理型言語的な、「あとでunifyされる値」みたいなものも同じ仕組みになっていて
    • let val p = promise() val q = future p in [q, q, q, 1, 2, 3] end
  • とすると、「q はあとで int の値が決まって入るけどとりあえず保留」みたいな状態になる
  • 式全体は int の list の型になる。
    • あとで fulfill (q, fib 20) とかすると全部の q がその時点でfib 20の値になる

  • こういう風に型が透過的な Future は便利だなあということに気づかされました。いやはや面白い。
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100509
 | 

presented by cafelier/k.inaba under CC0