問題リンク 解法 $ O(N\log N) $ の解法です。 O(N2)でも間に合うのですが、制約を勘違いしていたので、O(NlogN)の解法を考えました。 まず、開区間のまま考えるとややこしいので全て閉区間に変換することを考えます。 $ l_i≠l_j, r_i=l_j $ の時、 $ [l_i, …

問題リンク B問題にしては難しかった。 解法 N回操作した後の赤色のボールの数はC×D×Nなので、一回の操作でC×D個の赤ボールを追加するとしても問題ない。 そうすると赤ボールの数が青ボールの数以上になるのはいつか、という問題になる。 一回の操作で赤ボー…

問題へのリンク 解法 最短経路を求めたりする問題ではないので、BFSではなくDFSがしたい気分になる。 制約がとても緩いので、全探索が有効そう。 スタート地点は最大でも16通りしかないので、すべてのスタート地点から探索を開始してみることにする。 DFSの…

問題へのリンク 解法 区間の和を求めるということでまずしゃくとり法が思いついた。 全体の総和をsumとして、x = sum/10 とすると、区間の総和がx以上になるまで右端を動かし続け、x以上になった時点で区間の総和がsumと等しいかを確認すれば良い。 また、su…

N進数→10進数の変換 Nの部分を変換して使いましょう。 numは任意のN進数です。 powはdouble型などを返すので、誤差に注意。(誤差が気になる場合は自作累乗関数を作ろう。) string str = to_string(num); long long n = 0; long long sz = str.size(); for (i…