トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

AtCoder Beginner Contest 103

[競技プログラミング,競プロ解説]

AtCoder Beginer Contest 103 - C

  解説

問題文

 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まで与えてその最大値を求めてやればいい
    • 当然TLE

解説聞いて

  • もうこれ全然思いつかんやん…
    • aN それぞれを -1 してやり、合計したものが答え
  • aN = [3, 4, 9] = [2, 3, 8] => 13
    • 13 % 3 = 1, 13 % 4 = 1, 13 % 9 = 4

AtCoder Beginer Contest 103 - D

  解説

問題文

 東西一列に並んだ N 個の島と N−1 本の橋があります。
 i 番目の橋は、西から i 番目の島と西から i+1 番目の島を接続しています。
 ある日、いくつかの島同士で争いが起こり、島の住人たちから M 個の要望がありました。
 要望 i: 西から ai 番目の島と西から bi 番目の島の間で争いが起こったために、これらの島をいくつかの橋を渡って行き来できないようにしてほしい
 あなたは橋をいくつか取り除くことでこれら M 個の要望全てを叶えることにしました。
 取り除く必要のある橋の本数の最小値を求めてください。
お名前: コメント: