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
    • オブジェクト指向/関数型ハイブリッド
    • 制約プログラミングも行ける
      • 「バックトラックのためにこのデータの現在のデータを記憶/戻す」のようなversioningの機能が言語組み込み等々
    • 「型 とは 値の集合 である」という哲学がかなり徹底された特徴的な型システム
  • などが目立つところですが、いたって普通のコードしか出番がありませんでした…

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

  • それだけかと思いきや、
  • この言語には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

  • Blue というスクリプト言語です
    • Lua / JavaScript っぽいテーブルが全て的言語モデル
    • 節約主義者文法
      • ifという予約語がなくてすべて条件演算子 ? : で書く
      • else なし if まで cond ? expr って書くのはなかなか
      • ループも無限ループの loop { ... } しかないのであとは頑張れ、等

  • 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

  • Alice
    • 基本は普通の Standard ML です。SMLのコードは基本的に通ります。
    • 拡張として
      • 並列計算や遅延評価
      • 第一級(高階)モジュール
        • なんか合わせ技でモジュールの定義にlazyとかつけられる…すごい…
      • 制約解消系ライブラリを提供
      • などなどなど

  • 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

2009-09-28

Google Code Jam 2009 Round 2

| 12:29 | はてなブックマーク -  Google Code Jam 2009 Round 2 - cafelier@SRM

GCJ09-R2 の成績・ソース : AC-AC/_-_/AC-_/AC-_ : パニクりすぎ

A開く

  • お、問題文短い!
  • 『N×Nの、各要素は0か1の行列があります。隣接する行と行のswapを最小の回数やって、下三角にだけ1があるようにしてね』
    • Small: N≦8
    • Large: N≦40
  • とりあえず、各行毎に一番右の1の位置を計算しておけば
  • 『N要素の、各要素は0~Nのint配列vがあります。隣接要素のswapを最小回数にして、v[i]<=i になるように並び替えてね』
  • という問題になる

  • これ解がない場合もあるよなあ
    • あ、そういう入力はないと仮定して良い、と書いてある

  • うーん。なんだ。ということはソートすれば確実に正しい状態になってる。
    • バブルソートを書いて回数数えればいいとかかな。
    • いや、でもソートしきらなくても正しい状態になることはあるし…
    • …???
  • さっぱりわからん!次!

B開く

  • うわ面倒くさそう。後回し
  • digとか書いてあるし絵の感じからして、ミスタードリラーみたいなゲームかな…

C開く

  • 『折れ線グラフをN本描きたいんだけど、接したり交差したりするグラフは紛らわしいので別の図にしたい。そうでないのは1枚の図に詰め込む。最小で何枚の図が必要?』
    • Small: N≦16
    • Large: N≦100

  • とりあえず折れ線グラフの交差判定をしてから、
  • 「交差しないグループ」何個で全体をカバーできるか…という最小カバー問題にはなるなあ。
    • SmallのN≦16は愚直に全部のカバー方法を試して間に合うか
    • Largeは、折れ線の交差で作られる関係に限ることを利用するとなんかグラフのマッチングとかフローとかになるのかな。D-Largeよりは解けそうかも
    • (折れ線グラフ的な意味の)グラフをネタに(組み合わせ論的な意味の)グラフの問題を作ったというわけか!

  • それはそうとコード量多そう。めんどくさい。後回し。

D開く

  • 要は
  • 『半径rの円がN個、二次元平面上にばらまかれています。全部を、半径Rの円2個で覆おうと思ったとき、Rを最小にしてね』
    • Small: N≦3
    • Large: N≦40

  • て、読んでる間にもうA解いてる人がいる。すげー
  • それはともかく、N=3 なら、1個をカバーする円と2個をカバーする円に分ける分け方は3通りしかないから、全部試して最小を選べばよい

  • N=1 の場合…はR=r
  • N=2 の場合…R=max(r)
  • N-3 の場合…は、3通りの分け方の最小値を…
    • よし、だいたいかけた。
    • 2個(x0,y0,r0)と(x1,y1,r1)を1個でカバーするには半径Rをいくつにすればいいかな?
      • 絵を描いてみる
      • 2つの円の中心を結ぶ線の上に中心を置いて、両方に接するようにすればよさそう
        • distance( (x0,y0), (x1,y1) ) + r0 + r1 が直径

  • できた。サンプル通った
  • Small提出。通った

  • Largeは…2円か3円かに接する様な円を全列挙してそこから2つとって全カバーできるペアを全探索、かなあ。
  • 3円に接する円の中心を求めるとか書きたくない。放置。

Aに戻る

  • 点数も低いし、大量に解いてる人いるし、そんなに難しいはずは…

  • は…
  • あ、そうか、Smallの場合8行しかないから、並べかえ方は 8! = 40320 通りしかない
  • てことは、1回のswapでできる状態、2回のswapでできる状態、…を幅優先探索で全部探していっても余裕で時間内に終わる

  • 書いた
  • サンプル、Small通った。よし

  • そしてLargeは相変わらずさっぱりわからない…。
  • …なんでこんなにたくさん解いてるんだ。点数も低いし
  • 謎だけどわからないし他をやる

Cに戻る

  • とりあえずSmall書く
  • あ、折れ線の折れるポイントは全部共通だから、交差判定はすごい簡単だ

  • さて最小カバー。
    • 「まだ図に描いてないグラフの集合」を与えると、メモ化再帰で必要な最小の図の枚数を求める関数を書く
    • 引数の状態数は 2^N。
    • 各ステップは、重ならないグラフ集合は O(2^N) 個あるから
    • O(4^N) かー。4分ならなんとか終わるんじゃないかなー。ペナルティ低いしやってしまえ

  • 書いた。
  • サンプル通った
  • Small…うわー全然おわらない。4分の時点で1/3くらいしか終わらなかった。
    • なんかよくみたら O(N 4^N) か O(N^2 4^N) くらいのソースを書いてる気がする。これはダメだなあ。

  • たしか、むかしSRM過去問解いたときに、最小カバー使ったことがある…
    • (過去コード探索中…)
    • あった!
  • よくわからんが、これ使えば通るんじゃ。
  • コピペ。Go!

  • ゼロ除算で落ちた
    • は?
    • next_combination でなんか落ちてる
    • うーん。このコード書いたときに暗黙に仮定してた前提条件がなにかあるんだろうな…
    • わからんなー。

  • その昔のコードを読んでみると、
    • カバーに使う集合を極大集合に限定する等々の最適化 → 地道に探索
  • の2ステップになってる。前半はちゃんと動いてるっぽいので後半だけ今書こう。
    • 書いた。
    • Smallのデータ改めていれてみる
    • なんだか、前半が時間かかりすぎるデータがまだあるっぽい

  • よく考えたら N≦8 くらい向けに書いたコードだった気もしてきた。16だときびしい…

  • うおおどうすれバインダー


  • あらためて今やっていることを整理
    1. 「一つの図に描いてよい折れ線グラフ部分集合」を全列挙
    2. 無駄な物(他の一つの図に描いてよい集合の真部分集合になってるもの、など)を除く
    3. この集合族の中から最小個数の要素を取り出して、元の折れ線グラフ集合を全カバーする。ここは全探索。


  • うーむ
  • 無駄な物を除くフェーズは、昔のコードはなんかすごい頑張ってるけど、
  • 極大じゃない判定は、1要素増やしてみて大丈夫か判定、をN回くりかえすだけでわかる。これは全体で O(N*2^N) なので十分動く
    • それで十分な枝刈りになってそう
  • 全カバーを全探索のところは、next_combinationとかで探すより、普通に幅優先探索でいいんじゃなかろうか。


  • 書き直し…
  • できた。幅優先探索はAのソースからコピペ。
  • よし、さっき間に合わなかったSmallも終わる!
  • 再ダウンロード。通った!
  • ふぅ…

  • 終わってみれば当たり前のことを当たり前に書くだけだった…
  • なんで1時間もかかってるんだ俺…orz

A-Largeに戻る

  • これだけたくさんの人が解いてる問題が難しいはずはないんだ…n!
  • なんかシンプルな戦略で最適解がでるはず。


  • 上の方の列ほど制約がきついから
  • 上の方に入れるやつは下の方にも入れる
  • ということは、制約のきつい上から順にgreedyに埋められるもので埋めていく感じで最適解がでたり…

  • 自信全くないけどとりあえず書いてみる
    • 上の方の列から見ていって、下三角条件をみたしてなければ、
    • 一番近い、条件を満たす列をとってきてswapで持ってくる
    • 以下繰り返し

  • これで良いという証明がまったく思い浮かばないけど、
  • …このアルゴリズムでSmallの全探索君と答えが一致した
  • これは行ける!
  • Largeサブミット。

さて

  • 残り45分。
    • スコアボードを見ると
    • 500位の合格ラインは、あとどれでも1問解けば確実そう
    • 解けないとダメそう
  • B-Small、C-Large、D-Large、のどれなら解けるか…
    • D-Largeはたぶん僕には45分で書けない
    • C-Largeは…アルゴリズム思いつけるかどうか自信ないなあ
    • B-Smallは…実装重そうだけど、穴掘るゲームなら、やるべきことはどうせビットDPだろうし、45分全力で実装すれば…

というわけで、Bに戻る

  • 堀り方はミスタードリラーじゃなくてロードランナーだった。
  • 『C×Rマスのマップがあって、1,1からゲーム開始です。左右に動けます。右斜め下と左斜め下が掘れます。下まで降りるには最小で何マス掘ればいいですか』
    • ただし、下に落ちるときにFマスより多く一気に落ちると死亡
    • Small: 横6縦10
    • Large: 横50縦50
  • 今いる座標(6*10) * 今いる行の掘られ状態(2^6)
    • からの最小掘り進み回数をDP or メモ化再帰で求めればよい。
    • 今いるより上の行の掘られ状態は関係ないし、今いるより下の行は、今の行に到達した時点では掘れてない初期状態なのでやっぱり関係ない。一行分の状態だけ覚えとけばよい

  • 問題は、
    • 今いる座標(6*10) * 今いる行の掘られ状態(2^6)
  • から次にいける状態を列挙する処理で…
  • その処理だけ中身空の関数で実装してまわり全部は書けた。

  • えーと、どうする。
  • まず、キャラクタが動ける範囲は、
    • 現在位置から左右に、
      • 今の行にブロックがない
      • 下の行にブロックがある
    • 範囲

  • この範囲は&この範囲のみ自由にうろうろ歩ける
  • 掘ってから落ちるわけだけど、どういう落ち方があるかというと、
    • 落ちる前の足場はないといけない
    • 足場の右に落ちる場合、下の行で左にはいけないので、足場より左の堀り方は関係ないので掘らなくていい。
      • 逆も同様。
    • 行ける範囲の端っこまでいって、足場まで戻りながら隣を掘っていけば、
    • 足場から落ちる側は自由に掘れる。これを全パターン列挙する。

  • つまり
    • 動ける範囲を求める
    • foreach 動ける範囲(6)
      • foreach {左に落ちる, 右に落ちる}(2)
        • foreach {落ちる側の堀り方全通り}(2^6)

  • 頑張って書く
  • 結構時間かかった。のこり7分
  • サンプルあわない!
  • 細々としたバグをフィックスしまくり
  • わあ残り4分だ。もうSmallダウンロードしとけ!
  • 残り3分。サンプル通った!
  • Small動かした。よしサブミット!incorrect!!!!!!!!!!
    • どこが悪いんだ2分でバグとか見つかるわけが…

おしまい

  • 543位。通過ならず。

  • とりあえず、Bは上にブロックがあるマスは掘れないという条件を見落としてました。他にもまだあるかも…
    • ロードランナーはそういうマスも掘れたような記憶が…と思ったけど、そっちも掘れないっぽい。もうだめだ

  • とにかく C-smallがひどかったなあ、と。ここが30分早く解ければB-smallも余裕をもって直せたと思う。

  • まあ、「調子よければ通過できたはず」程度の実力で通過できても喜ぶところじゃない気がするので、来年がもしあれば「絶不調でもRound 2くらい余裕だぜ」と言えるくらいになっていたいものです。がんばろう。
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090928

2009-09-12

Google Code Jam 2009 Round 1A

| 12:44 | はてなブックマーク -  Google Code Jam 2009 Round 1A - cafelier@SRM

GCJ09-R1A の成績・ソース : AC-AC/AC-AC/AC-AC : 八分物語


A開く

  • 『"各桁の数字を二乗して総和を取る"という演算を繰り返して1になれる自然数をhappy numberという。baseによって違うので2進表記ではhappyでも10進だと違ったりする。入力で与えられる全てのbaseでhappyになるような最小の数を答えよう』

  • えーと、happyじゃない場合はどうなるんだ。1にならないでどっかで無限ループか
  • あと、必ずall-happyな数は存在するのかな。問題に書いてないから存在するんだろうな。そういうことにしよう。

  • 入力サイズ
    • baseは2進から10進まで
    • Small: baseは2個か3個与えられる
    • Large: baseは2個から9個まで

  • これは、入力パターンが2^9 = 512通りしかないから、手元で2時間かけて答え全部求めてから即座に表引きで返すような解が作れる…
    • だが断る
    • そうか、だから、"Important Note: Please remember that you must submit all code used to solve the problem." って注意書きがあるのか。そういう解き方をしたら表を作ったソースも忘れずsubmitしろよ、と。

  • さて
    • smallなら地道に、n=2から増やしてって全部でhappyかどうか判定して最初に見つかったのを表示、でいいんじゃないかなあ
    • happy判定は、メモ化 + ループ判定でできる。isHappy?(n,base) =
        • 既に (n,base) の場合が計算済みならそれを返す
        • そうでなければ、とりあえず isHappy?(n,base)==False として計算済みと思いつつ
        • isHappy?(二乗総和(n),base) を再帰呼び出し
        • 返ってきた結果を、改めて isHappy?(n,base) の結果として記憶
      • これで、無駄な最計算はなくなるし、ループしてたら途中の"とりあえずFalse"にヒットしてFalseが返る
  • 組めた

  • サンプルと合った
  • 2,3,4 でも 8,9,10 でも試す。時間は余裕。
  • よしsmall用データをゲット。submit。OK。
  • 次行こう。Largeは取らなくても、Small全取りで十分次のラウンドには進めるはず。

B開く

  • めんどくさい図が見えた。
  • さようなら

C開く

  • 『全部でC枚あるカードをコンプリートしたい。重複なしN枚ずつのセットで売ってくれるのだけど、コンプリートまでに買う必要のあるセット数の期待値は?』
    • Small: C,N<=10
    • Large: C,N<=40
  • Σn=1..∞ (ちょうどnセットかった時に揃う確率)*n
  • が答え
  • 極限を数式で求めるのは…どうすればいいんだー
    • 10000セットくらい買ったときまでシミュレートすれば十分じゃないですかね。誤差10^-5くらいなら。少なくともSmallはそれでいいでしょう。。。
  • 「kセット買ったときそろってる枚数がi枚の確率」みたいなのは行列の掛け算で表すと綺麗。
  • 最初は、v = (0枚そろってる確率=1.0、他=0.0)
  • 次は、N枚そろってる確率=1.0、他=0.0
  • その次は、N枚そろってる確率から 2N枚そろってる確率まで、組み合わせの数に応じて分布
  • ...
  • という1ステップ1ステップの変化を、行列Mで表現できて、
  • Mv、M(Mv)、M(M(Mv))、…で次々求まる。
  • 後は総和をとるだけ
※要するに M は
 (0枚→0枚になる確率  1枚→0枚になる確率  ...  C枚→0枚になる確率)
 (1枚→0枚になる確率  1枚→1枚になる確率  ...  C枚→1枚になる確率)
 ...
 (0枚→C枚になる確率  1枚→C枚になる確率  ...  C枚→C枚になる確率)
こういう「M[i][j] = i枚揃ってる状態で1セット買ったらj枚になる確率」な行列を考えました。
こうすると、v=(今0枚揃ってる確率, 1枚揃ってる確率, ... C枚揃ってる確率) という縦ベクトルに左からMを掛け算すると、もう1セット買った後の揃ってる確率ベクトルになります。各M[i][j]は順列組み合わせの個数を考えて頑張って式を出します

  • (N枚のデッキは重複ないことを忘れていて全然答えが合わず苦戦中…)
  • (あと行列とベクトルの縦横がごっちゃになってて酷い感じ)

  • あー重複ないのか。なんだー
  • 書けた。サンプルは10000回回せばぴったり。
  • 適当に自分でテストケース作ってみても、10000回と12000回ではもう収束しててまったく変わらない。
  • よし!10000回で十分!
  • Smallをsubmit。OK。

B再び

  • 『交叉点の信号がついたり消えたりするので最短時間で左下の角から右上の角まで歩いてね』
    • はいはいダイクストラダイクストラ。
  • なんでもグラフにしてみる の記事の時刻表の例と全く同じ考え方です
    • (場所) だけじゃなくて (場所,到達時刻) のペアによって行ける行き先が違うので、そういう拡大グラフを念頭に最短路
      • (場所,到達時刻) のペアは普通のDijkstraでもどうせ作るので、あまり拡大グラフとかは意識しないかもしれません。
  • というわけで書くだけ
    • 人間のいられる場所を表すデータとして、座標[y,x]の交叉点の左上が(2y,2x)、右下が(2y+1,2x+1)、のようなペアを使うことに決定
      • (y,x,{NE,SE,NW,SW}) みたいなのは考えるのも面倒だった
    • このエンコーディングの扱いを間違えないように気をつけながらガリガリ書く
    • ところで、嫌な入力ケースってなにがあるかなー
    • 右と上以外考えなくていいと見せかけて、すごく待ちの長い信号を作ることで、実は一時的に左や下に戻らないといけないケース
      • 絶対こういうの入ってる。
      • 戻るケースも忘れずdijkstraの隣接頂点列挙に入れておく
    • あとは…
      • Largeの方、信号点滅の時間が10^7オーダー…。これ全部の和を取ったら32bit越えるかな?念のためlongに。
  • できた。Small-submit。OK。
  • LargeもこれはOKでしょー。submit。
import java.util.*;

public class B
{
   public static void main(String[] arg)
   {
      Scanner sc = new Scanner(System.in);
      int T = sc.nextInt();
      for(int C=1; C<=T; ++C)
      {
         System.out.printf("Case #%d: ", C);
         (new B(sc)).caseMain();
      }
   }

   Scanner sc;
   B( Scanner sc ) { this.sc = sc; }

   void caseMain()
   {
      int Y = sc.nextInt();
      int X = sc.nextInt();
      long[][] S = new long[Y][X];
      long[][] W = new long[Y][X];
      long[][] T = new long[Y][X];
      for(int y=0; y<Y; ++y)
         for(int x=0; x<X; ++x)
         {
            S[y][x] = sc.nextInt();
            W[y][x] = sc.nextInt();
            T[y][x] = sc.nextInt();
         }
      System.out.printf("%d\n", solve(Y, X, S, W, T));
   }

   long solve(final int Y, final int X, long[][] S, long[][] W, long[][] T)
   {
      class State implements Comparable<State>
      {
         long t;
         int y, x;
         int id() { return y*(2*X) + x; }
         State(long t, int y, int x){this.t=t; this.y=y; this.x=x;}

         public int compareTo(State rhs) {
            if( t < rhs.t ) return -1;
            if( t > rhs.t ) return +1;
            if( y < rhs.y ) return -1;
            if( y > rhs.y ) return +1;
            if( x < rhs.x ) return -1;
            if( x > rhs.x ) return +1;
            return 0;
         }
      }

      PriorityQueue<State> Q = new PriorityQueue<State>();
      Q.add( new State(0, 2*(Y-1)+1, 0) );

      Set<Integer> visited = new HashSet<Integer>();

      while( !Q.isEmpty() )
      {
         State s = Q.poll();
         if( visited.contains(s.id()) )
            continue;
         visited.add(s.id());

         if( s.y==0 && s.x==2*(X-1)+1 )
            return s.t; // goal

         int[] dy={-1,+1,0,0};
         int[] dx={0,0,-1,+1};
         for(int i=0; i<4; ++i)
         {
            int y2=s.y+dy[i], x2=s.x+dx[i];
            if( y2<0 || 2*Y<=y2 || x2<0 || 2*X<=x2 )
               continue;
            if( visited.contains(y2*(2*X)+x2) )
               continue;
            long t2 = s.t;
            if( s.x!=x2 && s.x/2!=x2/2 ) t2 += 2;
            else if( s.y!=y2 && s.y/2!=y2/2 ) t2 += 2;
            else if( s.x!=x2 )
            {
               long Si = S[y2/2][x2/2];
               long Wi = W[y2/2][x2/2];
               long Ti = T[y2/2][x2/2] % (Si+Wi) - (Si+Wi);
               long d = (s.t - Ti) % (Si+Wi);
               if( d < Si ) t2 += (Si-d)+1;
               else t2 += 1;
            }
            else //if(y!=y2)
            {
               long Si = S[y2/2][x2/2];
               long Wi = W[y2/2][x2/2];
               long Ti = T[y2/2][x2/2] % (Si+Wi) - (Si+Wi);
               long d = (s.t - Ti) % (Si+Wi);
               if( d < Si ) t2 += 1;
               else t2 += (Si+Wi-d)+1;
            }
            Q.add( new State(t2, y2, x2) );
         }
      }
      return -1;
   }
}

A再び

  • 全部の答えを前計算するのはやりたくないなー。
  • なんとか賢く8分以内で…
    • 思いつかない間手が暇だったのでちょっとPythonっぽくyieldなど使うソースに書き換えてみたり
  • とりあえずさっきのsmall解で2,3,4,5,6,7,8,9,10の最悪ケースが何分かかるか計ってみる
    • 2分33秒、これは…

  • テストケース500個あるので一見500倍するとダメそうに見えるけど…
  • 全部メモ化でisHappy判定がキャッシュされるので、2個目移行のケースはそれなりに早いはず。~1000万回程度の辞書引き
    • 2,3,4,5,6,7,8,9,10を2個並べてみたら2個目は3秒くらい。
  • 3秒×500はまだダメそうに見えるけど…
    • 全部最悪ケースで埋めるなんて無体なことはしないと信じよう
    • もうスコアはRound1通過には十分だし、ドキドキ気分を味わいたい

  • Largeダウンロード
  • 実行開始
  • ...
  • ...
  • ...
  • 6分30秒経過...
    • 出力ファイルチラ見。250ケースまで進んでる…!
  • ...
  • ...
  • 7分40秒くらい
    • 解けた!submit!!!!!勝利!!!!!!
  • やばいこれは楽しい
# Python 2.6 (提出後ちょっと整頓した版)

memo = [dict() for _ in range(0,11)]
def isHappy(n, b):
   if n == 1:       return True
   if n in memo[b]: return memo[b][n]

   s = 0
   i = n
   while i > 0:
      s += (i%b)*(i%b)
      i //= b

   memo[b][n] = False
   v = isHappy(s, b)
   memo[b][n] = v
   return v

def happyGen(bases, i=0):
   if i == len(bases):
      n = 2
      while True:
         yield n
         n = n+1
   else:
      for n in happyGen(bases,i+1):
         if isHappy(n, bases[i]):
            yield n

### main ###

import sys

CN = int(sys.stdin.next())
for C in range(1, CN+1):
   bases = map(int, sys.stdin.next().split(" "))
   print "Case #%d: %d" % (C, happyGen(bases).next())

C再び

  • C,N<=10 が C,N<=40に増えても、気にせず10000回も回せば収束しているみたい。
  • ただ、10000だと1ケース15秒くらい。100ケースあるそうなので、これは間に合わない。タイムリミットは480秒。
    • 逆に言うと、1ケース4.8秒くらいまで回して収束してればそれで十分
      • 念のため4秒くらいかかるステップ数(3000回)で実験
      • うん、収束している
  • というわけでLargeダウンロード
  • 実行開始!
  • ...
  • ...
  • ...
  • 6分20秒経過...
    • 解けた!submit!!!!!勝利!!!!!!
-- Lua 5.1.2 (行列の縦横をsubmitした版と逆にした版)

function comb(N,k)
   v = 1
   for i=0, k-1, 1 do
      v = v * (N-i) / (k-i)
   end
   return v
end

function matmult(m, v, n)
   u = {}
   for i=0, n, 1 do
      u[i] = 0
      for j=0,n,1 do
         u[i] = u[i] + m[i][j] * v[j]
      end
   end
   return u
end

function makeM(C, N)
   m = {}
   for to=0, C, 1 do
      m[to] = {}
      for fr=0, C, 1 do
         if N<=to and fr<=to and to<=fr+N then
            m[to][fr] = comb(C-fr,to-fr) * comb(fr,N-(to-fr)) / comb(C,N)
         else
            m[to][fr] = 0.0
         end
      end
   end
   return m
end

function makeV(C)
   v = {}
   v[0] = 1.0
   for i=1, C, 1 do
      v[i] = 0.0
   end
   return v
end

function solve(C, N)
   m = makeM(C, N)
   v = makeV(C)

   e = 0
   for t=1, 3000, 1 do
      u = matmult(m, v, C)
      e = e + t*(u[C]-v[C])
      v = u
   end
   return e
end

-- main
CN = io.stdin:read("*n")
for CID=1, CN, 1 do
   C, N = io.stdin:read("*n","*n")

   io.stdout:write( string.format("Case #%d: %.8f\n", CID, solve(C,N)) )
end

感想

  • AとCはあとでマジメに考えます!Aはこれで正解のような気もするけどCはもう少し何かありそう
    • ああそうかー。Cは期待値で連立方程式になるだけかー。あるいはほとんど遷移関係がdagなのでローカルな方程式だけ使ってDPっぽく。なるほどなあ

Small最速理論

| 20:33 | はてなブックマーク -  Small最速理論 - cafelier@SRM

ついでなので、メタな戦略についても考えていることをだらだらと書いてみる。

  • Largeは見向きもせずにとにかくSmallだけ解けるアルゴリズムを考える

のが去年からの自分の方針です。Small用に考えたコードでそのままLargeを解けたら儲け物だけど、大抵そうもいかないので、Large用にはあらためて新しく考えてコードを書きおこします。

  • 理由A: せっかくSmall/Large分かれてるコンテストなんだから普段のSRMとかと違うことをやりたい
    • やりたい。(これが理由の7割)
  • 理由B: Smallだけでも全完できればそれだけで結構上まで行ける。
    • 2008
      • ラウンド名 Small全問解いた場合の順位, Smallの最高得点問題を落として残り解いた場合の順位 / 足きりライン
      • Round 1A (3) 450-604, (2) 813-1405 / 840
      • Round 1B (3) 262-376, (2) 616-1019 / 840
      • Round 1C (3) 223-375, (2) 621-1570 / 840
      • Round 2 (4) 319-852, (3) 1173-1409 / 1000
      • Round 3 (4) 226-253, (3) 329-396, (2) 626-667 / 500
      • APAC Local (4) 35, (3) 83-86 / 36
      • AMER Local (4) 52 / 21
      • EMEA Local (4) 86 / 43
      • Final (5) 100人中:61位~71位
    • 2009
      • Round 1A (3) 425-428, (2) 685-726, (1) 741-2028 / 1000
  • 理由C: テストケース入手
    • まずSmallをSmall専用コードで解くのは、あとで改めてLargeを解く時にも役立つと思う
      • Smallだけ解けるような単純なコードは、わりと楽に一発で正しく書ける
      • Largeを解けるような工夫したコードは、一発で正しく書くのは難しい
        • テストが充実していると正しく書くのが楽になる ←重要
        • Smallを解いておけば100ケース近いテストが手に入る!

サーバへのsubmitでcorrect/incorrectを見てテストするのだと、ペナルティも食らいますし、そもそもどんなテストケースでincorrectと言われたのかわからなくて、あんまりデバッグの役に立たないので…。手元に正しいinput-outputがあると大違い。

  • 理由D: そんなにタイムロスもないような気がする
    • Small用コードと別にLarge用コードを書き直す、というと無駄に時間かかるようにも思うんですが、入出力の部分や途中のデータ構造、補助関数も結構使い回せるので、意外とやってみると悪くない

とかなんとか。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090912

2009-09-04

Google Code Jam 2009 Qualification Round

| 13:43 | はてなブックマーク -  Google Code Jam 2009 Qualification Round - cafelier@SRM

GCJ09-QR の成績・ソース : AC-AC/AC-AC/AC-AC : 去年の記事にこじつける参加記

A問題見る

  • 『ちょうどD種類の単語(各単語はちょうどL文字。文字はアルファベット小文字26種)があることが判明している古代文明があります。全部の単語は判明済みです。部分的に読み取れてる単語がN個あるので、それぞれ可能な復元方法は何パターンか数えてね』
    • "(abc)d(ef)g" だったら、1文字目はaかbかc、2文字目はdで確定、3文字目はeかf、4文字目はgで確定
    • 単純に掛け算すると6通りだけど、そこから単語になってないものを削ると何通りかを数える

  • アルゴリズムコンテストの挑み方 (1) 「書く前に計算量を見積もろう」
    • 解き方なんて一瞬も考えようともせずにまずは入力データのサイズを見ます
      • Small: 1 ≤ L ≤ 10, 1 ≤ D ≤ 25, 1 ≤ N ≤ 10
      • Large: 1 ≤ L ≤ 15, 1 ≤ D ≤ 5000, 1 ≤ N ≤ 500
      • あと、文字の種類C≤26も効いてくるかも
    • だいたいの自分の感覚からすると…
      • 時間計算量 O(LDN) のアルゴリズムは、Largeの制限時間8分でも通る。
      • だから、それよりも高速なアルゴリズム(O(LD)+O(LN)等)を考案する必要は全くない。これで十分。
      • O(CLDN) は…C++ならなんとかなるかなあ。遅めの言語だと不安。しかしそんな嫌なケースはこないような気もする
      • Largeは捨ててSmallだけ通るような計算量オーダは? O(2^L ND) とかその辺か
    • (※この概算をする際に頭にうかべる計算量の項の選出基準として
      • データベース(D)とクエリ(N)みたいな関係の場合、何も考えずやるとO(DN)っぽくなるけど、インデックスを作る的なことをするとO(D+N)っぽくなる
      • 個別データの長さ(L)みたいなのは、何も考えずやると O(2^L) っぽくなるけど、工夫するとO(L)っぽくなる。DやNに関して指数時間や、その他線形より大きいオーダになりそうな気配はあんまりない
    • みたいなのが自分の脳内にあるような気がする)

  • というわけで、O(LDN) くらいを目標にアルゴリズムを考える。
    • 機械的に、foreach(未確定単語)foreach(既知の単語)マッチしたらcount++。
    • と、こんなもんじゃないかな。それだと O(CLDN) か。まあいいや、それで。
  • マッチしたかどうか判定はどうしよう。
    • 先頭からループしてって1文字1文字L文字目まで比較すればいいんだけど、
    • 括弧の関係をちゃんとparseするのがめんどくさい。だるい。

  • ピコーン
    • これ、'(' と ')' を '[' と ']' に置き換えたら正規表現じゃね?
    • "[abc]d[ef]g" だったら、1文字目はaかbかc、2文字目はdで確定、3文字目はeかf、4文字目はgで確定
    • 完 璧
// Rhino 1.7
var INPUT   = readFile(arguments[0]).split("\n")

var [L,D,N] = INPUT[0].split(" ").map(Number)
var words   = INPUT.slice(1, 1+D)
var cases   = INPUT.slice(1+D, 1+D+N).map(toRegex)
var answers = cases.map(solve)

for(var C=0; C<answers.length; ++C)
   print( "Case #"+(C+1)+": " + answers[C] )

function toRegex(s)
   { return RegExp("^"+s.replace(/\(/g,"[").replace(/\)/g,"]")+"$") }

function solve(pat)
   { return words.filter( function(w){return pat.test(w)} ).length }

  • ということでできた。正規表現の実装がちゃんとしてればO(LDN + CLN)くらいじゃないでしょーか。
  • Small のデータをダウンロード…なんかエラー出た。ちょっとバグってるからしばらく待てと運営からメッセージが来てる。
  • 不安だから念のためC++でも書いておこう。
    • 結局括弧のparseとか書いてる
    • 書けた
  • あらためて Small ダウンロード → submit → 正解!
  • Large ダウンロード → js版でも数秒で終わった。疑ってすみませんでした → C++版とも答え合ったし、submit

B問題開く

  • 『H×Wマスの2次元の高さマップが与えられるので、雨が降ったらその雨がどのマスに溜まるかで分類・色分けしてください。』
    • 自分の周囲4マスのうち、一番低い(かつ自分より低い)マスに流れる
    • 同点の場合は、北、西、東、南の順に優先。要はy座標小さい順→同じならx座標小さい順

  • 入力サイズは?
    • Small : 1 ≤ H, W ≤ 10; 0 ≤ altitudes < 10.
    • Large: 1 ≤ H, W ≤ 100; 0 ≤ altitudes < 10,000.
  • 要は10000マス。高さの値の大きさが問題になることはたぶんないでしょう…大小比較するだけだし。
  • 深く考えなくても、色塗りなら適当に塗ってれば O(HW) になるんじゃないかなー。これなら速度は十分すぎる。O((HW)^2)はギリギリな感じ。それより遅いとマズい。

# Ruby 1.8.7
gets.to_i.times do |c|
   puts "Case ##{c+1}:"

   # read the input
   h,w = gets.split(" ").map(&:to_i)
   m = (0...h).map{ gets.split(" ").map(&:to_i) }

   # union-find data structure
   uf,sz = {},{}
   (0...h).each{|y| (0...w).each{|x| uf[[y,x]]=[y,x] ; sz[[y,x]] = 1 }}

   # merge
   (0...h).each{|y| (0...w).each{|x|
      low = [[y-1,x], [y,x-1], [y,x+1], [y+1,x]].
            select{|yy,xx| 0<=yy && yy<h && 0<=xx && xx<w }.
            select{|yy,xx| m[yy][xx] < m[y][x]}
      if low.size > 0
         # uf
         a = [y,x]
         b = low.min_by{|yy,xx| [m[yy][xx],yy,xx]}
         a = uf[a] until uf[a]==a
         b = uf[b] until uf[b]==b
         if a != b
            a,b = b,a if sz[a] > sz[b]
            uf[a] = b
            sz[b] += sz[a]
         end
      end
   }}

   # coloring
   cur = ?a - 1
   cl = Hash.new{|cl,k| cl[k] = (cur+=1)}

   ans = (0...h).map{|y| (0...w).map{|x|
      a = [y,x]
      a = uf[a] until uf[a]==a
      cl[a]
   }}

   # output
   puts ans.map{|ss| ss.map(&:chr)*" "}
end
  • やたら長くなってしまった…普通に溜め池になるマスまでたどって塗っていく方がよかったかもしれない。まあいいや。
  • パス圧縮してないけどバランシングはしているので、計算量は O(HWlog(HW))なはず。
  • download & submit & download & submit! 20秒くらいかかって焦った。ちょっと富豪的に書きすぎた

 +--+--+--+
 |  |  |  |
 +--+--+--+
 |  |  |  |
 +--+--+--+
 |  |  |  |
 +--+--+--+

のまま考えるんじゃなくて

  ○-○-○ 
  |  |   |
  ○-○-○ 
  |  |   |
  ○-○-○ 

というグラフを思い浮かべる、ということはやっているような気がしなくもないです。チェス盤のマス目は二部グラフ のようなアイデアを使うと鮮やかに解ける問題には結構行き当たるので。


C問題開く

  • 『与えられた文章の中から "welcome to code jam" を何個取り出せるか、数えてね』
  • サイズ
    • Small: 文章の長さLは30文字まで
    • Large: 文章の長さLは500文字まで
  • O(2^L) はSmallでギリギリ。Largeだと私が死ぬまで計算機回しても通らない。絶対に、指数時間になるアルゴリズムを書いてはいけない。
  • O(L)かO(L^2)、最悪でもO(L^3)で解かねばならぬ。

  • 賢く解くには…グラフ…にしてみようにもどうしたらいいのかわからないなー。

  • ここはもう一つの手段、アルゴリズムコンテストの挑み方 (2) 「問題をひとまわり小さくしてみる」
    • 元の文章を text[0..L] とする。L を減らしてみよう。
    • つまり A =「text[0..L-1] に "welcome to code jam" が何個あるか?」をまず求める。
    • 求まったらなんか嬉しい?
      • 最後の1文字が "m" じゃない場合、すごく嬉しい。だって、その値 A がそのまんま答えになる
      • 最後の1文字が "m" だった場合、全体の答えは A + 「text[0..L-1]に"welcome to code ja"が何個あるか?」で求まる
        • 「text[0..L-1]に"welcome to code ja"が何個あるか?」はどう求める?
        • さらにLを小さく、「text[0..L-2]に"welcome to code ja"が何個あるか?」を求めて、
        • text[0..L-1]の最後の文字が"a"じゃないならそのままそれが答え
        • "a"なら、それに加えて「text[0..L-2]に"welcome to code j"が何個あるか?」も足す
    • 要するに
      • text[0..0] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
      • を求めれば
      • text[0..1] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
      • が求まって、次に
      • text[0..2] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
      • がわかって
      • ...
      • text[0..L] に "w" が何個、"we" が何個、…"welcome to code ja"が何個、"welcome to code jam"が何個あるか
      • がわかる。これだ!計算量は O(L×"welcome to code jam".length)
// Digital Mars D v2.031 (Submitした版よりもう少し手を入れました)
import std.stdio;
import std.string;
import std.conv;

int solve( string input )
{
   string target = "welcome to code jam";

   int[] q = [1] ~ new int[target.length];
   foreach(c; input) {
      int[] q2 = q.dup;
      foreach(i; 0..target.length)
         if( c == target[i] )
            q2[i+1] = (q[i+1] + q[i]) % 10000;
      q = q2;
   }
   return q[target.length];
}

void main()
{
   int N = to!(int)( stdin.readln.chop );
   foreach(i; 0..N)
      writefln("Case #%d: %04d", i+1, solve(stdin.readln.chop));
}
  • q[i] が「"welcome to code jam"[0..i] が何個あるか」を記憶しています
  • download&submit&download&submit。done。
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20090904

presented by cafelier/k.inaba under CC0