ABC 136 F. Enclosed Points - pekempey's blog

https://atcoder.jp/contests/abc136/tasks/abc136_f

I solved problems with F# because I don't want to use C++. Although I prefer to OCaml, I gave up it due to 64bit integers. I use verbose F# because in off-side rule we can't restore indents when carelessly erase them. OCaml is almost as fast as C++, where F# is a little slow regarding IO, so we should prepare own IO functions. Unbuffered IO is really slow.

UPD: I thought F# is available in Codeforces, but it is unavailable now. OCaml is not suitable for contest because OCaml doesn't have binary operators for 64bit integers. In 64bit platform, int has 64 bit precision, but Codeforces is now 32bit.

UPD: The following source code realize Int64 arithmetics. I want to use https://caml.inria.fr/pub/docs/manual-ocaml/manual042.html, but no contests support now. I want to replace all int with Int64, but some functions in the standard library takes int, so I can't.

open Scanf
open Printf

module L = struct
  open Int64
  let ( + ), ( - ), ( * ), ( / ), ( % ), ( ~- ) = add, sub, mul, div, rem, neg
end
let ( ~~ ) = Int64.of_int
let ( !! ) = Int64.to_int

let readint () = scanf " %d" (fun x -> x)
let readint64 () = scanf " %Ld" (fun x -> x)

module M = struct
  let md = 7L
  let ( + ) x y = let z = Int64.add x y in if z < md then z else Int64.sub z md
  let ( - ) x y = let z = Int64.sub x y in if z >= 0L then z else Int64.add z md
  let ( * ) x y = Int64.rem (Int64.mul x y) md
end

type bit = { dat : int64 array }

module BIT = struct
  let make (n : int) : bit = { dat=Array.make (n + 1) 0L }
  let update (bit : bit) (k : int) (v : int64) =
    let { dat } = bit in
    let i = ref (k + 1) in
    while !i < Array.length dat do
      dat.(!i) <- L.(dat.(!i) + v);
      i := !i + (!i land -(!i))
    done
  let query (bit : bit) (k : int) : int64 =
    let { dat } = bit in
    let i = ref k in
    let ans = ref 0L in
    while !i > 0 do
      ans := L.(!ans + dat.(!i));
      i := !i - (!i land -(!i))
    done;
    !ans
end

let () =
  assert (L.(2L + 3L) = 5L);
  assert (L.(2L - 3L) = -1L);
  assert (L.(2L * 3L) = 6L);
  assert (L.(2L / 3L) = 0L);
  assert (L.(2L % 3L) = 2L);
  assert (L.(min 2L 3L) = 2L);
  assert (M.(4L + 5L) = 2L);
  assert (M.(4L - 5L) = 6L);
  assert (M.(4L * 5L) = 6L);
  let bit = BIT.make 10 in
  for i = 0 to 9 do
    BIT.update bit i ~~(i+1)
  done;
  for i = 0 to 10 do
    let i = ~~i in
    assert (BIT.query bit !!i = L.(i * (i + 1L) / 2L))
  done;
  try (BIT.query bit (-1) |> ignore; failwith "") with _ -> ();
  try (BIT.query bit 11 |> ignore; failwith "") with _ -> ();

I used the following template. I'll omit the template.

#nowarn "62"
#light "off"
open System;;
open System.IO;;

let reader = new StreamReader(new BufferedStream(Console.OpenStandardInput ()));;
let writer = new StreamWriter(new BufferedStream(Console.OpenStandardOutput ()));;

let skipSpaces () = while reader.Peek () <= int ' ' do reader.Read () |> ignore done;;
let read f = skipSpaces (); [|while reader.Peek () > int ' ' do yield char (reader.Read ()) done |] |> System.String |> f;;
let readint () = skipSpaces (); let s = if reader.Peek() = int '-' then (ignore (reader.Read()); -1) else 1 in let mutable ans = 0 in while reader.Peek () > int ' ' do ans <- ans * 10 + (reader.Read () - int '0'); done; s * ans;;
let write (s : string) = writer.Write s;;
let writeln (s : string) = writer.WriteLine s;;

(* Write code here *)

reader.Close();;
writer.Close();;

Problem A

let a, b, c = readint (), readint (), readint();;
c - min (a - b) c |> printfn "%d";;

Problem B

I wrote keta function. string >> String.length may be simpler than it.

let rec keta n = if n = 0 then 0 else 1 + keta (n / 10);;
let N = readint ();;
{1..N} |> Seq.filter (fun x -> keta x % 2 = 1) |> Seq.length |> printfn "%d";

Problem C

As looking at elements from left to right, greedily subtract one from each element if we can.

A.[0] <- A.[0] - 1;;
let mutable ans = true;;

for i in 1..N-1 do
  if A.[i-1] > A.[i] then
    ans <- false
  elif A.[i-1] < A.[i] then
    A.[i] <- A.[i] - 1
done;;

(if ans then "Yes" else "No") |> printfn "%s";;

Problem D

It seems that doubling solution is easy to write than I thought. I wrote two pointers.

let S = read string;;
let N = S.Length;;

let mutable i = 0;;
let ans = Array.create N 0;;

while i < N do
  let j = i in
  i <- {i..N} |> Seq.find (fun i -> i = N || S.[i] <> 'R');
  let k = i in
  i <- {i..N} |> Seq.find (fun i -> i = N || S.[i] <> 'L');
  let a, b = k - j, i - k in
  ans.[k-1] <- ((a + 1) / 2 + b / 2);
  ans.[k] <- (a / 2 + (b + 1) / 2);
done;;

ans |> Array.map string |> String.concat " " |> writeln;;

Problem E

Once we notice that the sum doesn't change, we almost have solved this problem. That's a lie. Greedy part is not trivial for me.

let divisors x = Seq.initInfinite ((+) 1) |> Seq.takeWhile (fun i -> i * i <= x) |> Seq.filter (fun i -> x % i = 0) |> Seq.collect (fun i -> seq [i; x / i]);;

let N, K = readint (), readint ();;
let A = Array.init N (ignore >> readint);;

let f d =
  let x = Array.init N (fun i -> A.[i] % d) |> Array.sort in
  let mutable i = 0 in
  let mutable j = N - 1 in
  let mutable souwa = 0 in
  while i < j do
    let tukau = min x.[i] (d - x.[j]) in
    souwa <- souwa + tukau;
    x.[i] <- x.[i] - tukau;
    x.[j] <- x.[j] + tukau;
    if x.[i] = 0 then i <- i + 1;
    if x.[j] = d then j <- j - 1;
  done;
  souwa <= K;;

divisors (Array.sum A) |> Seq.filter f |> Seq.max |> printf "%d";;

Problem F

If we can notice that x[i]!=x[j] and y[i]!=y[j], this problem become a little easier. However, we can solve this problem without this constraint (My first solution is so).
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>] is too long.

let MOD = 998244353;;
type Mint = Mint of int
  with
    static member (+) (Mint x, Mint y) = Mint (let z = x + y in if z < MOD then z else z - MOD)
    static member (-) (Mint x, Mint y) = Mint (let z = x - y in if z >= 0 then z else z + MOD)
    static member (*) (Mint x, Mint y) = int64 x * int64 y % int64 MOD |> int |> Mint
    override this.ToString() = match this with Mint x -> x.ToString()
  end;;

type BIT = { dat : int [] }
[<CompilationRepresentation(CompilationRepresentationFlags.ModuleSuffix)>]
module BIT =
  begin
    let create n : BIT = { dat = Array.create (n + 1) 0 }
    let update ({dat=dat} : BIT) (k : int) (v : int) =
      let mutable i = k + 1 in
      while i < Array.length dat do dat.[i] <- dat.[i] + v; i <- i + (i &&& -i) done
    let query ({dat=dat} : BIT) (k : int) : int =
      let mutable i = k in
      let mutable ans = 0 in
      while i > 0 do ans <- ans + dat.[i]; i <- i - (i &&& -i) done;
      ans
  end;;

let N = readint ();;
let X, Y = Array.init N (fun _ -> readint (), readint ()) |> Array.sort |> Array.unzip;;
let YD = Y |> Array.distinct |> Array.sort |> Array.mapi (fun i x -> x, i) |> Map.ofArray;;
for i in 0..N-1 do Y.[i] <- YD.[Y.[i]] done;;
let L = BIT.create YD.Count;;
let R = BIT.create YD.Count;;
for y in Y do BIT.update R y 1 done;;

let two = Array.replicate N (Mint 2) |> Array.scan (*) (Mint 1);;

let mutable ans = two.[N] * (Mint N);;
for i in 0..N-1 do
  BIT.update R Y.[i] (-1);
  let d = BIT.query L Y.[i] in
  let c = BIT.query R Y.[i] in
  let a = i - d in
  let b = (N-1-i-c) in
  [Mint 1;
  two.[a] - Mint 1; two.[b] - Mint 1; two.[c] - Mint 1; two.[d] - Mint 1;
  (two.[a] - Mint 1) * (two.[b] - Mint 1);
  (two.[b] - Mint 1) * (two.[c] - Mint 1);
  (two.[c] - Mint 1) * (two.[d] - Mint 1);
  (two.[d] - Mint 1) * (two.[a] - Mint 1)] |> List.iter (fun x -> ans <- ans - x);
  BIT.update L Y.[i] 1;
done;;
printfn "%O" ans;;