2019-09-11から1日間の記事一覧
https://yukicoder.me/problems/no/878 前提知識 ダブリング 解説 https://yukicoder.me/submissions/377919 高い要素の個数を答える方針でしばらく考えていてダメだったので、 ちょっと言い換えを考えてみる。 区間が与えられた時に、先頭から順に最も近い…
https://yukicoder.me/problems/no/877 前提知識 セグメントツリーにセグメントツリーを乗せるテク 解説 https://yukicoder.me/submissions/377916 やりすぎ回答かもしれない。 maxという制約が入ったままだと問題としては扱いづらい。 なので、[l,r]という…
https://yukicoder.me/problems/no/876 解説 https://yukicoder.me/submissions/377914 問題をよく見ると、隣り合う数が異なる組+1を答える問題になっている。 つまり、数の実際の大小は特に意味がない。 加えて、今回は区間addのクエリもあるため、階差を使…
https://atcoder.jp/contests/abc140/tasks/abc140_f 解説 https://atcoder.jp/contests/abc140/submissions/7444067 まず、218は5*105くらいあるので、小さい数ではない。 割り当て問題としてマッチング問題があるが、そんな雰囲気は全然しない。 全然思い…
https://atcoder.jp/contests/abc140/tasks/abc140_d 解説 https://atcoder.jp/contests/abc140/submissions/7443535 400点にしてはだいぶ難しく見える。 回転というのは厄介か。 まず、重要な考察がいくつかある。 方向が一致してない箇所で幸福が1つ減る …
https://atcoder.jp/contests/abc140/tasks/abc140_e 解説 https://atcoder.jp/contests/abc140/submissions/7443801 総和を求める問題でよく使うテクであるが、「全てのパターンについてある値の総和」というのを 「(ある値×その値になる組み合わせ)の総…
https://atcoder.jp/contests/abc140/tasks/abc140_b 解説 https://atcoder.jp/contests/abc140/submissions/7443466 シミュレーションしていこう。 前に食べた料理の種類を記録しておけば、満足度Ciを得られるかどうかが分かる。 int N, A[20], B[20], C[20…
https://atcoder.jp/contests/abc140/tasks/abc140_c 解説 https://atcoder.jp/contests/abc140/submissions/7443482 なるべくA[i]を大きくするように考えたい。 A[i]中心に考えてみると、A[i]≦min(B[i-1],B[i])を満たす必要がありそう。 最大化したいので等…
https://atcoder.jp/contests/abc140/tasks/abc140_a 解説 https://atcoder.jp/contests/abc140/submissions/7443443 各桁についてN通りの候補があるため、答えはNNNになる。 つまり、N3を答えよう。 int N; //--------------------------------------------…