ABC296 E問題 Transition Game

atcoder.jp

どんな操作？

具体的に考えてみます。

で最初 を選んだとします。
1回目の操作で、 になります。
2回目の操作で、 になります。
3回目の操作で、 になります。
4回目の操作で、 になります。
4回の操作で最初に戻るので、周期4の繰り返しになります。

また、
で最初 を選んだとします。
1回目の操作で、 になります。
2回目の操作で、 になります。
3回目の操作で、 になります。
4回目の操作で、 になります。
いったん4になると、以降はずっと4のままで1,2,3に戻ることはありません。

どちらが勝つか？

繰り返しになる部分は、指定された回だけゴールから逆方向に戻ったところをに選ぶことで、回の操作後にゴールに達することが可能です。つまり、の値にかかわらずを適切に選ぶことで高橋君の勝ちになります。
繰り返しにならない部分は、一度通り過ぎると再度訪れることはありません。そこで、最初に青木君が大きなの値を指定すると、回の操作後にゴールに達するようなは存在せず、青木君の勝ちになります。

ループとそれ以外の検出

操作による値の変化を有向グラフで表します。入ってくる辺の次数が 0 の頂点はループではありません。その頂点から出ていく辺を取り除いたときに入次数が 0 になる頂点もループではありません。これを繰り返すことでループではない頂点をすべてリストアップすることができます。残りの辺で結ばれている頂点はループになっているので、この頂点の数が答えになります。

コード例 (Julia)

function solve()

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

  N = readInt()
  A = readInts()

  order = zeros(Int,N)

  for i = 1:N
    order[A[i]] += 1      # A[i] の入次数
  end

  stack = []

  for i = 1:N
    if order[i] == 0      # 入次数が 0 の頂点
      push!(stack,i)      # stack 配列に追加
    end
  end

  ans = N

  while length(stack) > 0
    p = pop!(stack)
    ans -= 1              # 入次数が 0 の頂点の分を引く

    q = A[p]
    order[q] -= 1         # p から出ていく辺が向かう頂点の入次数を 1 減らす
    if order[q] < 1
      push!(stack,q)      # 減らした結果、入次数が 0 になったら stack 配列に追加
    end
  end

  println(ans)

end  # function solve

# main
solve()

ABC296 D問題 M<=ab

atcoder.jp

条件1　
条件2　

条件1,2を満たす最小のを求める問題です。
を決めると、条件2から となります。(ceilは小数点以下を切り上げる関数)
の最小値を問われているので、 の最小値だけを考えて を調べればよいです。
また、は入れ替えても条件は変わらないため、の範囲で調べれば十分です。
を 1から まで変えて、 が 以上 以下であれば をこれまでの最小値と比較して、小さければ最小値を更新します。

コード例 (Julia)

function solve()

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

  N,M = readInts()

  ans = -1
  for i = 1:N
    if i * i > M
      break
    end

    k = cld(M,i)

    if k > N || k < i
      continue
    end

    p = k * i

    if ans == -1 || p <= ans
      ans = p
    end
  end

  println(ans)

end  # function solve

# main
solve()

ABC295 F問題 substr = S

atcoder.jp

求めるのは ですが、式のとおりにを求めてから和の計算をするのは効率が悪いです。
そこで、Sと一致する桁の位置を固定して、それ以外の桁の数を任意とする数のうち、 以上 以下になるのはいくつかを数えて、
これを桁をずらして和をとることを考えます。
以上 以下の範囲の数は、 以下および以下の範囲でそれぞれ数えて、その差から求められます。

例として、 以下の数のうち、 を含む数を考えます。
と一致する桁の位置を変えて和を計算することになりますが、その中で、678901 の桁の部分が と等しくなるケースについて考えてみます。

のより上位の桁は 12345、下位の桁は23456 です。上位の桁が 0～12344 の場合、下位の桁の値にかかわらずより小さな値になるため、条件を満たす個数はです。(の先頭が0の場合、上位の桁は0～ではなく、1～になるため、その分を減らします。)
上位の桁がと同じ12345の数については、それより下位の桁を見る必要があります。(の先頭が0の場合、上位の桁が0のケースは除きます。)
と重なるの桁の数よりが小さければ、より下位の桁にかかわらずより小さな値になるため、条件を満たす個数にを追加し、
逆に大きければ、より下位の桁にかかわらずより大きな値になるため、条件を満たす個数は 0 です。
等しい場合は、より下位の桁で大小が決まります。0～23456 であればR以下の数になるので、条件を満たす個数にを追加します。

コード例 (Julia)

function sum_f(NS, NR, digit_S, digit_R, S0)

  ans = 0

  for digit = 0: digit_R - digit_S    # S より下の桁数

    N1 = 10^digit
    N2 = 10^(digit+digit_S)

    N_low  = mod(NR, N1)              # S より下の桁の数値
    N_cent = div(mod(NR, N2), N1)     # S と重なる桁の数値
    N_up   = div(NR, N2)              # S より上の桁の数値

    if N_up > 0
      if S0
        ans += (N_up - 1) * N1
      else
        ans += N_up * N1
      end
    end

    if S0 && N_up == 0
      continue
    end

    if N_cent > NS
      ans += N1
    elseif N_cent == NS
      ans += N_low + 1
    end
  end

  return(ans)

end  # function solve

function solve()

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

  T = readInt()

  for t = 1:T

    SS,SL,SR = split(readline())            # 文字列として読み込む

    SL = string(parse(Int,SL) - 1)          # L ==> L-1 に置き換え

    S0 = false                              # S の先頭が 0 かどうか
    if SS[1] == '0'
      S0 = true
    end

    digit_S = length(SS)                    # 桁数
    digit_L = length(SL)
    digit_R = length(SR)

    NS = parse(Int,SS)                      # 整数型へ
    NL = parse(Int,SL)
    NR = parse(Int,SR)

    ans = sum_f(NS, NR, digit_S, digit_R, S0) - sum_f(NS, NL, digit_S, digit_L, S0)

    println(ans)

  end

end

# main
solve()

ABC295 E問題 Kth Number

atcoder.jp

期待値の求め方

昇順に並び替えたときの 番目の値が である確率を とすると、
求めたい期待値は、

です。

与えられた数列の中で を満たす の個数を 個、 の個数を 個、 の個数を 個、 の個数を 個とします()。
個の を1以上以下の整数に置き換える場合の数は、 です。
このうち、番目の値が になるような置き換え方を考えます。 に置き換えられる個数を 個、 の個数を 個、 の個数を 個とします()。 このとき、昇順に並び替えると値が なのは、 番目から 番目までです。がこの範囲に含まれればよいので、

これを満たす の範囲を考えればよいです。あるについて考えると、個の中から個と個を選ぶ場合の数は、

で、への置き換えは1～ までの 通り、への置き換えは～ までの 通りあるので、場合の数は、

となります。これを条件を満たす の範囲で和を求めることで、昇順に並び替えたとき 番目の値が になる場合の数が求められ、これをで割ることで確率 が求められます。

この考え方では、のループでを求め、のループで答えを求める三重ループになりますが、実際には計算時間がかかりすぎます。

ループを減らす

これまで、番目の値がちょうどになる確率を考えていました。この発想を変えて、番目の値が以上になる確率を考えてみます。

この式から、

となります。求めたい期待値は、で表すと、

になります。
与えられた数列の中で を満たす の個数を 個、 の個数を 個、 の個数を 個とします()。
個の を1以上以下の整数に置き換える場合の数は、 です。
このうち、番目の値が 以上になるような置き換え方を考えます。 に置き換えられる個数を 個、 の個数を 個とします()。 このとき、昇順に並び替えると値が 以上になるためには、 であればよく、一重ループで済みます。
場合の数は、

となります。あとは、

から を求めることになります。

コード例 (Julia)

_MOD = 998244353

F = []
invF = []

function init_fact(N)
  push!(F,1)
  for i = 1:N
    push!(F,(F[i]*i)%_MOD)
  end
  for i = 1:N+1
    push!(invF,invmod(F[i],_MOD))
  end
end

function combination(N,A)
  if N < 0 || A > N || A < 0
    return 0
  end
  x = (F[N+1] * invF[A+1]) % _MOD
  x = (x * invF[N-A+1]) % _MOD
  return x
end

function solve()

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

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

  B = []
  nzero = 0
  for i = 1:N
    if A[i] > 0
      push!(B,A[i])
    else
      nzero += 1    # A_i = 0 の個数
    end
  end

  # 階乗をあらかじめ計算しておく
  init_fact(nzero)

  # 0 以外の数字を昇順で並び替え
  sort!(B)

  ans = 0
  for k = 1:M
    # K 番目の数字が k 以上になる確率

    # K 番目の数字が k以上 <==> k より小さい数が K-1 個以下

    kpos1 = searchsortedfirst(B,k)  # k <= B[kpos1]

    # 「k より小さい数が K-1 個以下」 のうち、値が決まっている B を除いた個数
    under_max = (K-1) - (kpos1-1)

    for under = 0:under_max

      C = combination(nzero, under) # nzero 個の中から under個を選ぶ選び方
      n = 1
      if k-1>=0
        n = powermod( k-1, under, _MOD)   # under個は、1～k-1 の中から自由に1つ選べる
      end
      m = 1
      if M-k+1>=0
        m = powermod( M-k+1, nzero-under, _MOD)   # 残りは、k～M の中から自由に1つ選べる
      end

      s = (n * m) % _MOD
      s = (s * C) % _MOD
      ans += s
      ans = ans % _MOD
    end
  end

  ans = ans * invmod(powermod(M,nzero,_MOD), _MOD)
  ans = ans % _MOD

  println(ans)

end  # function solve

# main
solve()

ABC295 D問題 Three Days Ago

atcoder.jp

嬉しい列になる条件

嬉しい列は、「並び替えによって同じ列を2度繰り返すようにできるもの」です。
同じものが2度あらわれることから、列の中の各数字は偶数個になります。
逆に各数字の個数がすべて偶数であれば「並び替えによって同じ列を2度繰り返すようにできる」。
そのため、嬉しい列であることと列の中の各数字の個数が偶数個であることは同値です。

文字目から 文字目までの部分文字列が嬉しい列かどうかを調べたいので、
部分文字列に含まれる各文字の個数を素早く知りたいです。
そのためには、累積和の考え方( 1文字目から 文字目までに含まれる個数を とすると、 文字目から 文字目までに含まれる個数は、 と求められる)　を使います。

偶数か奇数かの表現に ビット配列を利用

各数字の個数が偶数か奇数かを区別すればよいので、ビット配列を利用してみます。
数字は 0 から 9 までの 10 個なので、10桁のビット配列で 10個の数字の数の偶奇を表現できます。
偶数を 0、奇数を 1 で表すことにします。
文字目から 文字目までの部分文字列が嬉しい列になるのは、
つまり の場合です。

求めたいのは、 となる整数の組 の数です。
それには、同じ値の が何個あるか数えて、そこから2個選ぶ場合の数 を加算していくことで求められます。

コード例 (Julia)

function solve()

  # 文字列入力
  S = readline()

  # 文字列の長さ
  N = length(S)

  # 各ビットが偶数回か奇数回かを表す
  B = 0

  # ビット状態が同じものが何個あるか記録するための辞書型データ
  D = Dict()

  # 初期状態を登録
  push!(D, B=>1)

  for i = 1:N
    #  i 文字目が k なら ビット配列の k 番目を反転する
    n = S[i] - '0' + 1
    m = (1 << n)
    B = xor(B, m)
    #  この状態を登録
    if haskey(D,B)
      D[B] += 1
    else
      push!(D, B=>1)
    end
  end

  #  ビット状態が同じペアの組み合わせの数が求める答え
  ans = 0
  for k in keys(D)
    n = D[k]
    ans += (n*(n-1))÷2
  end

  println(ans)

end  # function solve

# main
solve()

ABC294 F問題 Sugar Water 2

atcoder.jp

二分法探索

N本とM本の組み合わせですが、最大で となりうるため、すべての組み合わせを計算して、ソートして 番目を求めるのは時間がかかりすぎます。
番目を求めたいけれど、ソートするのが大変な場合、二分法で探索することを考えます。

ある濃度 に対して、それ以上の濃度になるのが より多ければ は求める濃度よりも小さく、 より少なければ は大きいことがわかります。
そこで、ある濃度 より濃度が大きいか小さいかを高速に判定することができるか考えてみます。

砂糖 g と水 g の濃度 は、

です。砂糖 g と水 g の砂糖水と、砂糖 g と水 g の砂糖水を混ぜたときの濃度が 以上になるのは

のときですが、この式で計算しようとすると選んだ2本のペアごとに計算することになり、大変な計算量になります。
そこで次のように式を変形します。

この式では の項は の値に関係なく計算できます。そこで、一方の高橋君が持っている砂糖水について を小さい順にソートしておいて、
青木君が持っている砂糖水それぞれについて、和が 0 以上になる、つまり

を満たす個数をカウントすればよいです。あらかじめソートしておくことで二分探索で最初に条件を満たすのが何番目かを探すことができ、一つ一つ比べなくても条件を満たす個数はわかります。
濃度 が変わるたびにソートをする必要がありますが、十分高速に求められます。

コード例 (Julia)

function solve()

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

  N, M, K = readInts()

  A = zeros(Int,N)
  B = zeros(Int,N)
  C = zeros(Int,M)
  D = zeros(Int,M)

  for i=1:N
    A[i],B[i] = readInts()
  end

  for i=1:M
    C[i],D[i] = readInts()
  end

  # 濃度 p の二分探索
  p_u = 100.0
  p_l = 0.0
  while  p_u - p_l > 1.0e-10
    p = (p_u + p_l) * 0.5

    # 濃度が p 以上の組み合わせを数える
    E = [ 100*A[i] - p * (A[i] + B[i]) for i = 1:N ]
    F = [ 100*C[i] - p * (C[i] + D[i]) for i = 1:M ]
    sort!(E)
    num = 0
    for i = 1:M
      pos = searchsortedfirst(E, -F[i])
      num += N-pos+1
    end
    if num < K
      p_u = p
    else
      p_l = p
    end
  end

  println( p_u )

end  # function solve

# main
solve()

ABC294 E問題 2xN Grid

atcoder.jp

範囲で調べる

圧縮された配列を元に戻して (最大長さ ) 2つの配列の各要素を比較するのは時間がかかりすぎるため、圧縮した情報のまま数えていきます。

ある値が、配列の何番目から何番目までの範囲になるかは、 の累積和から決まります。
ごとに、範囲の情報をまとめます。 は の可能性もあるため、vector配列ではなく、連想配列を使います。

そのあと、 ごとに範囲の先頭位置でソートして、一つずつ取り出します。あとから取り出した先頭位置が、前の最後尾位置より後ろであれば範囲の重なりはありません。
2つの範囲の先頭位置のうち後ろの方と、最後尾位置の前の方に挟まれた範囲が重なり範囲で、この範囲内の要素数を加算していって答えとします。
重なり範囲より後ろの部分は、次の範囲と重なっているかどうか調べる対象とします。

コード例 (Julia)

function solve()

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

  L, N1, N2 = readInts()

  D = Dict()

  k = 1
  for i = 1:N1+N2
    V, L = readInts()
    # 整数 V が書かれている範囲は、k から k+L-1
    # この範囲を記録する
    if ! haskey(D, V)
      D[V] = [ (k, k+L-1) ]
    else
      push!(D[V], (k, k+L-1))
    end
    k += L

    if i==N1
      k = 1
    end
  end

  ans = 0

  for (v, vec) in D
    sort!(vec)
    # 範囲の重複を数える
    s0 = 0
    e0 = 0
    for i = 1: length(vec)
      s1,e1 = vec[i]
      if s1 > e0
        s0 = s1
        e0 = e1
        continue
      end

      ans += min(e0,e1) - s1 + 1

      s0 = min(e0,e1) + 1
      e0 = max(e0,e1)
    end
  end

  println(ans)

end  # function solve

# main
solve()