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

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 手で行ける。

反例。4 手の例。四隅だけでは到達不可能。

解法

最初と最後以外は周上以外の点に移動する必要はない。周上の点の個数のオーダーは 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 手の例を作るのに手間取った。

ARC 089 D. Checker

https://beta.atcoder.jp/contests/arc089/tasks/arc089_b

この解説では、座標を(横,縦)で表している。

$(x,y)$ が黒であることと $(x \bmod 2K, y \bmod 2K)$ が黒であることは同値である。
$(x,y)$ が白であることと $(x+K,y)$ が黒であることは同値である。


f:id:pekempey:20180124212659p:plain
図1. 同値変換によって $2K \times 2K$ の領域に条件を移動できる($K=2$)。白の条件は黒の条件に言い換えられるため、黒しかない場合に還元できる。


f:id:pekempey:20180124191918p:plain
図2. 盤面をコピーすることで範囲が単純になる。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> s(4 * k + 1, vector<int>(4 * k + 1));

  for (int i = 0; i < n; i++) {
    int x, y;
    char c;
    cin >> x >> y >> c;
    if (c == 'W') {
      x += k;
    }
    x %= 2 * k;
    y %= 2 * k;
    s[x + 1][y + 1]++;
    s[x + 2 * k + 1][y + 1]++;
    s[x + 1][y + 2 * k + 1]++;
    s[x + 2 * k + 1][y + 2 * k + 1]++;
  }

  for (int i = 0; i + 1 < s.size(); i++) {
    for (int j = 0; j + 1 < s.size(); j++) {
      s[i + 1][j + 1] += s[i + 1][j] + s[i][j + 1] - s[i][j];
    }
  }

  auto sum = [&](int y, int x, int n) {
    return s[y + n][x + n] - s[y + n][x] - s[y][x + n] + s[y][x];
  };

  int ans = 0;
  for (int i = 0; i < 2 * k; i++) {
    for (int j = 0; j < 2 * k; j++) {
      int s1 = sum(i, j, k);
      int s2 = sum(i + k, j + k, k);
      ans = max(ans, s1 + s2);
    }
  }
  cout << ans << endl;
}

図1のコード

\documentclass[dvipdfmx,margin=1cm]{standalone}

\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{tikz}

\usetikzlibrary{calc}
\usetikzlibrary{patterns}

\begin{document}

\begin{tikzpicture}[yscale=-1,
  foo/.style={circle,inner sep=0.07cm},
  ]

  \foreach \x/\y in {2/0, 6/0, 0/2, 4/2, 2/4, 6/4, 0/6, 4/6} {
    \draw[fill=black!10] (\x,\y) rectangle ++(2,2);
  }

  \draw[help lines] (-0.5,-0.5) grid (8.5,8.5);
  \draw[step=2] (-0.5,-0.5) grid (8.5,8.5);
  \draw[ultra thick] (0,0) rectangle (4,4);

  \node[fill=black,foo] (a) at ($(0,3) +(.5,.5)$) {};
  \node[fill=black,foo] (b) at ($(4,7) +(.5,.5)$) {};
  \draw[-latex,very thick] (b) to node [auto,xshift=-0.4cm] {$\bmod 2K$} (a);

  \node[fill=white,draw=black,foo] (c) at ($(5,1) +(.5,.5)$) {};
  \node[fill=black,foo] (d) at ($(7,1) +(.5,.5)$) {};
  \node[fill=black,foo] (e) at ($(3,1) +(.5,.5)$) {};
  \draw[-latex,very thick] (c) to node [auto] {$+K$} (d);
  \draw[-latex,very thick] (d) to [bend right=30] node [auto,xshift=-0.1cm] {$\bmod 2K$} (e);

  \draw (0,0) to [very thick,bend right=20] node [auto] {$2K$} (4,0);
  \draw (0,0) to [very thick,bend left=20] node [auto,swap] {$2K$} (0,4);

\end{tikzpicture}

\end{document}

図 2 のコード

% pgfmanual v3.0.1a
\documentclass[dvipdfmx,margin=1cm]{standalone}

\usepackage{newtxtext}
\usepackage{newtxmath}
\usepackage{tikz}

\usetikzlibrary{calc}
\usetikzlibrary{patterns}
\begin{document}

\begin{tikzpicture}[yscale=-1]
  \begin{scope}[shift={(0,2)},local bounding box=scope1]
    \draw [help lines] (-0.5,-0.5) grid (4.5,4.5);
    \draw [step=2] (-0.5,-0.5) grid (4.5,4.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    % pattern=crosshatch dots -- See pgfmanual p.666
    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (0,0) rectangle (1,2);
    \draw [ultra thick,pattern=crosshatch dots] (3,0) rectangle (4,2);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \begin{scope}[shift={(10,0)},local bounding box=scope2]
    \draw [fill=black!20] (0,0) rectangle (4,4);
    \draw [fill=red!20] (4,0) rectangle (8,4);
    \draw [fill=blue!20] (0,4) rectangle (4,8);
    \draw [fill=green!20] (4,4) rectangle (8,8);

    \draw [help lines] (-0.5,-0.5) grid (8.5,8.5);
    \draw [step=2] (-0.5,-0.5) grid (8.5,8.5);
    \draw [very thick] (0,0) rectangle (4,4);

    \foreach \dy/\dx in {0/0, 0/4, 4/0, 4/4} {
      \foreach \x/\y in {1/0, 3/1, 2/3}{
        \draw [fill=black,circle] ($(\x,\y) + (.5,.5) + (\dx,\dy)$) circle[radius=0.1cm];
      }
    }

    \draw [-latex,ultra thick] (2,0) to [bend right=30] node [auto] {Copy} (6,0);
    \draw [-latex,ultra thick] (0,2) to [bend left=30] node [auto,swap] {Copy} (0,6);
    \draw [-latex,ultra thick] (2,8) to [bend left=30] node [auto,swap] {Copy} (6,8);

    \draw [ultra thick,pattern=crosshatch dots] (1,2) rectangle (3,4);
    \draw [ultra thick,pattern=crosshatch dots] (3,4) rectangle (5,6);

    \draw [-latex,line width=0.1cm] (0.5,1.5) -- (1,2);
  \end{scope}

  \draw [-latex,ultra thick] ($(scope1.east)+(0.5,0)$) -- node [auto] {Transform} ($(scope2.west)-(0.5,0)$);

\end{tikzpicture}

\end{document}