練習のためやってみた．

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  = 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  $ 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 = ;
while (n > ) {
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 = ; i < U; i++)
for (int j = ; j < 11; j++)
h[i][j] = v[i][j] = false;
for (int j = ; 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 
where eM = memo e
e g | g == c    = 
| otherwise = (1 + sum [p a * eM (g + a) | a <-[1..min n (c-g)] ]) / (1 - p )
where p a = prob c n g a

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