Round 1A (Google Code Jam 2009)

練習のためやってみた．
Bは問題文が長いので，まだ読んでいない．

（前回と同じテンプレート使用）

A

各baseに対するhappy数達を,無限リストとして，計算しておいて，最後にintersectionをとる．
という，作戦だが，どうも遅い．メモリを沢山使う．
やはり，これは配列つかって解く問題なのか？

main = do (n:_) <- getList
          forM_ [1..n] $ \i ->
              do bs <- getList
                 putStrLn.output i $ allHappy bs

expand :: (Integral a) => a -> a -> [a]
expand b = reverse.unfoldr f
    where f 0 = Nothing
          f x = let (q,r) = divMod x b
                in Just (r,q)

ssd :: (Integral a) => a -> a -> a
ssd b = sum.map (^2).expand b

isHappy :: (Integral t) => t -> t -> Bool
isHappy 2 _ = True
isHappy b n = hpart S.empty n
    where hpart s x | y == 1       = True
                    | S.member y s = False
                    | otherwise    = hpart (S.insert y s) y
                    where y = ssd b x

upp :: (Num a) => a -> a
upp b =  foldl' add 0 $ replicate 4 (b-1)
    where add x y = b * x + y

happy,happyMemo :: Integer -> [Integer]
happy 2 = [1..]
happy b = small ++ hpart (S.fromList small) [upp b+1..]
    where small = filter (isHappy b) [1..upp b]
          hpart s (x:xs) | S.member y s = x : hpart s xs
                         | otherwise    = hpart s xs
              where y = ssd b x
happyMemo = memo happy

allHappy :: [Integer] -> Integer
allHappy bs = head.tail.foldl1' intersect' $ map happyMemo bs

intersect' :: (Ord t) => [t] -> [t] -> [t]
intersect' (x:xs) (y:ys) =
    case x `compare` y of
      EQ -> x : intersect' xs ys
      LT -> intersect' xs (y:ys)
      GT -> intersect' (x:xs) ys

C++で配列ベースで実装してみたら，断然こっちのほうが効率良い．

#include <iostream>
#include <sstream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(x,xs) for(__typeof((xs).begin()) x = (xs).begin(); x != (xs).end(); x++)
#define ALL(xs) ((xs).begin()), ((xs).end())

typedef vector<int> vi;

const int U = 11814486;

inline vi getvi()
{
  string s;
  getline(cin, s);
  istringstream is(s);
  vector<int> vi;
  for(int i; is >> i;)
    vi.push_back(i);
  return vi;
}

inline int getint()
{
  string s;
  getline(cin, s);
  istringstream is(s);
  int n;
  is >> n;
  return n;
}

inline int ssd (int n, int b) {
  int s = 0;
  while (n > 0) {
    s += (n % b) * (n % b);
    n /= b;
  }
  return s;
}

inline bool isHappy(int n, int b,bool (* h)[11],bool (* v)[11]){
  if (v[n][b]) return h[n][b];
  v[n][b] = true;
  return h[n][b] = isHappy(ssd(n,b),b,h,v);
}

inline int solve(bool (* h)[11],bool (* v)[11])
{
  vi bs = getvi();

  for (int x = 2;;)
    {
      FOR (b,bs) if (!isHappy(x,*b,h,v)) goto NEXT;
      return x;
    NEXT:
      x++;
    }
}

inline void init(bool (* h)[11],bool (* v)[11])
{
  for (int i = 0; i < U; i++)
    for (int j = 0; j < 11; j++)
      h[i][j] = v[i][j] = false;
  for (int j = 0; j < 11; j++) h[1][j] = v[1][j] = true;
}

int main() {
  bool (* h)[11] = new bool[U][11], (* v)[11] = new bool[U][11];
  init(h,v);

  int t = getint();

  for (int i = 1; i <= t; i++)
      cout << "Case #" << i << ": " << solve(h,v) << endl;
}

「空白区切りの整数の並びを1行読み込む」のやりかたが分からず，苦労した．
結局，どこかからのコピペ．

C

確率の問題であるが，DP（多くの確率の問題はDPな気がする）．
そんなわけで，漸化式のようなものをたてて，あとはメモ化再帰．

main = do
  (t:_) <- getList
  forM_ [1..t] $ \i -> do
         (c:n:_) <- getList
         putStrLn.output i $ expected c n

choose :: (Integral a) => a -> a -> Integer
choose n r = div (prod (n-r+1) n) $ prod 1 r
    where prod a b = product [toInteger a..toInteger b]

prob :: (Integral a, Fractional b) => a -> a -> a -> a -> b
prob c n g a = on (/) fromInteger num (choose c n)
    where num = choose (c-g) a * choose g (n-a)

expected :: Int -> Int -> Double
expected c n = e 0
    where eM = memo e
          e g | g == c    = 0
              | otherwise = (1 + sum [p a * eM (g + a) | a <-[1..min n (c-g)] ]) / (1 - p 0)
              where p a = prob c n g a

なんども書くが，MemoTrieが便利すぎる．