近況
AtCoderの問題を解いて、コーディングの練習をしていますが、
最近はC問題にも手を出し始めました。
それに伴い、A・B問題ではあまり気にしなくてよかったことを気にしなくては行けなくなってきました。
処理速度について
そう、それはプログラミングの処理速度です。
分岐や繰り返し文を必要以上に書いてしまうと、
入力値の桁が大きすぎて、制限時間以内に処理が終わらず不正解となってしまいます。
プログラミングの勉強のため読んだ本でも、仕事でも、
「分岐や繰り返しは多くなるとよくない」と散々聞いてきましたが、
「ネストが深くなって読みにくくなるくらいでしょ？」
「別に何億とかの処理繰り返すわけでもないし、for文の中でさらにfor文回しても問題ないでしょ？」
くらいに思って、処理を最小限にする・無駄な計算はしない、ということはとりあえず二の次に考えていました。
何で躓いたか
それを考えなければ行けなくなったのが、以下の問題
こちらの問題
N M
L1 R1(例:1..3)
L2 R2(例:2..4)
⋮
LM RM
という入力値が与えられるので、M 行存在するL..Rの数字の中に、
いくつ重複が存在するかを数える問題です。
例えば、上の例だと、{1,2,3}と{2,3,4}の中には、
重複している数字は3なので、答えは1となります。
最初どうやって解いたか
では、この問題に私が最初どう解いたかというと、
以下のようなコードです。
_n,m = gets.split(' ').map(&:to_i)
can_pass = []
existed = []
(m).times do |a|
l,r = gets.split(' ').map(&:to_i)
if a == 0
existed = (l..r).to_a
else
can_pass = (l..r).to_a
existed = can_pass & existed
end
end
puts existed.length
変数existedとcan_passの中身を比較して、
重複している部分をexistedに残していって、
最後まで残った数字の数を数えるという方法です。
sampleでも全部期待している値が出たから、
これは正解だろうと思って提出しましたが、
結果がこちら。
見事に制限時間をオーバーしております....
何が問題か
処理速度についてあまり今まで考えたことがなかったので、正直困りました。
「そんなポンポン解放思いつくわけないだろう...」と。
この解き方の何が悪いかと考えてみると、
M回(最大10^5回)繰り返して、1≤Li≤Ri≤N(最大10^5個)の数字を検索して、いるため、
M*N回文処理が行われていることが問題でした。
どのように解決したか
そこで私がどのように解いたか、というのが
以下のような方法です。
_n,m = gets.split(' ').map(&:to_i)
l = []
r = []
m.times do |a|
single_l,single_r = gets.split(' ').map(&:to_i)
l << single_l
r << single_r
end
array = (l.max..r.min).to_a
puts array.length
まずLとRをそれぞれの配列に格納し、
Lの最大値とRの最小値、つまり、M行存在するL..Rの数字に重複している数字を、
数えて来るという方法にしました。
これにより、処理を行う回数は、M回となるので、
無事、制限時間内に回答が出力されるようになりました。
学び
解説を見てみると、他の解放もあるようでしたが、
すっと頭の中に入ってこなかったため、自分の解法しか理解できていないのですが、
別のやり方でもM回の処理で回答を出力することが可能なようです。
問題文を見て、頭の中で回答を考えて、コードを書くとなると、
どうしても原始的に1から10まで、
問題に書かれている処理を実装しようとしがちです。
ですが、そのまま処理すると必要以上に計算に処理がかかってしまったりすることがあるため、
出来るだけ無駄をなくすためにできる処理の方法がないかということを、
常々考えながら、コーディングしていくことが大事だと感じました。
他にもっと良い解法があるのか、他の人の回答を見て勉強しようと思います。