ABC298 F問題 Rook Score

atcoder.jp

巨大なマス目から、(R,C) を選び、R行 または C列 のマス目の総和の問題です。
あらかじめ、各行の総和と各列の総和を計算しておくと、問題の値は、

と求められます。
ほとんどのマス目は 0 であることから、0以外の値のある行と列のみをリストアップします。
行・列を総和が大きい順に並び変えて、 の最大値を求めていきます。
列方向に探索するときに、 の値がそれまでの最大値以下であれば、それ以降の列は調べる必要が無くスキップすることができます。
また、(R,C)マスの値をすぐに取り出せるように、(R,C)をキーとする辞書型としておきます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()

  A = Dict()
  row = Dict()
  col = Dict()

  for k = 1:N
    r,c,x = readInts()
    A[ [r c] ] = x

    # r 行の和
    y = 0
    if haskey(row,r)
      y = row[r]
    end
    row[r] = x + y

    # c 列の和
    y = 0
    if haskey(col,c)
      y = col[c]
    end
    col[c] = x + y
  end

  nrow = length(row)
  ncol = length(col)

  # 和が大きい順に並び替え
  rows = sort(collect(row), by=x -> x[2], rev=true)
  cols = sort(collect(col), by=x -> x[2], rev=true)

  ans = 0

  for i = 1:nrow
    for j = 1: ncol
      v = rows[i].second + cols[j].second
      if ans >= v
        break
      end
      r = rows[i].first
      c = cols[j].first
      if haskey(A, [r c])
        v -= A[ [r c] ]
      end
      if v > ans
        ans = v
      end
    end
  end

  println(ans)

end  # function solve

# main
solve()

ABC298 E問題 Unfair Sugoroku

atcoder.jp

動的計画法で、サイコロを 回振ったあとに地点 にいる確率を とします。
さらに1回サイコロを振ることによって地点 のいずれかに確率で到達します。(地点が N より大きくなる時は、N に置き換えます。)
このことから、


…

と確率の加算を行います。これをループ処理することで、 回後にゴールに到達している確率が求められます。

高橋君と青木君について、この確率を求めます。
この確率は累積確率なので、その差分が高橋君が 回目に初めてゴールに到達する確率になります。
このとき、青木君がゴールに到達していない確率は 1 から累積確率を引いた値で、これらの確率の積で高橋君が回目にゴールに到達したときに高橋君が勝つ確率が求められます。
これを についてループすることで高橋君が勝つ確率が求められます。

コード例 (Julia)

_MOD = 998244353

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N, A, B, P, Q = readInts()

  p = invmod(P,_MOD)  # 1/P
  q = invmod(Q,_MOD)  # 1/Q

  taka = zeros(Int,N+1,N)
  aoki = zeros(Int,N+1,N)

  taka[1, A] = 1
  aoki[1, B] = 1

  # 高橋君の DP
  for i = 2:N
    for j = 1:N
      if taka[i-1, j] == 0
        continue
      end
      for k = 1 : P
        n = min(j+k, N)
        taka[i, n] += taka[i-1, j] * p
        taka[i, n] %= _MOD
      end
    end
  end

  # 青木君の DP
  for i = 2:N
    for j = 1:N
      if aoki[i-1, j] == 0
        continue
      end
      for k = 1 : Q
        n = min(j+k, N)
        aoki[i, n] += aoki[i-1, j] * q
        aoki[i, n] %= _MOD
      end
    end
  end

  ans = 0

  for i = 2:N
    prob = taka[i, N] - taka[i-1, N]  # 高橋君が i 回目にゴールに着く確率
    pa = 1 - aoki[i-1, N]             # 青木君がゴールに着いていない確率
    ans += (prob * pa) % _MOD
    ans %= _MOD
  end

  if ans < 0
    ans += _MOD
  end

  println(ans)

end  # function solve

# main
solve()

ABC298 D問題 Writing a Numeral

atcoder.jp

各クエリで を数とみなした値を更新していきます。
クエリ1は、値を10倍してを加えます。
クエリ2は、先頭の数字にをかけた値を引きます。
このクエリのために、追加する数字を配列に記録することと、をあらかじめ計算しておきます。
それぞれの値は、mod 998244353 での値とします。
クエリ3は、更新している値をそのまま出力するだけです。

コード例 (Julia)

_MOD = 998244353

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  Q = readInt()

  ord = zeros(Int,600001)   # 10^N
  ord[1] = 1
  for i = 1:600000
    ord[i+1] = (ord[i] * 10) % _MOD
  end

  S = zeros(Int,600001)
  S[1] = 1
  ans = 1
  head = 1
  tail = 2

  for q = 1:Q
    A = readInts()
    if A[1] == 1
      x = A[2]
      ans = (ans * 10 + x) % _MOD
      S[tail] = x
      tail += 1
    elseif A[1] == 2
      n = tail - head
      a = (ord[n] * S[head]) % _MOD
      ans -= a
      if ans < 0
        ans += _MOD
      end
      head += 1
    elseif A[1] == 3
      println(ans)
    end
  end

end  # function solve

# main
solve()

ABC297 F問題 Minimum Bounding Box 2

atcoder.jp

期待値の求め方

マスの数は個で、ここから 個 の選び方は、 通りです。
選んだマスの位置を とすると、スコアは となります。

スコアが になる選び方が 通りあるとすると、スコアの期待値は

と計算されます。ここから を求めることを考えていきます。

場合の数の計算

縦 マス、横マスの固定範囲内で マスの選び方は 通りですが、これにはスコアが より小さな選び方も含んでいます。
そこで外側の4辺について、辺上に選んだマスがある場合(〇)とひとつも無い場合(×)で分類します。これによってマスの選び方を 種類に分類できます。

求めたいのは、①の場合の数です。

選び方全体

辺A のマスを選ばない選び方

辺C のマスを選ばない選び方

辺B のマスを選ばない選び方

辺D のマスを選ばない選び方

辺A,B のマスを選ばない選び方

辺B,C のマスを選ばない選び方

辺C,D のマスを選ばない選び方

辺D,A のマスを選ばない選び方

辺A,C のマスを選ばない選び方

辺B,D のマスを選ばない選び方

辺A,B,C のマスを選ばない選び方

辺A,D,C のマスを選ばない選び方

辺A,B,D のマスを選ばない選び方

辺C,B,D のマスを選ばない選び方

4辺すべてのマスを選ばない選び方

以上の16式から16個の変数を求めると、 と表示することにして

縦 マス、横マスの範囲の選び方は 通りあるため、結局、

となります。

コード例 (Julia)

const MOD_ = 998244353

const NMAX = 1_000_000

fact    = Vector{Int}(undef, NMAX)
invfact = Vector{Int}(undef, NMAX)

function setup_fact( )
  fact[1] = 1
  invfact[1] = 1
  for i = 2:NMAX
    fact[i] = (i * fact[i-1]) % MOD_    # N!
    invfact[i] = invmod(fact[i],MOD_)   # 1/N!
  end
end

function Comb( N, M )
  if N < 0 || M < 0 || N - M < 0
    return 0
  end
  if M == 0 || N - M == 0
    return 1
  end

  ret = (invfact[M] * invfact[N-M])%MOD_
  ret *= fact[N]
  return ret % MOD_
end

function solve()


  # あらかじめ n!, 1/n! を計算
  setup_fact()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  H,W,K = readInts()

  F = zeros(Int, H, W)

  for h=1:H, w=1:W
    F[h,w] = Comb( h*w, K )
  end

  ans = 0

  for h=1:H, w=1:W
    maru1 = F[h,w]
    maru1 += (h>1) ? -2*F[h-1,w] : 0
    maru1 += (w>1) ? -2*F[h,w-1] : 0
    maru1 += (h>1&&w>1) ? 4*F[h-1,w-1] : 0
    maru1 += (w>2) ?   +F[h,w-2] : 0
    maru1 += (h>2) ?   +F[h-2,w] : 0
    maru1 += (h>1&&w>2) ? -2*F[h-1,w-2] : 0
    maru1 += (h>2&&w>1) ? -2*F[h-2,w-1] : 0
    maru1 += (h>2&&w>2) ?   +F[h-2,w-2] : 0
    maru1 %= MOD_
    if maru1 < 0
      maru1 += MOD_
    end
    coef = h * w * (H-h+1) * (W-w+1)
    coef %= MOD_
    ans += coef * maru1
    ans %= MOD_
    if ans < 0
      ans += MOD_
    end
  end

  ans *= invmod(F[H,W], MOD_)
  ans %= MOD_

  println(ans)

end  # function solve

# main
solve()

ABC297 E問題 Kth Takoyaki Set

atcoder.jp

安いほうから順に 個を選ぶことを考えてみます。
各種類を1つだけ買った時の価格を集合に加えます。
集合の中から一番安い価格を取り出します。
その価格に、さらに1つ追加で買うときの価格をに加えます。
は同じ値の重複を許さないようにして、から一番安い価格を取り出し、一つ追加した価格を加えることを繰り返したとき、回目に取り出した価格が求める答えです。

コード例 (Julia)

using DataStructures

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N,K = readInts()
  A = readInts()

  s = SortedSet{Int}()

  for i = 1:N
    push!(s,A[i])
  end

  for i = 1:K-1
    c = pop!(s)
    for j = 1:N
      push!(s,c+A[j])
    end
  end

  println(pop!(s))

end  # function solve

# main
solve()

ABC297 D問題 Count Subtractions

atcoder.jp

正の整数に対して
なら
なら
を何回繰り返すと になるかという問題です。

この操作を1回ずつ行うと、たとえばのとき回程度になるため時間がかかりすぎます。

そこで、 の場合、 を で割った商と余りを求めます。 回の操作で、 になるので、
であれば次に と に対する操作を考えます。であれば、 回の操作後にと等しくなります。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  A,B = readInts()

  if A < B
    A,B = B,A
  end

  ans = 0

  while A > B
    d,r = divrem(A,B)
    if r==0
      ans += d-1
      A -= (d-1)*B
    else
      ans += d
      A,B = B,A-d*B
    end
  end

  println(ans)

end  # function solve

# main
solve()

ABC296 F問題 Simultaneous Swap

atcoder.jp

条件の整理

並び替えで と が一致するためには、少なくとも と で値の出現回数が一致する必要があります。
一致しない場合は、「No」です。

操作前に、 の各組が同じ位置のとき、操作後には の組み合わせになります。
並び順は問題にしていないので、 の方を元の位置に戻すと、 となり、これはの方に の巡回置換を行ったことに相当します。

以上から、 に長さ3の巡回置換を繰り返すことで と一致させることができるか、という問題に言い換えることができます。

長さ3の巡回置換は、2回の互換(2要素の入れ替え)に分解することができるので、 を に一致させるための互換の回数が奇数のときは、長さ3の巡回置換だけでは一致させることができません。
逆に偶数回の互換で一致させることができる場合、長さ3の巡回置換を繰り返しで一致させることができます。

また、 の中に同じ値がある () 場合、互換は偶数回にも奇数回にもなるので、一致させることができます。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  N = readInt()
  A = readInts()
  B = readInts()

  # A と B の中身が一致しているか調べる

  n1 = zeros(Int,N)
  n2 = zeros(Int,N)

  for i = 1:N
    n1[A[i]] += 1
    n2[B[i]] += 1
  end

  for i = 1:N
    if n1[i] != n2[i]
      # i の登場回数が A と B で異なる
      #   --> 並び替えても一致しない
      println("No")
      return
    end
  end

  for i = 1:N
    if n1[i] >= 2
      # 同じ数字が2回以上現れる
      #   --> 一致させることができる
      println("Yes")
      return
    end
  end

  # A を小さい順に並び替えたときの B の並び
  C = zeros(Int,N)
  for i = 1:N
    C[A[i]] = B[i]
  end

  n_swap = 0

  i = 1
  while i <= N
    p = C[i]
    if p == i
      i += 1
    else
      n_swap += 1
      C[i] = C[p]
      C[p] = p
    end
  end

  if n_swap % 2 == 0
    println("Yes")
  else
    println("No")
  end

end  # function solve

# main
solve()