[競技プログラミング,競プロ解説]
N 個の正整数 a1,a2,...,aN が与えられます。
非負整数 m に対して、f(m)=(m mod a1)+(m mod a2)+...+(m mod aN) とします。
ここで、X mod Y は X を Y で割った余りを表します。
f の最大値を求めてください。
- f(m)は簡単に実装できるから、それにmを1〜10^5まで与えてその最大値を求めてやればいい
- もうこれ全然思いつかんやん…
- aN それぞれを -1 してやり、合計したものが答え
- aN = [3, 4, 9] = [2, 3, 8] => 13
- 13 % 3 = 1, 13 % 4 = 1, 13 % 9 = 4
東西一列に並んだ N 個の島と N−1 本の橋があります。
i 番目の橋は、西から i 番目の島と西から i+1 番目の島を接続しています。
ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。
要望 i: 西から ai 番目の島と西から bi 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい
あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。
取り除く必要のある橋の本数の最小値を求めてください。
