今みても、基本的な手法を色々確認できて面白い。
A - One Card Poker
シグネチャを決める。
abc054a :: Int -- A
-> Int -- B
-> String -- 答え
強さの数値として、2～13のカードはそのままの値、1のカードには14を与えて、これを比較すればよい。
結果
abc054a a b =
case compare (val a) (val b) of
GT -> "Alice"
EQ -> "Draw"
LT -> "Bob"
where
val 1 = 14
val k = k
B - Template Matching
シグネチャを決める。
abc054b :: Int -- N
-> Int -- M
-> [String] -- Ai
-> [String] -- Bi
-> Bool -- 答え
abc054b n m as bs = ...
「テンプレート画像Bが画像Aの中に含まれている」という表現にはあいまいさがある。
「Bを平行移動して重ねたとき、Bの全ての黒マスがAでも黒マスになっている」という読み方と、
「Bの全てのマスが一致している」という読み方ができる。
例1の説明の中に「テンプレート画像Bが、画像A中の左上の 2×2 の部分画像と右下の 2×2 の部分画像に一致する」
（強調筆者）とあるところから、後者であるとわかる。
よって、Bがはみ出さないように平行移動する全てのやり方の中で、
重ねた区画が一致するようなやり方が少なくとも一つ見つかれば True とする。
リストのままする解法
Data.List.Split.divvy は、与えられたリストから、長さ n のリストを、先頭を m ずつずらしながら切り出せるだけ切り出すという
風変わりな計算をする。今回の場合にうってつけ。
まず divvy m 1 as で Ai を M 行だけの高さで、全ての位置で切り出す。
さらにそれら M 行を同時に divvy m 1 することで、 M 列だけの幅で、全ての位置で切り出す。
これが Bi と全て一致すればよい。
import Data.List
import Data.List.Split
abc054b :: Int -> Int -> [String] -> [String] -> Bool
abc054b _n m as bs = or
[ True
| as1 <- divvy m 1 as
, as2 <- transpose $ map (divvy m 1) as1
, bs == as2
]
二次元配列を使う方法
もっと普通のやり方。
import Data.Array
abc054b :: Int -> Int -> [String] -> [String] -> Bool
abc054b n m as bs = or
[ True
| i <- [0 .. n - m]
, j <- [0 .. n - m]
, (bb ==) $ elems $ ixmap ((1,1),(m,m)) (\(x,y) -> (x+i,y+j)) aA
]
where
aA = listArray ((1,1),(n,n)) $ map ('#' ==) $ concat as
bb = map ('#' ==) $ concat bs
ハッシュ？
公式解説に
より高速な解法として、ハッシュを用いた解法が存在します。(詳細は略)
とだけ書かれているが、よくわからない。
C - One-stroke Path
シグネチャを決める。横着する。
abc054c :: Int -- N
-> Int -- M
-> [[Int]] -- ai, bi
-> Int -- 答え
順列組み合わせを使う方法
たかだか $N \leq 8$ なので手を抜くと、1を先頭とする全ての 1～N の順列組み合わせを作り、
それがグラフ上で経路として正しいものを数える。
import Data.List
import Data.Array.Unboxed
abc054c :: Int -> Int -> [[Int]] -> Int
abc054c n _m uvs = length
[ ()
| p <- permutations [2 .. n]
, and [g ! ab | ab <- zip (1 : p) p] ]
where
g :: UArray (Int,Int) Bool
g = accumArray (flip const) False ((1,1),(n,n)) $
[ ((u,v),True) | u:v:_ <- uvs] ++
[ ((v,u),True) | u:v:_ <- uvs]
真面目に深さ優先探索する方法
訪問済み頂点集合はビットで表現する。
import Data.Bits
import Data.Array
abc054c :: Int -> Int -> [[Int]] -> Int
abc054c n _m uvs = dfs (bit 1) 1
where
g = accumArray (flip (:)) [] (1,n) $
[ (u,v) | u:v:_ <- uvs] ++
[ (v,u) | u:v:_ <- uvs]
done :: Int
done = sum [bit i | i <- [1 .. n]]
dfs :: Int -- 訪問済み頂点集合のビット表現
-> Int -- 現在位置
-> Int -- 答え、経路の本数
dfs visited u
| visited == done = 1
| otherwise = sum [dfs (setBit visited v) v | v <- g ! u, not $ testBit visited v]
巡回セールスマン問題
公式解説に
より高速な解法として、bitDP を用いた時間計算量 $O(2^N N^2)$ となる解法が存在します。(詳細は略)
と書き逃げされている。想像するに、訪問済み頂点集合をビット表現する部分が $2^N$ で、
それらのうち、最後に訪問した頂点が $u$ である経路の本数を $2^N \times N$ 要素の配列に格納して、
もう一本そこに辺を継ぎ足すという、巡回セールスマン問題の解き方の一つを使う感じかな？
import Data.Bits
import Data.Array
abc054c :: Int -> Int -> [[Int]] -> Int
abc054c n _m uvs = sum [cnt ! (all1, i) | i <- [2 .. n]]
where
g = accumArray (flip (:)) [] (1,n) $
[ (u,v) | u:v:_ <- uvs] ++
[ (v,u) | u:v:_ <- uvs]
all1 :: Int
all1 = pred $ bit $ pred n
bnds = ((0,1),(all1,n))
cnt = listArray bnds $ map f $ range bnds
f (0,1) = 1 -- スタート地点
f (_,1) = 0 -- それ以外で末尾1はありえない
f (visited, u)
| not $ testBit visited (u - 2) = 0 -- 無意味な組み合わせ。使わない
| otherwise = sum
[ cnt ! (visited1, v)
| let visited1 = clearBit visited (u - 2)
, v <- g ! u, v == 1 || testBit visited1 (v - 2) ]
-- , v <- g ! u ]
頂点1は常に訪問済みなので、ビット表現は頂点2をビット0とする。
v が無効な場合を参照しても結果は0になるだけなので、testBit visited1 ... はサボっても影響ない。
総当たり $O(N!)$ とセールスマン問題の $O(2^N N^2)$ を比較してみると、
$N! = 1 \cdot \ldots \cdot N$
$2^N \cdot N^2 = 2 \cdot \ldots \cdot 2 \cdot N \cdot N$
$N! / (2^N \cdot N^2) = \frac{1}{2} \cdot \ldots \cdot \frac{N}{2} \cdot \frac{1}{N} \cdot \frac{1}{N}$
これが $>1$ になるには、Nがある程度大きくならないといけない。$N \leq 8$ では実感できない。
D - Mixing Experiment
シグネチャを決める。横着する。
abc054d :: [Int] -- N,Ma,Mb
-> [[Int]] -- ai, bi, ci
-> Int -- 答え
ストレートに
$N \leq 40$ といっても $2^{40} - 1$ とおりの組み合わせを調べる必要があるように見えてたじろぐが、
$1 ≦ a_i,b_i,M_a,M_b ≦ 10$ と振り幅が小さいので、$a_i, b_i$ の和はたかだか400までしか行かない。
両方の組み合わせで $401^2 = 160,801$ 要素の配列に、その配合を作る最小価格を入れた配列を
40回舐めて 6,432,040 回の演算は間に合う。
(aiの和 ,biの和) というペアをキーにした Map でも、
配合不能な場合に無限大を入れた Array でも解ける。
配列版で。
import Data.List
import Data.Array.Unboxed
abc054d :: [Int] -> [[Int]] -> Int
abc054d [_n,ma,mb] abcs
| null cands = -1
| otherwise = minimum cands
where
tooBig = div maxBound 2
bnds = ((0,0),(400,400))
arr0 = listArray bnds $ 0 : repeat tooBig :: UArray (Int,Int) Int
arrN = foldl' step arr0 abcs
step arr (a:b:c:_) = accum min arr [((p+a,q+b),r+c) | ((p,q),r) <- assocs arr, r < tooBig]
cands = [z | xy <- zip [ma, ma + ma .. 400] [mb, mb + mb .. 400], let z = arrN ! xy, z < tooBig]
計算の流れはナップザック問題と似ている。
半分全探索
上で十分速いのでもういいのだけど、半分全探索を使って計算量を下げられると、
公式解説にもユーザ解説にも言葉だけあるのでやってみる。
上のロジックをN/2ずつについて実行すると、$201^2$ 要素の配列が二つできる。大きさ1/4
片方を ((a,b),c) もう一方を ((d,e),f) としたとき、
$a+d : b+e = M_a : M_b$ となるような組み合わせについて $c+f$ の最小値を求める。
突き合わせる相手が1:1でないので、少し煩わしい。
import Data.List
import Data.Array.Unboxed
abc054d :: [Int] -> [[Int]] -> Int
abc054d [n,ma,mb] abcs
| null cands = -1
| otherwise = minimum cands
where
tooBig = div maxBound 2
bnds = ((0,0),(200,200))
n2 = div n 2
arr0 = listArray bnds $ 0 : repeat tooBig :: UArray (Int,Int) Int
arrN1 = foldl' step arr0 $ take n2 abcs -- 前半分
arrN2 = foldl' step arr0 $ drop n2 abcs -- 後半分
step arr (a:b:c:_) = accum min arr $
[((p+a,q+b),r+c) | ((p,q),r) <- assocs arr, r < tooBig]
cands =
[ cz
| ((a,b),c) <- assocs arrN1, c < tooBig
, xy@(x,y) <- zip [- a, ma - a .. 200] [- b, mb - b .. 200] -- 突き合わせ
, x >= 0, y >= 0
, let z = arrN2 ! xy, z < tooBig
, let cz = c + z, 0 < cz ]