AtCoder Beginner Contest (ABC) 223 PythonでC問題解いてみた
前回解いたやつ
こんにちは。メリーです。
valorantでゴールドとシルバーを行き来しております。
打ち合い時にしゃがむ癖があり、そのせいでヘッドショットに入らないので、修正したいところです。
あと、キルジョイのセットアップの知識量増やしたい・・・
ということで、今日も今日とてAtCoder Beginner Contest (ABC) 223 のC問題解いていきます。
言語はPython、提出はPyPyです。
今回は答えを見ずに解けたので自信付きました。
目次
C問題 熟考編
問題文
いろんな種類の導火線をパッチワークのようにつなぎ合わせ、導火線の左右から同時に着火。
導火線の火がぶつかる場所はどこかな?という問題。
というわけで方針を考えていきましょう。
まず、導火線の火がぶつかるときはどういうときか。
そう、導火線が全て燃え尽きたときですね。
更に考えると、導火線の左の火と右の火が同じ時間だけ燃えたときですよね。
これら2つのことを組み合わせて、導火線の片側からのみ火をつけて、燃え尽きた時間の半分の時間の地点が求めるものになります。
なので、方針は
1. 導火線の片側からのみ着火した場合の燃え尽きる時間を求める。
2. 1を2で割ったものを記録する。
3. 左側から着火した時、2の時間に火がついている地点を求める。
ということです。
C問題 コーディング編
それではコードを書いていきましょう。
n = int(input()) a = [] b = [] for i in range(n): A,B = map(int,input().split()) a.append(A) b.append(B) jikan = 0 for i in range(n): jikan += a[i]/b[i] a_time = jikan/2 jikan = 0 long = 0 for i in range(n): jikan += a[i]/b[i] long += a[i] if jikan > a_time: jikan -= a[i]/b[i] long -= a[i] time = a_time - jikan long += time * b[i] break print(long)
ではコードの解説を。
for i in range(n): jikan += a[i]/b[i]
このループでは、方針の1をやっています。
導火線iが燃え尽きるのにかかる時間はその導火線の長さ÷速度です。
各導火線が燃え尽きるのにかかった時間を加算していくと、全て燃え尽きるまでにかかる時間がわかります。a_time = jikan/2
で方針2のことを行っています。着火してからa_time秒後の地点を求めればよいのです。方針3は以下のコードです。
for i in range(n): jikan += a[i]/b[i] long += a[i] if jikan > a_time: jikan -= a[i]/b[i] long -= a[i] time = a_time - jikan long += time * b[i] break
jikanはこのコードの直前でリセットしてます。
このコードで、a_time秒後に何本目の導火線に火がついているのかを求めてます。
それをif文でチェックしてます。(a本目までの導火線が消えた累計時間がa_timeを初めて超えた時、a本目の導火線の最中で燃え尽きる。)
なので、求める地点は、a-1本目までの導火線の累計距離 + a本目の導火線が消えた距離。
そして、a本目の導火線が消えた距離は、(a_time - a-1本目までが全て燃えるのにかかった時間) × a本目の導火線の燃える速度で求められます。
また、if文で、longとjikanをそれぞれマイナスしてるのは、マイナスしないとa本目まで燃え尽きた時のlongとjikanが求まっちゃうからです。
最後に求めたlongを出力して終了です。
今回の問題は答えを見ずに解答できたのでとっても自信が付きました。
また、茶色に近めの難易度だったので喜びも大きいです。
明日も頑張っていきたいです!!!!
それでは。