A - Happy Birthday!

問題 ABC100A

シグネチャを決める。

abc100a :: Int -- A
        -> Int -- B
        -> Bool -- 答え
abc100a a b = a <= 8 && b <= 8

隣り合うものを取らないようにするには、一つおきに分けるしかない。
8個を超えて取ろうとすると、相手の分まで手を出すことになる。
$A + B > 16$ は問題の条件から確認の必要はない。

B - Ringo's Favorite Numbers

問題 ABC100B

シグネチャを決める。

import Data.Bool

abc100b :: Int -- D
        -> Int -- N
        -> Bool -- 答え
abc100b d n = bool n 101 (n == 100) * 100 ^ d

$N \cdot 100^D$ と思いきや、$N= 100$ のときもう一度100で割れてしまうのでこれを飛ばす必要がある罠。

C - *3 or /2

問題 ABC100C

シグネチャを決める。

abc100c :: Int   -- N
        -> [Int] -- a_i
        -> Int   -- 答え

黒板に書いてある数を一斉に半分にする回数を数える、という類題を見た覚えがあるなぁ。
3倍しても2で割れる回数は変わらないので、$a_i$ を2で割れる回数の合計をとる。

ビットトリックで、$x$ と $x - 1$ の xor をとる方法で下位桁に連続するビット0の個数を数えると、計算量はどうなるんだろう。popCount が命令にあれば $O(1)$ かな？

結果

import Data.Bits

abc100c :: Int -> [Int] -> Int
abc100c _n as = sum [pred $ popCount $ xor a $ pred a | a <- as]

公式解説より

ユーザ解説のお二人は、問題の難易度に合わせて、普通に2で割る回数を数えている。
公式解説に方法だと計算量は $O(\log(\max(a_i)))$ とある。

続きに不穏なことが書いてある。
2で割れる回数を二分法で求めることにより計算量 $O(\log \log(\max(a_i)))$で求める方法もあると。
$a_i \leq 10^9$ と上限が決まっているので、最大で29回2で割ることができる。
$k = 16,8,4,2,1$ について順に、$a_i$ が $2^k$ で割り切れるなら割って、
割ることのできた$k$を足し合わせると答えになる、という仕組みか。

コードにするとこうなる：

abc100c :: Int -> [Int] -> Int
abc100c _n as = sum [count a | a <- as]

count x = sum $ snd $ mapAccumL step x [(k, 2^k) | k <- [16,8,4,2,1]]
  where
    step v (k,k2) =
      case divMod v k2 of
        (q, 0) -> (q, k)
        _      -> (v, 0)

といっても、計算機のビット幅に収まる数ならxorテクニックで $O(1)$ でする方が速いし、$O(\log X)$ を $O(\log \log X)$ にして性能向上というのは $X$ が大きな文脈でないと意味がない。たかだか32だの64だのといったサイズでは。かといって計算機のビット幅を超えるような$X$を相手にするときにこのやり方でどうにかなるかというと、多分どうにもならない。

D - Patisserie ABC

シグネチャを決める。

abc100d :: Int   -- N
        -> Int   -- M
        -> [[Int]] -- x_i,y_i,z_i
        -> Int   -- 答え

最終的に小計の絶対値をとるときに、負の数で符号反転するか、そのままにするかが決まる。その8とおりの世界線を全てやってみて、最大になるものが本当の結末、とする。

最後は結局足し合わせるので、3つのパラメータの符号を固定した後は足してしまった$N$個の値から、$M$個選んで最大になるものを選べばよい。
とここでうっかりDPを使って頑張って解くこともできるが、降順ソートして上位$M$個で十分。

結果

import Data.List

abc100d :: Int -> Int -> [[Int]] -> Int
abc100d _n m xyzs = maximum                   -- 8通りのやり方の最大値
    [ sum . take m . sortBy (flip compare) .  -- 上位M個を足し合わせる
      map (sum . zipWith ($) sigfuns) $ xyzs  -- 各xi,yi,ziの符号を調整して足して
    | sigfuns <- replicateM 3 [id, negate] ]  -- 符号反転するかどうか8通りのやり方

クイックセレクト

公式解説ではここで、
列全体をソートせずとも、任意のM番目の値を最悪計算量 $O(N)$ で求めるアルゴリズムを使うことで全体も $O(N)$ で解ける、と言っている。

最悪計算量が $O(N^2)$ になることで有名なクイックソートの1ステップを実行すると、列がピボットとの大小で2分割される。大きい方がM個以下なら、それらはそれ以上ソートせずとも上位M個には含まれると確定する。なので小さい方からあと足りない分を再帰的に取り出す。
逆に、大きい方がM個より多い場合、小さい方は確実に上位M個には含まれないので放置して、大きい方だけ再帰的に繰り返す。

ただしピボットの取り方に工夫をこらさないとダメ。そこで「中央値の中央値」を使う、という話になっている。

• Select() は、列のM番目の要素をクイックセレクトにより見つける
  • Pivot() に列を渡してピボットを選ぶ
• Pivot() は、列の中央値の中央値を求める
  • 要素を5つごとに分割し、5つの値ごとの中央値を$O(1)$で求めた結果列の中央値を Select()で選ぶ

という相互再帰をする、とある。これは、理論計算量は小さくても実装が面倒なやつでは…

この問題では対象が整数なので、最大値と最小値の平均をとるとか無精すると、最小値近くの値ばっかりとか意地悪される可能性がある。

まぁ我々は、これを自作しなくとも Data.Vector.Algorithms.Intro.select(By) があるので利用しよう。

ということで selectBy (flip compare) を使えば終わりなのだけど、解説のとおりに「M番目の値」だけが得られる場合、実はまだ話が終わらない。その値はユニークとは限らないので、同じ値がM番目以降にも並んでいるかもしれない。すると

値 A が求まった後は求めた値より大きい値の合計を計算すれば良い

（超、ではなく以上、と解釈して）では数えすぎる。「より大きい値」の個数と合計を求め、個数の不足ぶんを A の繰り返しで補う、というロジックが必要。

import qualified Data.Vector.Unboxed as UV
import qualified Data.Vector.Algorithms.Intro as VAI

abc100d :: Int -> Int -> [[Int]] -> Int
abc100d n m xyzs = maximum
    [ UV.sum . UV.take m . UV.modify (\v -> VAI.selectBy (flip compare) v m) .
      UV.fromListN n . map (sum . zipWith ($) sigfuns) $ xyzs
    | sigfuns <- replicateM 3 [id, negate] ]

リスト版が6msだったのが3msになったよ！