Rubyで競技プログラミング

最近Ruby on Rails チュートリアル:実例を使って Rails を学ぼうを終えてRubyの練習がてら競プロの問題をいくつか解いてみたので、 入出力の方法とかのメモ。

他に関連しそうな記事:

入出力

基本的なこと

  • getsで標準入力から1行文字列を受け取る
    • 改行も入るので取り除くにはgets.chopとかする
  • 整数への変換はto_i浮動小数to_f、文字列はto_s
  • str.splitで空白文字で分割
  • a.join(sep)で配列を区切り文字で連結した文字列を得る

よくあるパターン

  • 1行に整数が空白区切りであるとき
x_1 x_2 ... x_n
# 入力
# 個々の変数にとるとき
a,b,c = gets.split.map(&:to_i)
# 配列としてとるとき
xs = gets.split.map(&:to_i)

# 出力
puts xs.join(' ')
  • 複数行に整数があるとき
x_1
x_2
...
x_n
# 入力
xs = []
n.times { xs << gets.to_i }

# 出力
xs.map { |x| puts x }
  • 複数行に複数個数字があるとき
n_1 x_11 ... x_1(n_1)
...
n_m x_m1 ... x_m(n_m)
ns = [] # [n_1, ..., n_m]
xs = [] # [[x_11,...],...,[x_m1,...]]
3.times do
  line = gets.split.map(&:to_i)
  ns << line.shift
  xs << line
end

配列

  • Array.new(n,z)で長さn、初期値zの配列を作る
    • zを省略するとnilで初期化
    • 連番がほしければ(1..n).to_aでもできる
  • 二次元配列はArray.new(n){ Array.new(m) }で作る
  • <<で末尾に追加
  • popで末尾から、shiftで先頭から取り出す

AOJ 2403 The Enemy of My Enemy is My Friend

概要

問題文

頂点数Nの単純無向グラフが与えられる。 また各頂点には値B_iが割り当てられている。 このとき、頂点0を含む独立集合のうち値の総和の最大値を求めよ。

制約:  1 \leq N \leq 40 ,\ 0 \leq B_i \leq 10^3

解法

半分全列挙+高速ゼータ変換 (想定解法ではないらしい)。

頂点を半分に分けて、0を含む側をV_0、含まない側をVとする。 S \subseteq Vに対して関数ff(S) = 「SがVの独立集合ならば値の総和、さもなくば0」と定めて、 g(T) = \text{max}_{S \subseteq T}f(S)を高速ゼータ変換で求める。

あとはV_0側の独立集合Sを全列挙して\text{sum}(S) + g(Sに接続するVの頂点集合の補集合)の最大値を返せば良い。 計算量はO(\frac{N}{2}2^\frac{N}{2})

AOJ 2371 TransferTrain

概要

問題文

電車で目的地まで行くための最短経路を求めるというよくある感じの問題。

N本の路線がありそれぞれの路線はa_i個の駅からなる。 一つの路線について駅s_1,\ldots,s_{a_i}とそれらの間の所要時間t_1,\ldots,t_{a_i - 1}が与えられる。 電車は両方向にあるのでどちら向きに移動しても良い。

また、同じ駅が複数回現れる (異なる路線はもちろん、同じ路線でもありうる)とき、その駅は乗り換え駅で、時間Tで乗り換えることができる。

このとき今いる駅から目的駅までの最短時間と乗り換え回数を求めよ。最短経路が複数あるときは乗り換え回数が最小のものを求めよ。

制約:  1 \leq N \leq 5\times 10^4,\ \sum_{i=1}^{N}a_i \leq 10^5

解法

Dijkstra.

普通に路線ごとにs_1 \overset{(t_1,0)}\longleftrightarrow s_2 \overset{(t_2,0)}\longleftrightarrow \cdotsと辺を張る。 辺のコストは(かかる時間、乗り換え回数)を表している。

乗り換えのために同じ駅同士でコストTの辺を張ると辺の数が大きくなりすぎるので次のように工夫する。 駅名sに対して一つ頂点Sを作っておき、駅sが現れるごとにs \overset{(T,1)}\longrightarrow SS \overset{(0,0)}\longrightarrow sのように辺を張る。

後は普通にDijkstraする。スタートとゴールがa,bのとき上に対応するのはA,Bになる。 また、乗り換えを一回余分に数えている (b \overset{(T,1)}\longrightarrow Bの部分) のでそれを引いたものが答え。

AOJ 2707 Jail

概要

問題文

自然数 0,1,2,\ldots に対して以下の操作を  N-1 回行ったときの先頭の数字を答えよ。

  • 先頭から 0,k,2k,\ldots 番目の数字を削除する。

制約: 1 \leq N \leq 10^5, 2 \leq k \leq 10^5

解法

下のように、ある数字が削除される前は先頭から何番目だったか逆から構成していくと分かりやすい。

削除前 012k-1kk+1k+2
削除後 01k-2k-1k

これを見るとK-1個おきに削除前の数字と対応が付いているのがわかる。 削除後の x 番目の数字は削除前だと  K * \lfloor \frac{x}{K-1} \rfloor + x \bmod (K-1) + 1 番目となることがわかるので これを N-1 回繰り返し計算すれば良い。