A – Ferris Wheel
|
1 2 3 4 5 6 7 |
a,b = map(int, input().split()) if a>=13: print(b) elif 6<=a<=12: print(b//2) elif 5>=a: print(0) |
C – Prison
方針
・全ゲートをパスするIDの区間を作る
・区間の左側は1からスタートして最大値を、区間の右側はnからスタートして最小値を更新して区間を狭めていく
・区間内の数字が全ゲートをパスするIDであるため、区間に含まれる個数を出力
・左側の最大値が、右側の最小値よりも大きくなった場合は0を出力
※全ゲートが許可するIDの区間が重なっている必要があるが、以下の例ではゲート1とゲート2の両方をパスするIDは存在しない。
例：ゲート1をパスするIDが8~10、ゲート2をパスするIDが3~5の場合
→ゲート1(8,10)：×××××××(○)○○ ：(○)は左側の最大値8
→ゲート2(3,5) ：××○○(○)××××× ：(○)は右側の最小値5
解答
コード・コメント
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#入力 n,m = map(int, input().split()) #区間左側の最大値を1で初期化：右にスライドして更新していく left_index = 1 #区間右側の最小値をnで初期化：左にスライドして更新していく right_index = n #ゲートの数だけ繰り返し #left_indexは右に、right_indexは左にスライドすることで区間が狭まっていく for i in range(m): #入力 l,r = map(int, input().split()) #左側の最大値を更新 left_index = max(left_index,l) #右側の最小値を更新 right_index = min(right_index,r) #左側の最大値が、右側の最小値よりも大きい場合 if left_index > right_index: #0を出力：全ゲートをパスするIDが存在しない print(0) #前述のコーナーケース以外 else: #区間内の個数を計算：区間が[2,3,4]の場合、4-2+1=3となる。詳細は累積和で検索 ans = right_index - left_index + 1 #区間内の個数を出力 print(ans) |
コード
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
n,m = map(int, input().split()) left_index = 1 right_index = n for i in range(m): l,r = map(int, input().split()) left_index = max(left_index,l) right_index = min(right_index,r) if left_index > right_index: print(0) else: ans = right_index - left_index + 1 print(ans) |
参考
区間に関する問題なので、累積和に関する情報を事前に持っていると良いかもしれません。
累積和を実装して問題を解くことができずとも、考え方に触れておくだけで別の問題で解答に至りやすくなるのではないかと思います。
最後の”ans”で区間内の個数を計算する部分などはこちらの記事の2-2の項目に記載されています。
コメント