山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder 300点の問題を Ruby で解き直す その2

ABC 054 C - One-stroke Path

グラフと深さ優先探索の問題です。

方針

頂点 1 から深さ優先探索を行い、深さが  N - 1 となれば、全ての頂点を訪れたパスが存在することになります。

コード

N, M = gets.chop.split.map(&:to_i)
a = Array.new(M)
b = Array.new(M)
M.times{|i|
  a[i], b[i] = gets.chop.split.map(&:to_i)
  a[i] -= 1
  b[i] -= 1
}

# 隣接リスト
$adj = Array.new(N){Array.new()}
M.times{|i|
  $adj[a[i]].push(b[i])
  $adj[b[i]].push(a[i])
}
$cnt = 0
$vis = Array.new(N){true}
$vis[0] = false
def dfs(i, v)
  if i == N - 1
    $cnt += 1
  else
    $adj[v].each do |u|
      if $vis[u]
        $vis[u] = false
        dfs(i + 1, u)
        $vis[u] = true
      end
    end
  end
end

dfs(0, 0)
puts $cnt

ABC 057 C - Digits in Multiplication

計算の高速化が求められる問題です。

方針

 A \times B = N

を満たす  A\ (A \leq B) は、 1 \leq A \leq \sqrt{N} の範囲に絞られるので、この範囲で全探索を行います。

コード

N = gets.chop.to_i

m = Math.sqrt(N).to_i
max = N.to_s.size
(1..m).each do |i|
  if N % i == 0
    max = [max, [i.to_s.size, (N / i).to_s.size].max].min
  end
end
puts max

ABC 061 C - Big Array

計算量を落とすことが必要な問題です。

方針

二次元配列  c c_i = (a_i, b_i) として、 a について昇順にソートします。次に、 b_i の累積和を計算して、値が  K 以上になったときの要素が答えになります。

N, K = gets.chop.split.map(&:to_i)
c = Array.new(N){Array.new(2)}
N.times{|i|
  c[i][0], c[i][1] = gets.chop.split.map(&:to_i)
}

# 多次元配列のソート
c.sort_by!{|x| x[0]}

k = 0
N.times{|i|
  k += c[i][1]
  if k >= K
    puts c[i][0]
    exit
  end
}