会社の人がやっていたのでAtcoder Beginners Selectionの最後の3問をやってみる。

ABC085C - Otoshidama

問題要約:

10,000円札、5,000円札、1,000円札を合計N枚使って、Y円を作ることができるか？

重要な制約として、$$1 ≤ N ≤ 2000$$というのがある。
これにより$$\mathcal{O}(n ^ 3)$$の解法、つまり各お札に対してループを回す全探索(3重ループ)はTLEになり通らないことがわかる。

※$$2000 ^ 3 = 8 * 10 ^ 9$$なので、時間の制約を超えてしまう。つまりTLEになる。

よくよく考えると、10,000円札と5,000円札の枚数を固定してしまい、
「残りの金額 = 1,000円札 * 残りの枚数」になっているかどうかをチェックすればいいことに気づく。
例えば、
$$58,000(9枚) = 10,000円札 * 5枚 + 5,000円札 * 1枚 + 1,000円札 * x枚$$
の場合は、
残りの金額 = 58,000 - (10,000 * 5 + 5,000 * 1) = 3,000円で、
残りの枚数 = 9 - (5 + 1) = 3枚となり、
$$3,000 = 1,000 * 3$$なので、組み合わせとして正しいことになる。

つまり、58,000円を合計9枚のお札で表すことは可能で、
その組み合わせのひとつは(10,000, 5,000, 1,000) = (5, 1, 3)ということになる。

これは10,000円札と5,000円札についてループを回すだけでよい$$\mathcal{O}(n ^ 2)$$の解法。
これでいいかんじにACできる。

もう一歩踏み込んで考えてみる。

$$58,000 = 10000 * i + 5000 * j + 1000 * k \cdots (1)$$
$$ 9 = i + j+ k \cdots (2)$$

ここで例えば$$i = 5$$とすると、(1), (2)から次の式が導ける。

$$8,000 = 5000 * j + 1000 * k \cdots (3)$$
$$4 = j + k \cdots (4)$$

この(3), (4)の連立方程式を解けばj, kが求まるので、$$\mathcal{O}(n)$$でやれた。

n, y = gets.strip.split.map(&:to_i)
a, b, c = -1, -1, -1

(0..n).each do |i|
    k = (5000 * (n - i) - (y - 10000 * i)) / 4000
    j = n - i - k

    c1 = j >= 0 && k >= 0
    c2 = i + j + k == n
    c3 = 10000 * i + 5000 * j + 1000 * k == y

    if c1 && c2 && c3
        a, b, c = i, j, k
        break
    end
end

puts "#{a} #{b} #{c}"

ABC049C - 白昼夢 / Daydream

問題要約:

空文字Tに'dream', 'dreamer', 'erase', 'eraser'の4つの単語を末尾にくっつける操作を行って、文字列Sが作れるか？

例えば作るべき文字列Sがerasedreamだった場合、まず空文字Tの末尾にeraseをくっつけて次にdreamをくっつければ作れる。
ということで、前から見ていって実際に文字列Sが作れるかどうかを判定しようとすると、WAになってしまう。

例えば作るべき文字列Sがdreameraseだった場合、
前から見ていって最初はdreamerだな、としてしまうと残りがaseになるので、これは作れないなと判定してしまう。
しかし実際にはdream + eraseで作れてしまうという罠。
じゃあdreamとdreamerで短い方から試せばいいじゃんと思うが、それもだめ。
例えば作るべき文字列Sがdreamereraseの場合は、最初にdreamを選んでしまうと間違ってしまう。
じゃあdreamとdreamerの場合で分岐させて、最終的に作れた方を採用すればいいんじゃ？と思ってしまうけど、
これは文字列Sの長さが$$10 ^ 5$$もある制約があるので、無理そうだとわかる。

なぜかというのをコードで書いてみると

words = ['dream', 'dreamer', 'erase', 'eraser']
ave_length = words.map(&:length).inject(:+) / words.size.to_f

# 文字列Sを構成する部品の平均文字数
p ave_length # => 5.75

# 仮に文字列Sを構成する各文字列の長さが10文字だったとしても
# 文字列Sの長さは 10 ^ 5もあるので、
count = 10 ** 5 / 10

# 文字列Sを構成する部品のおおよその数
p count # => 10000

# つまり'dream'にするか'dreamer'にするか、
# または'erase'にするか'eraser'にするかをその都度選択していくと
# これだけの分岐が生まれる
branch = 2 ** 1000
p branch # めちゃでかい！！！！

ってことこで、これは到底探索するのは無理。

実はこういう文字列系の問題には定跡みたいなものがあって、ずばり後ろからみるということ。

例えば作るべき文字列Sがdreameraseだった場合、
後ろからみてみると、まずeraseで次にdreamなのがわかる。

作るべき文字列Sがdreamereraseの場合、
後ろからみてみると、まずeraseで次にdreamerなのがわかる。

あとは実際に後ろからみていってマッチする単語の部分を消していって、ぴったり空文字になればおk。 ざっくり$$|S| * 4 = 10 ^ 5 * 4$$なので計算量的にも大丈夫。

s = gets.strip

words = ['dream', 'dreamer', 'erase', 'eraser']

until s.empty? do
    matched = false
    words.map do |w|
        if s[-w.size, w.size] == w
            s = s[0..-w.size - 1]
            matched = true
            break
        end
    end

    unless matched
        puts 'NO'
        exit 0
    end
end

puts 'YES'

ABC086C - Traveling

問題要約:

グリッド上の各点への移動が制限時間内に可能か、またちょうどその点にいることが可能か、全部試して

全ての地点への移動が時間内に可能かを実際に試せばいい。

例えば(3, 1, 2)から(6, 1, 1)なら、(1, 2)地点から3秒後に(1, 1)地点に行けるかを考える。
この場合だと(1, 2) -> (1, 1) -> (1, 0) -> (1, 1)みたいに移動すれば可能。

チェックすべき条件は２つあって、まずそもそも時間内に到達できるか？という条件。
例えば(0, 0)から3秒後に(100, 100)へは当然行けない。1秒につき上下左右のどこかへ移動するだけなので。
この条件をチェックするには、2点間のマンハッタン距離と時間を比べればいい。
(グリッド上を移動する場合は、マンハッタン距離が最短距離であり、この場合は最短時間にもなる。)

もうひとつは、時間内に到達可能だとして、その時間ちょうどにその地点にいることはできるか？という条件。
これはその場にとどまることは出来ないという重要な制約に基づくもの。
例えば、(0, 0)から4秒後に(1, 0)にいることは可能かどうかを考えてみると、
4秒あれば(1, 0)にらくらく到達可能ではあるけど、4秒後にちょうど(1, 0)にいることはできないことに気づく。

これが5秒だったらどうだろう？
(0, 0)から(1, 0)へは、最短で1秒で移動できる。そこで残りの4秒をじっとすることはできないので、
とりあえず右の(2, 0)にいってみる(2秒目)。
次に左に戻って(1, 0)に行く(3秒目)。また右の(2, 0)に行く(4秒目)。最後に左に戻ると目的地の(1, 0)にいることができる。

つまり、最短で目的地点に着いた場合に、残りの秒数を消化してまた目的地点に戻るためには最低2秒必要だということがわかる。
この調整は何度でも繰り返すことができるから、2n秒残っていればいい。
よって、目的地までの最短秒数を引いた残りの秒数が偶数になっていれば、時間ちょうどにその地点にいることができることがわかる。

この2つのチェックを全ての移動について行えばおk。

n = gets.to_i
data = n.times.map { gets.strip.split.map(&:to_i) }

def is_reachable?(current, next_data)
    tc, xc, yc = current
    tn, xn, yn = next_data
    dist = (xc - xn).abs + (yc - yn).abs
    
    return false if dist > tn - tc

    ((tn - tc) - dist).even?
end

current = [0, 0, 0]
data.each do |d|
    unless is_reachable?(current, d)
        puts 'No'
        exit 0
    end
    current = d
end

puts 'Yes'

おしまい。