今日は遅めに起きて、不動産屋に行くかーと思ったら、『殺し屋1』のKindle版が1巻5円で売っていたので全巻まとめて50円で買ってずっと読んでいた。
不動産屋をはしごして解約と契約をしに行かなきゃならなかったのにずっと読んでいた。やばい。不動産屋には結局行かなかった。やばい。 火曜日のお昼に絶対に行こう。暑くてもくじけない。夕方になって少し涼しくなったらWF-1000XM3着けて軽く散歩した。

AtCoderの問題解いてて思ったことがあった。この問題自体はずっと前にやってて、この前ブログにも書いたけど。

ABC085C - Otoshidama

問題：

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

この問題の場合、各お札についてループを回す$$\mathcal{O}(n^3)$$の解法は、最速の言語でも実行時間の制限を超えてしまうので通らない。
こんな感じ。

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

(0..n).each do |i|
    (0..n).each do |j|
        (0..n).each do |k|
            if 10000 * i + 5000 * j + 1000 * k == y
                a, b, c = i, j, k
            end
        end
    end
end

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

なので計算量を落とすことを考えるんだけど、少し考えると、最初の2つのお札の数を決めてしまえば、あとは辻褄があうかチェックすればよくて、2重ループつまり$$\mathcal{O}(n^2)$$で解けることがわかる。
こんな感じ。

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

(0..n).each do |i|
    (0..n-i).each do |j|
        if 10000 * i + 5000 * j + 1000 * (n - i - j) == y
            a, b, c = i, j, n - i - j
        end
    end
end

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

これでも実行時間の制限をクリアできて正解になるんだけど、もう一歩踏み込んで考えると、連立方程式を解けば$$\mathcal{O}(n)$$で解けることがわかる。
こんな感じ。

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

#   y = 10000∗i + 5000∗j + 1000∗k
#   n = i + j + k
# なので、iを固定してj, kの連立方程式を解けばいい

(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}"

今回は制約のせいで$$\mathcal{O}(n^3)$$が通らなかったけど、この制約がゆるくて$$\mathcal{O}(n^3)$$でも問題なかったときに、この3つのなかでどれが一番いいコードなのって気になった。

$$\mathcal{O}(n^3)$$のやつは、コメントなくても何やってるかめちゃわかりやすいしバグも入りづらそうだなって思うけど、もちろん時間計算量が終わってる。

$$\mathcal{O}(n^2)$$のやつは、ちょっとだけわかりづらくなった(でもちょっとコメントあればわかる程度)代わりに時間計算量はそこそこって感じ。

$$\mathcal{O}(n)$$のやつは、めちゃ計算速いけど、わかりづらいし、人間がわざわざ連立方程式を解いてそれをコードに落とし込むのってどうなのって気持ちがちょっとある。

コンテストとかだと連立方程式解いてる時間なんてないから$$\mathcal{O}(n^2)$$のやつ一択なんだけど、自由に時間使って書いて良いよって言われたらどれが良いのか迷う。
今は「コメントをちゃんと書いた上で$$\mathcal{O}(n)$$のやつ」かなああっていう気持ち。
結局求められる要件とかデータ量とか状況によるよなって感じになってもどかしい。
ご意見あるかたお待ちしています。あ、コメント欄ないんだった…。

夜はtrello登録して、やりたいことやることやってること読みたい本などを登録してみた。箱大事。
それとHabitifyを入れた。ゴムまりになっていく。