A - Maximize the Formula
シグネチャを決める。無精する。
abc110a :: [Int] -- A,B,C
-> Int -- 答え
最大の数字Pを10の位に置いたら、残りの二つQ,Rは1の位で、足し合わせるのでどっちがどっちでもいい。
$10P + Q + R = 9P + P + Q + R = 9P + A + B + C$
結果
abc110a :: [Int] -> Int
abc110a abc = 9 * maximum abc + sum abc
公式解
全パターンを試しても3つなので、それを作ってから最大値を選ぶというアプローチを説明している。
abc110a [a,b,c] = maximum [10 * a + b + c, a + 10 * b + c, a + b + 10 * c]
ここから共通項をくくりだしていくと
maximum [10 * a + b + c, a + 10 * b + c, a + b + 10 * c] =
let abc = a + b + c in maximum [9 * a + abc, 9 * b + abc, 9 * c + abc] =
let abc = a + b + c in maximum [9 * a, 9 * b, 9 * c] + abc =
let abc = a + b + c in 9 * maximum [a, b, c] + abc =
9 * maximum [a, b, c] + (a + b + c)
と、上の解が導出される。
B - 1 Dimensional World's Tale
シグネチャを決める。
abc110b :: Int -- N
-> Int -- M
-> Int -- X
-> Int -- Y
-> [Int] -- xi
-> [Int] -- yi
-> Bool -- 答え (TrueのときWar)
X側の最大値がY側の最小値にかかっていなければ戦争にはならない。
結果
abc110b :: Int -> Int -> Int -> Int -> [Int] -> [Int] -> Bool
abc110b _n _m x y xs ys = xmax >= ymin
where
xmax = maximum $ x : xs
ymin = minimum $ y : ys
公式解、ユーザ解説ともに、「$X < Z \leq Y$ の範囲で $Z$ を試し、一つでも条件を満たすものがあれば No War」というnaiveなアプローチを紹介しているが、もういいね。
C - String Transformation
シグネチャを決める。
abc110c :: String -- S
-> String -- T
-> Bool -- 答え
問題の条件から、可能な変換は、一対一対応に限られ、また、あらゆる一対一対応が可能なことを示す。
文字だと考えにくいので、1から26に対して同じ数を割り当てる対応を考える。
リストの第i要素に割り当てる先を置いたリストを考えると、 [1..26] で表される。
文字 $c_1$ と $c_2$ を交換することは、任意の整数 $1 \leq i,j \leq 26$ を選び、このリスト中の $i$ と $j$ の位置を交換することに対応する。
そのような操作を任意回行った結果、このリストは常に1から26の順列である。同じ数が重複したり、範囲外の数が紛れ込んだりすることはない。
元々このリストは、対応付けの飛び先を示すものである。
その観点からみると、飛び先が順列であることは、対応付けが一対一対応であることと同値である。
また、操作は任意回行えるので、あらゆる順列を作ることができる。（作れない順列はない。）
よって、SをTにするための変換でも、それが一対一対応（全く現れない文字については無視して）であるかどうかを判定せよ、というのが元の問題の要求である。
結果
富豪的というよりは少し怠惰に、初歩的な関数だけを使って実装することを考える。
それぞれの文字に対応づけられている相手を全て集めたとき、全て同じ文字になっていれば、対応づけられている先が唯一であることが確認できる。
これを両向きに行う。
import Data.Array
abc110c :: String -> String -> Bool
abc110c s t = unique s t && unique t s
unique :: String -> String -> Bool
unique s t = all allSame $ elems $ accumArray (flip (:)) [] ('a','z') $ zip s t
allSame :: Eq a => [a] -> Bool
allSame [] = True
allSame (x:xs) = all (x ==) xs
公式解説は、前からインクリメンタルに、
- 初めての文字なら対応を付ける
- 対応が発見済みの文字なら、矛盾していなければ続行、食い違っていれば投了
を両向きに行う、と言っているようだ。
import qualified Data.Map as M
abc110c :: String -> String -> Bool
abc110c s t = loop M.empty M.empty s t
loop :: M.Map Char Char -> M.Map Char Char -> String -> String -> Bool
loop _ _ "" _ = True
loop fw rv (c:cs) (d:ds) =
case (sub fw c d, sub rv d c) of
(Just fw1, Just rv1) -> loop fw1 rv1 cs ds
_ -> False
sub :: M.Map Char Char -> Char -> Char -> Maybe (M.Map Char Char)
sub m a b =
case M.lookup a m of
Nothing -> Just $ M.insert a b m
Just x | x == b -> Just m
| otherwise -> Nothing
26要素なのでimmutable arrayでも苦ではないが、自分はMapを使う方が好き。
import Data.Array
abc110c :: String -> String -> Bool
abc110c s t = loop arr0 arr0 s t
where
arr0 = listArray ('a','z') $ replicate 26 '.'
loop :: Array Char Char -> Array Char Char -> String -> String -> Bool
loop _ _ "" _ = True
loop fw rv (c:cs) (d:ds) =
case (sub fw c d, sub rv d c) of
(Just fw1, Just rv1) -> loop fw1 rv1 cs ds
_ -> False
sub :: Array Char Char -> Char -> Char -> Maybe (Array Char Char)
sub arr a b =
case arr ! a of
'.' -> Just $ arr // [(a,b)]
x | x == b -> Just arr
| otherwise -> Nothing
D - Factorization
シグネチャを決める。
abc110d :: Int -- N
-> Int -- M
-> Int -- 答え
失敗した考え方
$M$から始めて、$a_i$で割ることで$M$の約数のどれかを辿って、最後に1にたどり着く。
この様子は、次のようなグラフでモデル化できる。
$M$の全ての約数に対応させたノードを持つグラフを考える。
数$Y$が数$X$の約数であるとき、$X$から$Y$への辺を張る。自分へのループも張る。
$M$から$1$への距離$N$な経路の本数が答え。
計算量を節約するため、隣接行列の$N$乗を高速化するまでやったけれど間に合わなかった。
行列の次数は$M$の約数の個数、$O(\sqrt M)$
行列の積を計算するには、成分ごとに次数の積和が必要なのでその3乗、つまり$O(M^{3/2})$
積を計算する回数は$\log N$回に抑えたので、全体の計算量は $O(M^{3/2} \log N)$
$N = 10^5, M = 10^9$ を入れるとまるで無理だったとわかる。
$N$と$M$が逆だったらよかったのに。
自分へのループを張らない
上のグラフで、自分への経路は、$a_i = 1$ で足踏みすることに対応している。
これをなくして、必ずより小さい数に進む形にすると、ループがないDAGとなる。
このグラフの$M$から1への、距離1から距離$N$の経路を考える。
距離$K$の経路は、1でない数で$K$回割ることで$M$を1にした。なので、1を適当に$N-K$個挟み込むバリエーションがある。
よって、距離$K$の経路の本数を$P[K]$とおくと、$\sum_{K=1}^N {}_NC_K P[K]$ が求める答えになる。
mmのキーは$M$の約数、値は、距離ごとの経路の本数をもつリストである。
import qualified Data.IntMap as IM
abc110d :: Int -> Int -> Int
abc110d n m = reg $ sum [ mul c $ comb n (n - i) | (i, c) <- take (succ n) $ zip [0..] (mm IM.! 1)]
where
fs = factors m
mm = IM.fromListWith (zipWith1 (+)) $
(m,[1]) :
[(fj, 0 : mm IM.! fi) | fj:fis <- tails fs, fi <- fis, mod fi fj == 0]
comb = mkComb n
-- factors m ：mの約数を昇順に列挙する
factors :: Int -> [Int]
-- zipWith1 ：片方のリストが尽きても打ち切らないzipWith
zipWith1 :: (a -> a -> a) -> [a] -> [a] -> [a]
-- mkComb n ：n以下の nCk を mod P で求める関数を生成する
mkComb :: Int -> (Int -> Int -> Int)
-- reg x : x を mod P で正規化する
reg :: Int -> Int
-- mul x y : mod P で x * y を求める
mul :: Int -> Int -> Int
落とし穴
自然に考えた「距離1から距離$N$の経路」で、大抵の場合は問題ないが、テストケース 4_hand_2 は許してくれない。
AtCoder Companionsで調べると、$M = 1$の場合は必ず答えは1、とキャンセルしているコードが列挙される。
つまり、$M=1$の場合はスタートがゴールなので、経路は1つに決まっている。
これは特別扱いしなくても、「距離0から距離$N$の経路」とすれば ${}_nC_0 = 1$ で正しく答えが得られる。（ので上のコードはそうなっている。）
公式解説
やれやれできた、と思ったら、公式解説のアプローチはまるで違っていた。（はまやんのユーザ解説も公式と同じ内容）
$M$を素因数分解したら $M = p_1^{b_1} \cdot \dots \cdot p_k^{b_k}$ となったとする。
すると、$a_i$ はみなこれの約数なので、$a_i = p_1^{c_{i,1}} \cdot \dots \cdot p_k^{c_{i,k}}$ と表される。ただし $c_{i,j}$は0もありうる。
つまり、素因数ごとに、$b$を各$a_i$に分配するやり方の場合の数を、$k$個の素因数について掛け合わせたら答えになる。
$b$を$N$人に（0個を含めて）分配するやり方の場合の数は、重複組み合わせ ${}_N H_b$ で数えられる、という。何この記号。
高校数学の美しい物語によると
$n$種類のものから重複を許して$r$個選ぶ場合の数は ${}_{n + r - 1}\mathrm{C}_r$通り。
3種類の味のお菓子があって、どれでもいいから5つあげる、と言われたときの選び方、ということで、これだとよくわからなくなる。
5つの味のないお菓子があるから、2つ仕切りを置いて、左、中、右にそれぞれの味を付けるときのやり方なら、7つのナニカのうち、5つはおかし、2つは仕切り、という置き方になるので、$_{3 - 1 + 5}\mathrm{C}_{5}$ となる。了解。
結局、
\prod_j {}_N \mathrm{H}_{b_j} = \prod_j {}_{N + b_j - 1} C_{b_j}
を求めればよい。
abc110d :: Int -> Int -> Int
abc110d n m = foldl' mul 1 [comb (pred n + b) b | b <- bs]
where
bs = map length $ group $ primeFactors m
comb = mkComb (pred n + maximum bs)
-- primeFactors n ：nを素因数分解し、素因数の昇順のリストを返す
primeFactors :: Int -> [Int]