April Challenge 2018
Chef 側の解説がまだ出てないので、それ読んで思うものがあったら更新します。
CHEFAT:
この制約なら SIMD O(n^2) 通る。そうは言っても 2 ケースほど TLE になってしまったので、平方分割＋遅延評価で平均的に速くなるようにした。
多くの提出は $\log(1-x)=-x-x^2/2-x^3/3-...-x^{100}/100$ で近似してる。
最後に exp とったときの誤差は大丈夫なのかなと思ったけど $e^{x+\epsilon} - e^x \approx \epsilon e^x$ なので大丈夫そう。
SSPLD:
固有多項式を埋め込む（そんなに次数は大きくない）。具体値を埋め込むとコード長制限に引っかかるため実行時に計算。多項式乗算・剰余は FFT で高速にやらないと厳しい。多くの提出は hadamard transform を使ってるように見える。確かにできそう。
11 変数多項式 f(x,y0,...,y9) を FFT する感じ？f(x,y0,...,y9) にある多項式を掛けることで遷移を表現できる（下の桁から値を決めていくわけだが、遷移関数は周期的、周期は 10^k mod s に依存）。そして S×2×2×…×2 の FFT をしておけば係数の積から値の積に変換できて、解ける。（S に関して言うと 2 冪じゃないから FFT じゃないけど（高速ではない））→よく考えたらNTTなのでSでできない。いや体拡大でできるかもしれないけど、そうではないんだろう。
CodeChef March Challenge 2018
PSHTRG
Q=1 で考えてみよう。これは，数列をソートして最大 3 つを見る，それで駄目なら次の 3 つを見るというのを繰り返すことで求められる。この繰り返しが O(log max a) 回しか起きないことに気がつくと，50th max 程度まで保持するセグメント木があれば解けることがわかる。最悪ケースはフィボナッチ数列だろう。
実装：https://gist.github.com/pekempey/829c0d930e2a992a2041e8f363d2f8be
CHEFKNN
最終的な結果が K 色を含むようなものの総数は，第一種スターリング数によって S(N+1, N+1-K) と表せる。自分はこの事実に実験で気がついたが，おそらくは組合せ論的に導けるものなのだろう。この事実に気がつければ，やるべきことは第一種スターリング数の計算の高速化のみとなる。第一種スターリング数は rising factorial の展開係数として現れるので rising factorial を高速に展開すればよい。分割統治でやると O(n log2 n) だが，少し工夫すると O(n log n) になる。多分 100pts は O(n log n) のためなんだろうけど，変な O(n log2 n) が通ってるように見えるな。
実装：https://gist.github.com/pekempey/eeadc0c5306db890a8d9a742d2f433fd
ちなみに自分のコードは T=5, N=106, K=106 だと 5 sec 以上かかる。T=4 ですら 5 sec 以上掛かる。明らかに最悪ケースが入っていない。展開時の係数を求める際に，具体値を求めて係数表現に戻すという方法もあるらしい。これなら FFT 1 回でいいし速そう。
CUTTREE
与えられたスコアは，頂点 u と頂点 v が連結ならば 1 増えるようなスコアと言い換えられる。これに気がつけば部分点がとれる。満点解法はこれを高速化するだけである。高速化するには距離が等しい頂点対をまとめて計算すればよい。距離 d の頂点対の総数を計算するには重心分解と畳み込みが使える。これを求め終わった後に，もう一度畳み込みを行って最終的な答えを得る。しかしこの畳み込みは任意 mod のものである。任意 mod の畳み込みは様々な方法があって，Karatsuba 法や NTT 9 回，FFT 4 回などがある。
実装：https://gist.github.com/pekempey/4782989f6417ad6de97a6864ca33e39f
公式解説
March 2018: Questions Tagged With march18 - CodeChef Discuss
CHEFKNN: CHEFKNN - Editorial - CodeChef Discuss
CHEFTREE: CUTTREE - Editorial - CodeChef Discuss
ARC091 F Strange Nim
https://arc091.contest.atcoder.jp/tasks/arc091_d
K を固定して Grundy 数 g(n) を考える。実験すると g(Kn)=n であることに気づける。g(Kn)=n ということは，その直前 n 個を見ると 0..n-1 の順列になっている。これに気がつくと漸化式が見える。
実験から漸化式まで導く方法が解説放送でされているが，自分は気づかなかった。高速化パートもそれはそれで難しいんだけど，時間を掛ければわかるタイプ。
図：https://gist.github.com/pekempey/2893024239ec6aa14e83805fa890364b
yukicoder 661, 662, 663, 664, 665
最近いろんな作業を Rust で書いてるんですが、Rust やってると Haskell が書きたくなってくる。664はまだです。
661 ハローキティはりんご3個分
import Control.Monad main = getLine >> getContents >>= mapM_ (putStrLn . solve . read) . lines solve n | n `mod` 40 == 0 = "ikisugi" | n `mod` 8 == 0 = "iki" | n `mod` 10 == 0 = "sugi" | otherwise = show (n `div` 3)
662 スロットマシーン
import Data.List import Data.Maybe import Control.Monad main = do dic <- replicateM 5 readKV (n1, a) <- readReel (map fst dic) (n2, b) <- readReel (map fst dic) (n3, c) <- readReel (map fst dic) -- [0] [1] [2] [3] [4] -- 000 0 0 -- 000 0 0 -- 000 0 0 let cnt = map (\k -> let x = a!!k; y = b!!k; z = c!!k in 5*x*y*z) $ [0..4] let ans = sum $ zipWith (*) cnt (map snd dic) print $ fromIntegral ans / fromIntegral (n1 * n2 * n3) mapM_ print cnt readKV :: IO (String, Int) readKV = do [k, v] <- words <$> getLine return (k, read v) readReel :: [String] -> IO (Int, [Int]) readReel dic = do n <- readLn :: IO Int x <- replicateM n (fromJust . flip elemIndex dic <$> getLine) return (n, [length . filter (==i) $ x | i <- [0..4]])
663 セルオートマトンの逆操作
リストモナドの bind を連鎖させれば全列挙できるけど、それだと指数時間になってしまう。bind 後に重複除去をすると計算量が落ちる（いまさらなんだけど、groupBy する前にソートしないと危険）。dp[i] から dp[i+1] が作れる系の DP はたいていこう書けると思う。
import Data.List import Control.Monad main = do n <- readLn :: IO Int a <- replicateM n readLn :: IO [Int] print $ solve a md :: Int md = 10^9 + 7 type Stat = (Int, Int, Int, Int) solve :: [Int] -> Int solve a = let b = foldl' g [((i, j, i, j), 1) | i <- [0,1], j <- [0,1]] a in modsum . map snd . filter (\((h1, h2, x, y), _) -> h1 == x && h2 == y) $ b where g :: [(Stat, Int)] -> Int -> [(Stat, Int)] g acc a = compress (acc >>= f a) f :: Int -> (Stat, Int) -> [(Stat, Int)] f a ((h1, h2, x, y), cnt) = [((h1, h2, y, z), cnt) | z <- [0, 1], rule x y z == a] compress :: [(Stat, Int)] -> [(Stat, Int)] compress a = map f . groupBy (\x y -> fst x == fst y) $ a where f :: [(Stat, Int)] -> (Stat, Int) f x = let key = fst (head x); val = modsum . map snd $ x in (key, val) modsum :: [Int] -> Int modsum = foldl' (\x y -> (x + y) `mod` md) 0 rule :: Int -> Int -> Int -> Int rule 0 0 0 = 0 rule 0 0 1 = 1 rule 0 1 0 = 1 rule 0 1 1 = 1 rule 1 0 0 = 0 rule 1 0 1 = 1 rule 1 1 0 = 1 rule 1 1 1 = 0
665 Bernoulli Bernoulli
F# だと演算子の優先順位がいい感じに自動生成されるんだけど、Haskell でその感覚でやったらハマった（どういう順序になってるんでしょう）。
import Data.List (foldl', scanl) md :: Int md = 10^9 + 7 -- sometimes ambigious infixl 6 +++ (+++) :: Int -> Int -> Int (+++) a b = (a + b) `mod` md infixl 7 *** (***) :: Int -> Int -> Int (***) a b = a * b `mod` md infixr 8 ^^^ (^^^) :: Int -> Int -> Int (^^^) a b | b == 0 = 1 | odd b = a *** a ^^^ (b - 1) | otherwise = (a *** a) ^^^ (b `div` 2) modinv :: Int -> Int modinv a = a ^^^ (md - 2) infixl 7 /// (///) :: Int -> Int -> Int (///) a b = a *** modinv b prodmod :: [Int] -> Int prodmod = foldl' (***) 1 -- p/(x-0) p/(x-1) -- vvvvvvvvvvvvvvvvvvvv vvvvvvvvvvvvvvvvvvvv -- (x-1)(x-2)...(x-n+1) (x-0) (x-2)(x-3)...(x-n+1) -- --------------------- a[0] + ... ---------------------------- a[1] + ... -- (0-1)(0-2)...(0-n+1) (1-0) (1-2)(1-3)...(1-n+1) -- ^^^^^ ^^^^^^^^^^^^^^^^^^^^ -- [L] [R] lagrange :: [Int] -> Int -> Int lagrange a x | x < n = a !! x | otherwise = let (sm, _, _, _) = foldl' f (0, 0, 1, q) a in sm where n = length a p = prodmod [(x - i) | i <- [0..n-1]] q = prodmod [-i | i <- [1..n-1]] f :: (Int, Int, Int, Int) -> Int -> (Int, Int, Int, Int) f (sm, k, l, r) ak = (nextSm, k + 1, nextL, nextR) where nextSm = sm +++ ak *** p /// (l *** r *** (x-k)) nextL = l *** (k + 1) nextR = r /// negate (n - 1 - k) computeSmall :: Int -> [Int] computeSmall k = scanl f 0 [1..k + 1] where f s x = s +++ (x ^^^ k) solve :: Int -> Int -> Int solve n k = lagrange (computeSmall k) (n `mod` md) main = do [n, k] <- map read . words <$> getLine :: IO [Int] print $ solve n k
SRM 729 Med. FrogSquare
問題概要
n × n のグリッドが与えられる。スタート地点は (sx,sy) でゴール地点は (gx,gy) である。ユークリッド距離が d 以上の点に移動できる。移動回数の最小値を求めよ。ただし到達不可能な場合は -1 を出力せよ。
誤解法
四隅だけ使えばよく，到達できるなら 3 手で行ける。
解法
最初と最後以外は周上以外の点に移動する必要はない。周上の点の個数のオーダーは O(n) なので，単純な BFS でも計算量は O(n2) となる。
class FrogSquare { public: int minimalJumps(int n, int d, int sx, int sy, int tx, int ty) { vector<pair<int, int>> g; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (i == 0 || i == n - 1 || j == 0 || j == n - 1) { g.emplace_back(i, j); } } } g.emplace_back(tx, ty); queue<pair<int, int>> q; q.emplace(sx, sy); vector<vector<int>> dist(n, vector<int>(n, -1)); dist[sx][sy] = 0; while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (auto p : g) { int xx = p.first; int yy = p.second; if ((xx - x) * (xx - x) + (yy - y) * (yy - y) >= d * d && dist[xx][yy] == -1) { dist[xx][yy] = dist[x][y] + 1; q.emplace(xx, yy); } } } return dist[tx][ty]; } };
図
\documentclass[margin=1cm]{standalone} \usepackage{tikz,newtxtext,newtxmath} \begin{document} \begin{tikzpicture}[ foo/.style={fill,circle,inner sep=0,minimum size=2mm}, ] \clip (-1,-1) rectangle (11,11); \draw [help lines] (0,0) grid (10,10); \node [foo] (z) at (8,8) {}; \node [foo] (a) at (0,0) {}; \node [foo] (b) at (10,5) {}; \node [foo] (c) at (0,10) {}; \node [foo] (d) at (8,2) {}; \draw (8,8) circle [radius=11cm]; \draw (0,0) circle [radius=11cm]; \draw (10,5) circle [radius=11cm]; \draw (0,10) circle [radius=11cm]; \draw [->,>=latex,thick] (z) -- (a); \draw [->,>=latex,thick] (a) -- (b); \draw [->,>=latex,thick] (b) -- (c); \draw [->,>=latex,thick] (c) -- (d); \end{tikzpicture} \end{document}
感想
自分の部屋では med の反例を作れる人がいなかったので，もし反例が作れてたらかなり稼げた（残念）。四隅の反例はすぐに作れたんだけど，4 手の例を作るのに手間取った。
