[AtCoder] ABC 172 C – Tsundoku

2020年7月25日

問題

方針

累積和と二分探索

机 \( A \) の本を \( i \) 冊読んだとき、机 \( B \) の本を最大でいくつ読むことができるかを考えます。机 \( A \) の本を \( i \) 冊読むのにかかる時間は、累積和で求めることができます。残り時間が \( t \) 分のとき、机 \( B \) の本を何冊読むことができるかは、累積和と二分探索で求めることができます。

しゃくとり法

しゃくとり法という言葉が適切かどうかは分かりませんが、似たような発想で解きます。まず初めに、机 \( A \) の本を最大まで読むことができる冊数を \( a \) とします。次に、机 \( A \) の本を \( a \) 冊読んだとき、机 \( B \) の最大まで読むことができる冊数を \( b \) とします。このとき、\( a + b \) 冊読んだことになります。次に、机 \( A \) の本を \( a – 1 \) 冊読んだとき、机 \( B \) の本をいくつまで読めるかを考えます。このとき、机 \( B \) の本は \( b \) 冊読めることが確定しているので、\( b + 1 \) 冊目以降から探索すれば良いです。したがって、机 \( A \) の本を \( a \) から \( 0 \) 冊まで読んだとき、机 \( B \) の本を最大でいくつ読むことができるかが分かります。

コード

累積和と二分探索

しゃくとり法