AGC 020 A..C問題
A問題
端に追いやられたら負けである。よって相手に近寄るように移動するのが最適行動になる。この戦略を実際にシミュレートすることで答えが得られる。
main = do [n, a, b] <- map read . words <$> getLine putStrLn $ turnA n a b turnA :: Int -> Int -> Int -> String turnA n a b | a + 1 /= b = turnB n (a + 1) b | a /= 1 = turnB n (a - 1) b | otherwise = "Borys" turnB :: Int -> Int -> Int -> String turnB n a b | b - 1 /= a = turnA n a (b - 1) | b /= n = turnA n a (b + 1) | otherwise = "Alice"
B問題
$i$ 番目のラウンドは関数 $f_i(x)=\lfloor x/a_i \rfloor a_i$ で表せる。初期人数を $x$ としたとき $f_{K - 1} \circ f_{K - 2} \circ \cdots \circ f_0 (x)=2$ となる $x$ の最大値・最小値を求めれば良い。$f_i$ は単調増加関数なので、合成しても単調増加関数である。よって、$x$が取りうる範囲は二分探索により求めることができる。
import Data.List (foldl') main = do _ <- getLine a <- map read . words <$> getLine let l = binarySearch ((>=2) . foo a) 0 (10^18) let r = binarySearch ((>=3) . foo a) 0 (10^18) if l < r then putStrLn $ show l ++ " " ++ show (r - 1) else print (-1) foo :: [Int] -> Int -> Int foo a x = foldl' (\a b -> a `div` b * b) x a binarySearch :: (Int -> Bool) -> Int -> Int -> Int binarySearch f l r | r - l == 1 = r | otherwise = let m = div (l + r) 2 in if f m then binarySearch f l m else binarySearch f m r
C問題
空集合も考慮する。サンプル1で作れる値は {0,1,1,2,2,3,3,4} である。$i$ 番目の値と $2^n-1-i$ 番目の値の和が一定であることは、互いに補集合の関係になっていることから言える。この対称性から、中央値は S を unique して中央値を取ったものと一致する。もう少し考えると、数列 $a$ の総和を $s$ としたとき $\lceil s/2 \rceil$ となる値が中央値であることが言える。
C++ であれば bitset を用いた $O(n^2\max a/64)$ の解法で十分間に合う。多倍長整数が使える言語であれば、多倍長整数の shift, or は高速であることが多いため間に合う。
import Data.List (foldl', find) import Data.Bits (shiftL, (.|.), testBit) main = do _ <- getLine a <- map read . words <$> getLine let f = foldl' (\a x -> a .|. shiftL a x) 1 a :: Integer let s = sum a let (Just ans) = find (\x -> testBit f x) [(s + 1) `div` 2 ..] print ans
input() a = list(map(int, input().split())) dp = 1 for x in a: dp |= dp << x s = sum(a) dp >>= (s + 1) // 2 dp <<= (s + 1) // 2 dp = bin(dp) print(len(dp) - len(dp.rstrip('0')))
