ABC223の参加記録です。
昨日のARC128で0完だったため、レートが50ほど下がりました。今日は少しでも取り戻せると良いなと思って参加しました。C問題までスムーズに解けて、Dが解けたらそこそこ上がるかな。と思って参加しましたがまさかAB2完で終わるとは。。。
この記事では、私が理解した内容でABC223のC問題までを振り返ります。レート600程度、使用言語はPython3です。
A – Exact Price
標準入出力と倍数判定が出来るかが問われる問題。
100の倍数判定は、100で割った余りが0かを調べればわかります。
0も100で割った余りが0になりますが、正の倍数ではないため、この問題の出力は”No”を出すようにしましょう。
サンプル3があってよかったです。サンプル3を試さなかったらWAになっているところでした。
# AtCoder Beginner Contest 223
# A - Exact Price
N=int(input())
if N==0:
print("No")
else:
print("Yes") if N%100==0 else print("No")
B – String Shifting
繰り返し処理と、文字列の操作、辞書順比較が出来るかが問われる問題。
文字列の操作はPython3だとスライスでうまくいきますね。
都度、辞書順比較で、最小のものと最大のものを保持しておけばOKですね。
# AtCoder Beginner Contest 223
# B - String Shifting
S = input()
N = len(S)
Smax = S
Smin = S
for i in range (N):
S = S[1:] + S[0]
if Smax < S:
Smax = S[::]
if Smin > S:
Smin = S[::]
print(Smin)
print(Smax)C – Doukasen
累積和と二分探索が出来るか、距離と時間の関係がわかっているかが問われる問題。
私はこの問題コンテスト中にACすることは出来ませんでした。
1か所直したらACしたので惜しいところまでは言っていたと思うのですが、詰め切れませんでした。
以下、この問題を解く方針を書いていきます。
- 導火線によって進む速度が異なるため、片方に火をつけて、すべて燃え尽きるまでの時間を計算する。
- 両端から火をつけた場合には、上記の時間の半分で2つの火がぶつかる。
- 半分の時間で、何個目の導火線までが燃え尽きているかを二分探索する。
- 燃え尽きた導火線の数から、燃え尽きた導火線の長さがわかる。
- 残り時間で導火線がどれだけ燃えるかを計算したら左からどれだけ燃やし尽くしたかがわかる。
# AtCoder Beginner Contest 223
# C - Doukasen
from bisect import bisect_right
N = int(input())
acc_doukasen = [0] # 導火線の長さの累積和
acc_doukasenpersec = [0] # 各導火線が燃え尽きる秒数の累積和
AB = []
for i in range (N):
A, B = map(int,input().split())
acc_doukasen.append(acc_doukasen[-1] + A)
C = A / B
acc_doukasenpersec.append(acc_doukasenpersec[-1] + C)
AB.append( (A, B, C) )
# 片方から火をつけて燃え尽きるまでの時間
all_time = acc_doukasenpersec[-1]
# 導火線の火がぶつかる秒数
mid_time = all_time / 2
# 導火線火がぶつかる一つ手前のインデックス番号を求める
bisect_index = bisect_right(acc_doukasenpersec, mid_time) - 1
# 答え用の変数に、導火線の累積距離を足す
ans = acc_doukasen[bisect_index]
# 火がぶつかる導火線の燃える時間を求める
rest = mid_time - acc_doukasenpersec[bisect_index]
# 答え用の変数に、火がぶつかる導火線で進む距離を足す
ans += rest * (AB[bisect_index][0] / AB[bisect_index][2])
print(ans)
コメント