2024-04-21

ABC350

A - Past ABCs

与えられる文字列は 6文字で、先頭の3文字は気にする必要が無く、末尾 3 文字は数字であることが保証されています。
そのため、文字列の4文字目から6文字目までの部分文字列を数字に変換して条件を満たすか値かどうかを調べればよいです。

B - Dentist Aoki

長さ N の論理型の配列を用意します。歯が生えている状態を TRUE, 抜いている状態を FALSE として、
初期状態はすべて TRUE とします。与えられた治療する番号について、その配列要素が TRUE のときは FALSE, FALSE のときは TRUE に変えます。
最終的に TRUE の数が答えになります。

C - Sort

与えられた配列 A を先頭から順にみていきます。
i 番目の要素 A[i] が i と異なるとき、 i 番目の要素と A[i] 番目の要素を入れ替えます。
すると A[i] 番目の要素は正しい値になります。これを i 番目の要素が A[i] = i になるまで繰り返します。
A[i] = i になったら、i に 1加えて同じことを繰り返します。
たとえば、
3 4 6 1 2 5 8 7
↓ 　1番目と3番目入れ替え
6 4 3 1 2 5 8 7
↓ 　1番目と6番目入れ替え
5 4 3 1 2 6 8 7
↓ 　1番目と5番目入れ替え
2 4 3 1 5 6 8 7
↓ 　1番目と2番目入れ替え
4 2 3 1 5 6 8 7
↓ 　1番目と4番目入れ替え
1 2 3 4 5 6 8 7
↓ 　7番目と8番目入れ替え
1 2 3 4 5 6 7 8
のように入れ替えればよいです。

D - New Friends

ユーザを頂点、友達関係を辺で表現するグラフを考えます。条件から無向グラフです。
Union-Find 木から、友達関係の連結成分を求めます。頂点 i が含まれる連結グラフの頂点数が N で、
頂点 i の次数が d のとき、頂点 i は追加で (N-1-d) の頂点を相手に辺を結ぶことができます。
この値を全頂点で合計します。一つの辺で2つの頂点の次数を1つずつ増やすことができるため、合計した値を 2 で割った値が答えです。

E - Toward 0

メモ化再帰で解きます。
ある整数 N について、支払金額の期待値の最小値を $C \left[N \right]$ とします。
1番目の操作を選ぶと、支払金額の期待値は $C \left[ \frac{N}{A} \right] +X$ です。
2番目の操作を選ぶと、
$C \left[ N \right] = \frac{1}{6} \left( C \left[ \frac{N}{1} \right] +C \left[ \frac{N}{2} \right] + C \left[ \frac{N}{3} \right] + C \left[ \frac{N}{4} \right] + C \left[ \frac{N}{5} \right] + C \left[ \frac{N}{6} \right]\right) +Y$
$\frac{5}{6} C \left[ N \right] = \frac{1}{6} \left( C \left[ \frac{N}{2} \right] + C \left[ \frac{N}{3} \right] + C \left[ \frac{N}{4} \right] + C \left[ \frac{N}{5} \right] + C \left[ \frac{N}{6} \right]\right) +Y$
$C \left[ N \right] = \frac{1}{5} \left( C \left[ \frac{N}{2} \right] + C \left[ \frac{N}{3} \right] + C \left[ \frac{N}{4} \right] + C \left[ \frac{N}{5} \right] + C \left[ \frac{N}{6} \right]\right) +\frac{6}{5} Y$
となります。
そこで、 $C \left[N \right]$ と $\frac{1}{5} \left( C \left[ \frac{N}{2} \right] + C \left[ \frac{N}{3} \right] + C \left[ \frac{N}{4} \right] + C \left[ \frac{N}{5} \right] + C \left[ \frac{N}{6} \right]\right) +\frac{6}{5} Y$ の小さいほうを $C \left[N \right]$ とすればよいです。
これを再帰で求めます。値が決まった Cost[N] を連想配列などで管理してメモ化することで効率よく答えが求められます。

F - Transpose

( ) の深さが一つ増えるごとに反転されるので、深さが奇数のときは反転、偶数のときはそのままでよいことになります。
あらかじめ、何文字目の "(" と何文字目の ")" が対応しているかを探しておきます。
処理は再帰で行います。 "(" と ")" で挟まれた範囲について、深さが偶数のときは前から順に、奇数のときは後ろから大文字小文字を反転させて一文字ずつ出力していきます。
"(" または ")" が見つかったら再帰で処理して、それが終わったら対応するカッコの次から処理を継続します。

2023-06-25

ABC300 F問題 More Holidays

atcoder.jp

できるだけ長く連続した'o' の長さを求める問題ですが、長さを求めるためには最初の'o' の位置 $X_{start}$ と最後の'o'の位置 $X_{end}$ から $長さ = X_{end} - X_{start} + 1$ と考えればよいです。
'o'が連続する連続部分文字列をできるだけ長くするためには、最初の'o'は文字列の先頭あるいは'x'の次の文字となります。最初の'o'の位置から $K$ 個の'x'を'o'に変えます。
文字列の先頭からの場合、最後の'o'は $K+1$ 個目の'x'の一つ前になります。最初の'o'が $i$ 個目の'x'の次の文字の場合、最後の'o'は $K+i+1$ 個目の'x'の一つ前になります。
文字列は、 $S$ を $M$ 個連結したものなので、最初の'o'の一つ前の'x'の選び方は、先頭の $S$ 内だけループして調べれば十分です。
最後の'x'の位置は、何個目の $S$ の何番目の'x'か、から計算します。求めた位置が全体の文字列の長さ $NM$ を超えていれば、最後の'o'の位置を $X_{end} = NM$ とします。

コード例 (Julia)

function solve()

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

  N,M,K = readInts()
  S = readline()

  X = Vector{Int}()

  # S 内の 'x' の位置
  for i = 1:N
    if S[i] == 'x'
      push!(X,i)
    end
  end

  # S 内の 'x' の個数
  nx = length(X)

  ans = 0

  for i = 0:nx
    # 連続する 'o' の先頭
    head = 1
    if i > 0
      head = X[i] + 1
    end

    # 'o' に変えるのは 'x' の何個目までか
    # S を d 回繰り返した後の r 個目
    d,r = divrem( i + K, nx )

    # 連続する 'o' の最後
    tail = d * N + X[r+1] - 1
    if tail > N * M
      tail = N * M
    end

    if ans < tail - head + 1
      ans = tail - head + 1
    end
  end

  println(ans)

end  # function solve

# main
solve()

2023-06-25

ABC300 E問題 Dice Product 3

atcoder.jp

積が N になるための出た目の回数

サイコロを何回か振った結果、1,2,3,4,5,6 の目が出た回数がそれぞれ $n_1, n_2, n_3, n_4, n_5, n_6$ 回のとき、全部の積を素因数分解すると、
$2^{n_2 + 2 n_4 + n_6} \times 3^{n_3 + n_6} \times 5^{n_5}$
となります。これが N と一致するためには、まず N を
$N = 2^a \times 3^b \times 5^c$
の形に素因数分解でき、かつ
$a = n_2 + 2 n_4 + n_6$
$b = n_3 + n_6$
$c = n_5$
が成り立てばよいです。N の素因数分解で、2,3,5 以外の素数が現れたら不可 (確率 0) です。

サイコロを振って出た目を掛けていってN になる確率を求める問題です。N を素因数分解して、2,3,5 以外の素数がある場合は、サイコロの目を掛けていっても N に一致することはありません。(確率 0)
素因数分解した結果を、 $N = 2^a \times 3^b \times 5^c$ とします。

コード例 (Julia)

MOD_ = 998244353

fact    = Vector{Int}()
invfact = Vector{Int}()

function setup_fact(N)
  resize!(fact,N)
  resize!(invfact,N)

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

function f5(d2,d3,d4,d5,d6)

  if d2 < 0 || d3 < 0 || d4 < 0 || d5 < 0 || d6 < 0
    return 0
  end

  sum = d2 + d3 + d4 + d5 + d6

  n = fact[sum]
  n %= MOD_
  n = d2 > 1 ? (n*invfact[d2])%MOD_ : n
  n = d3 > 1 ? (n*invfact[d3])%MOD_ : n
  n = d4 > 1 ? (n*invfact[d4])%MOD_ : n
  n = d5 > 1 ? (n*invfact[d5])%MOD_ : n
  n = d6 > 1 ? (n*invfact[d6])%MOD_ : n

  return n
end

function solve()

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

  N = readInt()

  # N を 2 で何回割り切れるか
  n2 = 0
  while mod(N,2) == 0
    n2 += 1
    N = div(N,2)
  end

  # N を 3 で何回割り切れるか
  n3 = 0
  while mod(N,3) == 0
    n3 += 1
    N = div(N,3)
  end

  # N を 5 で何回割り切れるか
  n5 = 0
  while mod(N,5) == 0
    n5 += 1
    N = div(N,5)
  end

  # 2,3,5 以外の素因数があれば、不可(確率 0)
  if N != 1
    println(0)
    return
  end

  # n!,  1/n! をあらかじめ計算しておく
  M = max( n2+n3+n5, 5 )
  setup_fact(M)

  ans = 0

  for d4 = 0:n2
    for d6 = 0:max(n2,n3)
      d2 = n2 - 2 * d4 - d6
      if d2 < 0
        continue
      end
      d3 = n3 - d6
      if d3 < 0
        continue
      end
      d5 = n5

      sum = d2 + d3 + d4 + d5 + d6

      # (1/5)^sum
      c = powermod(invmod(5,MOD_), sum, MOD_)

      # 組み合わせ数をかける
      c *= f5(d2,d3,d4,d5,d6)
      c %= MOD_

      ans += c
      ans %= MOD_

    end
  end

  println(ans)

end  # function solve

# main
solve()

2023-06-25

ABC300 D問題 AABCC

atcoder.jp

エラトステネスのふるいで素数のリストを作成して、
$a,b,c$ を $i,j,k$ 番目の素数 ( $i \lt j \lt k$ ) とします。
$i,j$ をループして、条件を満たす $k$ の個数を求めることを考えます。
$i,j$ すなわち $a,b$ の値を固定すれば、 $c$ の範囲は $b \lt c \le \sqrt{\frac{N}{a^2 b}}$ となります。
この範囲に入るのが素数リストの何番目から何番目かを求めれば、個数が求められます。
このとき、上限の値は素数リストを二分探索することで高速に求めることができます。

コード例 (Julia)

primes = []   # 素数
prime2 = []   # 素数の2乗

function prime_list(N)
  # エラトステネスの篩

  p = trues(N)
  p[1] = false  # 1は素数ではない

  for i = 1:N
    if ! p[i]
      continue
    end

    for j = i*i:i:N
      p[j] = false
    end
  end

  for i = 1:N
    if  p[i]
      push!(primes,i)     # 素数リスト
      push!(prime2,i*i)   # 素数の2乗リスト
    end
  end

end


function solve()

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

  N = readInt()

  prime_list(Int(floor(sqrt(N))))

  M = length(primes)

  ans = 0

  for i = 1:M
    for j = i+1:M-1
      k = j + 1
      if prime2[i] * primes[j] * prime2[k] > N
        break
      end

      klow = j
      khigh = M
      Nk = div(N, prime2[i] * primes[j])

      while khigh - klow > 1
        kc = div( khigh + klow, 2 )
        if prime2[kc] > Nk
          khigh = kc
        else
          klow = kc
        end
      end

      ans += klow - j

    end
  end

  println(ans)

end  # function solve

# main
solve()

2023-06-11

ABC299 F問題 Square Subsequence

atcoder.jp

部分文字列の数え上げ

まず、部分文字列を数える方法を考えてみます。文字列の長さを $N$ 文字とすると、各文字に対して選ぶか選ばないかの2択なので、部分文字列の選び方は $2^N$ 通りあります。
しかし、これは同じ部分文字列になる選び方が複数あるとき、それらすべてを重複カウントしています。
重複カウントを避けるために、可能な限り左側の文字から選んでいく動的計画法(DP)を考えます。 $i$ 文字目を最後の文字とする部分文字列の数を $dp(i)$ と表します。
1文字目の文字として'a'から'z'の各文字が最初に現れる位置 $i$ で $dp(i)=1$ とします。つづいて $i$ 文字目の後ろにさらに1文字を追加すると考えて、 $i+1$ 文字目以降の 'a'から'z'の各文字が最初に現れる位置 $k$ で $dp(k) += dp(i)$ と加算します。これを $i = 1,2,\cdots,N$ とループして $dp(i)$ を確定していきます。最終的に、 $\sum dp(i)$ が重複のない部分文字列の数になります。

繰り返しになる部分文字列の数え上げ

同じ文字列の繰り返し $TT$ の形の部分文字列を探します。先頭からの部分文字列と途中からの部分文字列が一致する場合の数を求めたいですが、「途中」がどの位置からなのかはいろいろありえます。
そこで、最初の $T$ の最後の文字が $K$ 文字目である場合に限定します。このとき、2つ目の $T$ は $K+1$ 文字目からと、探し始める位置を固定できます。文字列 $S$ の最初から $K$ 文字目までを $S_1$ 、 $K+1$ 文字目から最後までを $S_2$ として、 $S_1$ の部分文字列のうち $S_2$ の部分文字列にもなる文字列の数を探します。
例えば、
$S_1 = abcabc$
$S_2 = cbacbac$
のケースを考えてみます。 $S_1$ の $dp(3)$ は3文字目の"c"を最後に選ぶ部分文字列の数で、 "c", "ac", "bc", "abc" の4つがあることから $dp(3)=4$ になります。これに対応する $S_2$ の"c" の文字の位置は、"c" については 1文字目、"ac", "bc" については 4文字目、"abc"については7文字目になります。これらは数える上で区別する必要があるので、 $S_1$ と $S_2$ の共通部分文字列で $S_1$ では $i$ 文字目が最後の文字、 $S_2$ では $j$ 文字目が最後の文字になる文字列の数を動的計画法の $dp(i,j)$ と表すことにします。
文字列 "c" に対応して $dp(3,1) = 1$ 、文字列"ac","bc" に対応して $dp(3,4) = 2$ 、文字列"abc"に対応して $dp(3,7) = 1$ になります。これにさらに一文字追加することを考えます。
"c" に "a"を追加すると "ca" になり、これは $dp(4,3)$ に対応するため、 $dp(4,3) += dp(3,1)$ と加算します。"b"を追加すると $dp(5,2) += dp(3,1)$ と加算します。"c"を追加すと $dp(6,4) += dp(3,1)$ と加算します。
"ac"または"bc"に一文字追加するケースは、"a"を追加すると $dp(4,6) += dp(3,4)$ 、"b"を追加すると $dp(5,5) += dp(3,4)$ 、"c"を追加すると $dp(6,7) += dp(3,4)$ と加算します。
"abc" は $dp(3,7)$ であり、 $S_2$ の最後の文字に達しているため文字を追加することができません。
このように計算して、 $\sum_j dp(K,j)$ の和が最初の $T$ の最後の文字が $K$ 文字目である場合の数になります。
$K=1,2,\cdots,N$ のループで和を計算することで答えが得られます。

コード例 (Julia)

_MOD = 998244353

function solve()

  S = readline()
  N = length(S)

  ans = 0

  for K = 1:N
    S1 = SubString(S,1,K)
    S2 = SubString(S,K+1,N)

    # 'a'から'z'が文字列中の何文字目か
    d1 = Dict(k => Int[] for k = 'a':'z')
    d2 = Dict(k => Int[] for k = 'a':'z')

    for j = 1:K
      c1 = S1[j]
      push!(d1[c1], j)
    end
    for j = 1:N-K
      c2 = S2[j]
      push!(d2[c2], j)
    end

    # 各文字の数
    n1 = Dict()
    n2 = Dict()
    for c = 'a':'z'
      n1[c] = length(d1[c])
      n2[c] = length(d2[c])
    end

    dp = zeros(Int,K,N-K)

    # 一文字目
    for c = 'a':'z'
      if n1[c] == 0 || n2[c] == 0
        continue
      end
      dp[ d1[c][1], d2[c][1] ] = 1
    end

    # 二文字目以降
    for i = 1:K-1
      for j = 1:N-K-1
        if dp[i,j] == 0
          continue
        end

        for c = 'a':'z'
          p1 = -1
          p2 = -1
          for x = 1:n1[c]
            if d1[c][x] > i
              p1 = d1[c][x]
              break
            end
          end
          for x = 1:n2[c]
            if d2[c][x] > j
              p2 = d2[c][x]
              break
            end
          end

          if p1 > 0 && p2 > 0
            dp[p1,p2] += dp[i,j]
            dp[p1,p2] %= _MOD
          end
        end
      end
    end

    for j = 1:N-K
      ans += dp[K,j]
      ans %= _MOD
    end

  end

  println(ans)

end  # function solve

# main
solve()

2023-06-11

ABC299 E問題 Nearest Black Vertex

atcoder.jp

頂点[p_i] から黒頂点までの最短距離が $d_i$ であることから、距離 $d_i - 1$ 以下の頂点はすべて白頂点であると確定します。
各頂点について調べることで、白と確定する頂点をすべてリストアップします。
そのあとで、未確定の頂点は黒として、各頂点[p_i] から距離 $d_i$ に黒頂点があるかどうか調べることで判定ができます。

コード例 (Julia)

function solve()

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

  N,M = readInts()

  edge = [ [] for i = 1:N ]

  for i = 1:M
    u,v = readInts()
    push!(edge[u], v)
    push!(edge[v], u)
  end

  K = readInt()

  p = zeros(Int,K)
  d = zeros(Int,K)

  for i = 1:K
    p[i],d[i] = readInts()
  end

  color = ones(Int,N)      # 1なら黒, 0なら白
  q = zeros(Int,N)         # 幅優先探索のキュー
  db = [ [] for i = 1:K ]  # p[i] から距離 d[i] の頂点リスト

  for i = 1:K
    dist = fill(-1,N)
    q[1] = p[i]
    dist[p[i]] = 0
    head = 1
    tail = 2
    while head < tail
      a = q[head]
      head += 1
      if dist[a] == d[i]
        push!(db[i],a)
      elseif dist[a] < d[i]
        color[a] = 0      # 距離がd[i]未満は白
      elseif dist[a] > d[i]
        break
      end

      for b in edge[a]
        if dist[b] == -1
          dist[b] = dist[a] + 1
          q[tail] = b
          tail += 1
        end
      end
    end
  end

  for i = 1:K
    black = 0
    for b in db[i]
      black += color[b]
    end
    if black == 0
      println("No")
      return
    end
  end

  println("Yes")
  println(join(color))

end  # function solve

# main
solve()

2023-06-11

ABC299 D問題 Find by Query

atcoder.jp

$S_p \ne S_{p+1}$ となる $p$ を一つ求める問題です。
$S_1 \ne S_N$ であることから、 $S_1 = S_2 = \cdots = S_N$ ではなく、どこかで $S_p \ne S_{p+1}$ となります。
1と $N$ の間の $a$ について、 $S_1 = S_a \ne S_N$ であれば、1から $a$ の間に値が変わることが無いかもしれませんが、 $a$ から $N$ の間では少なくとも1つ値が変わるところがあります。そこで、 $a$ から $N$ の間を調べればよいです。 $S_1 \ne S_a = S_N$ であれば、1から $a$ の間を調べればよいです。1と $N$ の中間を $a$ とする二分法を繰り返して範囲を絞り込むことで答えが求められます。

コード例 (Julia)

function solve()

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

  N = readInt()

  zero = 1
  one  = N

  while one - zero > 1
    a = div( one + zero, 2)
    println("? ",a)
    b = readInt()
    if b == 0
      zero = a
    else
      one = a
    end
  end

  println("! ",zero)

end  # function solve

# main
solve()