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')))

感想

C++ の bitset 解法より Haskell の Integer 解法の方が速かった。計算範囲が若干減るからからかな。ところで bitset が想定だということに驚いている人が思ったより多いことに驚いている。

CF Good Bye 2017 G: New Year and Original Order

http://codeforces.com/contest/908/problem/G

解法

上の桁から決めていく桁 DP により解くことができる。ソート済み整数はレピュニット数*1 の和で表せるという性質が役に立つ。たとえば 1122244 という整数の場合

1122244
1111111
  11111
     11
     11

という表現が可能である。$\underbrace{1\dots1}_n=(10^{n+1}-1)/9$ と表せるため、以下の表現も可能である。

$$1122244\times 9 + 9 = 10^8 + 10^6 + 10^3 + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0$$

1122244 の次に 2 を使うとしよう。このとき次のような変化を見せる。

\begin{align}
1122244\times 9 + 9 &= \underline{10^8 + 10^6} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underline{10^9 + 10^7} + 10^3 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

つまり 1 と 2 に対応するレピュニット数が 10 倍されて、それ以外はそのままになっている。ここまでわかると、1,2,3,...,9 に対応するレピュニット数の総和は独立に数え上げられることが分かる。よって、次のようなDPが可能となる。

\begin{align}
1122244\times 9 + 9 &= \underbrace{10^8}_{dp[i][less][1]} + \underbrace{10^6}_{dp[i][less][2]} + \underbrace{10^3}_{dp[i][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 \\
11222244\times 9 + 9 &= \underbrace{10^9}_{dp[i+1][less][1]} + \underbrace{10^7}_{dp[i+1][less][2]} + \underbrace{10^3}_{dp[i+1][less][3]} + 10^0 + 10^0 + 10^0 + 10^0 + 10^0 + 10^0
\end{align}

\begin{align}
dp[i+1][j'][k] \gets \begin{cases}
10\times dp[i][j][k] & \text{$d \le k$} \\
dp[i][j][k] & \text{otherwise}
\end{cases}
\end{align}

ここで $d$ は遷移時に選んだ数字である。

Submission #33803662 - Codeforces

感想

アプローチの掛け方が少ないから少し考えれば解けるような問題だった。
レピュニット数は AtCoder でも最近見たしね。Eの方が圧倒的に難しい。

Zig-Zag Numbers

条件を満たすような○○以上△△以下の整数を求める問題は、上の桁から決めていくDPがよく使われる。DEGwer さんの記事いわく、下から決める方法も上手くいくらしいので、Zig-Zag Numbers と呼ばれる非常に面倒な問題を下からの桁DPで解いてみた。

F - ジグザグ数 (Zig-Zag Numbers)

下から決めていく桁 DP なのだけど、Ordering モノイドを使うと見通しが良いかもしれない。最近の言語とかだと標準で使われている概念なので知っている人も多いと思うが、一応説明しよう。Ordering モノイドというのはモノイドで、$\mathtt{EQ},\mathtt{LT},\mathtt{GT}$ の 3 種類の値を取る。二項演算は以下で定義される。

EQ * x = x
LT * x = LT
GT * x = GT

Haskell だと compare が Ordering を返す。

Prelude> compare 1 2
LT
Prelude> compare 2 2
EQ
Prelude> compare 3 2
GT
Prelude> :t compare
compare :: Ord a => a -> a -> Ordering
Prelude>

これは何者なのかというと、長さの等しい 2 つのリストを辞書順比較するときに自然に現れるものである。 比較する2つのリストを$x=[3,1,4,2,5,9,1], y=[3,1,4,1,5,9,2]$とする。各要素を比較すると $[\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}]$となる。これを$\mathtt{fold}$で畳み込むと何が起きるかというと、foldr なら、

\begin{align}
& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT}
\end{align}

辞書順比較そのものであることが確認できる。モノイドになっているので、当然どのような順序で計算しても結果は同じになる。

上からの桁 DP をする場合、Ordering モノイドは一度 $\mathtt{LT}$ か $\mathtt{GT}$ になったら変化しないので、状態は 2 つあれば区別がつく($\mathtt{GT}$は無視できるため)。しかし下から桁 DP をする場合は、Ordering モノイドはいくらでも変化しうるので 3 状態持たなければならない。

https://beta.atcoder.jp/contests/joi2012yo/submissions/1893277

ARC086 E問題 Smuggling Marbles

E: Smuggling Marbles - AtCoder Regular Contest 086 | AtCoder

解法

縮約解について説明する。よく考えるとマージテク解と本質的に同じ。

深さが等しい頂点をまとめて計算できるのは自明だと思いたい。普通にやると$O(depth\times n)$ だが、各深さごとに木を縮約してあげると $O(n \log n+ n\log (10^9+7))$ で解ける。

縮約するとなぜ計算量が落ちるのかというと、内部節点がかならず分岐を持つ木であれば、内部節点の個数は葉の個数より少ないためである。

f:id:pekempey:20171211161024p:plain

内部節点の個数の評価は二分木で有名だろう。一応説明する。

証明(内部節点の個数の評価)

葉と隣接する内部節点をひとつ選び、それを改めて葉に置き直す操作を考える(図を参照)。頂点がひとつになるまでこの操作を繰り返すと、その回数は内部節点の個数と一致する。この操作によって葉は少なくとも一つ減るため、(内部節点の個数)<(葉の個数)であることが言える。(証明終わり)

f:id:pekempey:20171211161743p:plain

感想

縮約すると計算量が落ちるのには気がついたのだけど、縮約の仕方がまずかったみたいでコンテスト中には通せなかった。縮約は post-order に並べて隣接要素の LCA を取っていくと良いのだが、変な方法でやろうとして失敗した。

CSA #60 E問題

Rust で書き直したのだが Rust で提出できなかった。そういえばクロージャ再帰ってできるんだろうか。グラフを引数に渡すのくどい。

パスを交差させる必要はなくて、互いに素なものだけ考慮すれば良い。これは適当な木DPで解ける――具体的には、状態を(dp0: 親と繋がない)(dp1:親と繋ぐ)として値を (パス数, パス長) とすれば良い。

macro_rules! input {
  ($($x:ident : $t:ty), *) => {
    $(let $x: $t;)*
    {
      let mut s = String::new();
      std::io::stdin().read_line(&mut s).unwrap();
      let mut it = s.trim().split_whitespace();
      $($x = it.next().unwrap().parse().unwrap();)*
      assert!(it.next().is_none());
    }
  };
}

fn dfs(u: usize, p: usize, g: &Vec<Vec<(usize, i32)>>) -> ((i32, i32), (i32, i32)) {
  use std::cmp;

  let mut dp0 = (0, 0);
  let mut dp1 = (1, 0);

  for &(v, c) in &g[u] {
    if v == p { continue }
    let (ep0, ep1) = dfs(v, u, g);

    let x0 = (dp0.0 + ep0.0    , dp0.1 + ep0.1);
    let y0 = (dp1.0 + ep0.0    , dp1.1 + ep0.1);
    let x1 = (dp1.0 + ep1.0 - 1, dp1.1 + ep1.1 + 1);
    let y1 = (dp0.0 + ep1.0    , dp0.1 + ep1.1 + 1);

    if c == 0 {
      dp0 = x0;
      dp1 = y0;
    } else if c == 1 {
      dp0 = x1;
      dp1 = y1;
    } else {
      dp0 = cmp::min(x0, x1);
      dp1 = cmp::min(y0, y1);
    }
  }
  (dp0, dp1)
}

fn main() {
  input!(n: usize);

  let mut g: Vec<Vec<(usize, i32)>> = vec![Vec::new(); n];

  for _ in 1..n {
    input!(a: usize, b: usize, c: i32, d: i32);
    let a = a - 1;
    let b = b - 1;
    let d = if d != 2 { c ^ d } else { d };
    g[a].push((b, d));
    g[b].push((a, d));
  }

  let ((x, y), _) = dfs(0, n, &g);
  println!("{} {}", x, y);
}