きろく

特筆すべき記録のまとめ

2019-07-12から1日間の記事一覧

AtCoder Beginner Contest 130:F - Minimum Bounding Box

問題 解法 解答 問題 atcoder.jp 解法 x_max, x_min, y_max, y_min の座標となる点が変化するタイミングのみ調べればよい.なぜならば,変化するタイミング間では求める面積は広義単調増加・減少になるので,間ではなく両端のタイミングでその区間での面積の…

AtCoder Beginner Contest 130:E - Common Subsequence

問題 解法 解答 問題 atcoder.jp 解法 まず,問題文の解釈から.選んだ部分列の数字を文字列を連結させて読むのではなく,数列としてみたときに等しいものの個数を求める.例えば {1, 3, 3, 3} と {1333} は,各項を文字列としてみて連結させると同じものに…

AtCoder Beginner Contest 130:D - Enough Array

問題 解法 解答 問題 atcoder.jp 解法 ある区間 [l, r] の和が K 以上であるとき,区間 [l, r + 1], [l, r + 2], ... , [l, N] のそれぞれの和も当然 K 以上なので,各 l について最初に区間の和が K 以上となる r が分かればよい.この l, r は尺取り法によ…

AtCoder Beginner Contest 130:C - Rectangle Cutting

問題 解法 解答 問題 atcoder.jp 解法 与えられた長方形の重心を通るような面積を半分にする直線は,長方形の対角線である 2 本が考えられる.それ以外の点で半分にする直線は 1 本に定まる.O(1). 解答 atcoder.jp

プログラミングバトル 本戦 - BCU30:B - Interval Addition

問題 解法 解答 問題 atcoder.jp 解法 広義単調増加となっている部分列の個数が答えになる.無駄に最初から全体に +min(A) してから・・・などと考えると反例が出てくるので注意する(1 WA した). 解答 atcoder.jp