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

ABC 054 C - One-stroke Path

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

方針

頂点 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

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

方針

を満たす は、 の範囲に絞られるので、この範囲で全探索を行います。

コード

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

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

方針

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

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
}