📑

ABC365 C Transportation Expensesを理解し忘れないようにする

2024/08/06に公開

本記事を書いた意図

ABC365Cが解けなかったので理解する。それだけだと忘れる+人に説明する代わりにzennでのアウトプットで理解度を深める

https://atcoder.jp/contests/abc365/tasks/abc365_c

問題の概要

N人それぞれに交通費の補助が割り当てられるが、その合計がM円をギリギリ超えないように交通補助費の上限値を求める。

解き方

交通補助Xを0から限界値+1(10^9+1)から2分探索して問題文通りの計算を行い、⚪︎と×の境界値を見つける。
あとは境界値の⚪︎を出力すればいい。
2分探索を行っているから計算量はlog10^9、問題文通りの計算はN回、よって計算量は(Nlog(10^9))となる。

回答コード

https://atcoder.jp/contests/abc365/submissions/56414785

参考元

ABC365Cの解説放送

Discussion