AtCoder ABC 318 E - Sandwiches (緑色, 450 点)

AtCoder ABC-E 緑色diff 3つのものの真ん中に着目する 3つ組(i<j<k)の問題累積和累積和テク:左右両端からの累積和や累積結果を前処理 indexベースで考える数列解説あとで詳しく書く典型要素を詰め合わせた教育的問題ある量を固定して考える【問題集】累積和・二分探索法・しゃくとり法 AtCoder450点

色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。問題へのリンク問題概要長さの数列がある。各要素は以上以下の整数値である。制約メモ各値ごとに考えていった。つまり、として、について求めていった。各について、となる添…

2020-11-28

JOI 本選 2016 B - スタンプラリー２ (AOJ 0626, 難易度 6)

JOI JOI本選 JOI難易度6 AtCoder AOJ 3つのものの真ん中に着目する 0と1と2の問題最適化テク:最適解の形を考える累積和ある量を固定して考える N個のものうち1個を変更・削除したものを解く差分更新典型要素を詰め合わせた教育的問題最大スコア文字列スタンプ 3つ組(i<j<k)の問題解空間:O(N^2)通りの選択肢盤面を予め変更する操作操作:挿入【問題集】累積和累積和テク:条件を満たすものの個数を累積和で表す累積和テク:累積和や累積結果を前処理しておく【問題集】累積和・二分探索法・しゃくとり法【問題集】累積和・いもす法最適化問題

「3 つのものの真ん中に着目する」という典型が学べる。面白かった！問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さの文字列が与えられます。このような文字列のスコアを、以下の条件を満たす…

2020-10-14

AOJ 2959 Revenge of UMG (HUPC 2019 day2-H)

この問題のテスターをやってた！今流行の NTT 系問題！！しかも分割統治 + FFT というカッコいいやつ！！問題へのリンク editorial 問題概要 'U', 'M', 'G' のみからなる長さの文字列の UMG 数を、以下の条件を満たす添字の組の個数として定義する。 T[…

2020-04-12

AtCoder ABC 162 D - RGB Triplets (茶色, 400 点)

AtCoder AtCoder400点 ABC-D 包除原理補集合を考える数え上げ問題解空間:O(N^2)通りの選択肢 3つのものの真ん中に着目する半分全列挙文字列制約条件:等間隔茶色diff 3つ組(i<j<k)の問題典型要素を詰め合わせた教育的問題式変形等差数列 0と1と2の問題

落ち着いて頭を整理。。。問題へのリンク問題概要 'R', 'G', 'B' のみからなる長さの文字列が与えられる。の index の組であって、ととはすべて互いに異なるであるという条件を満たすものの個数を求めよ。制約考えたこと頭がごっちゃになりそ…

2018-08-28

AtCoder ABC 102 D - Equal Cut (ARC 100 D) (青色, 600 点)

しゃくとり法ある量を固定して考える全探索 3つのものの真ん中に着目する数列前処理二分探索累積和最大値と最小値の差を扱う問題 ABC-D AtCoder AtCoder600点累積和テク:左右両端からの累積和や累積結果を前処理青色diff ARC-D 均等に分けるそのまま覚えたいシンプル設定の中堅以上の典型問題中堅以上の典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題最小コスト最大スコア累積和テク:累積和や累積結果を前処理しておく【問題集】累積和【問題集】累積和・二分探索法・しゃくとり法最適化問題

かなり悩んだ問題へのリンク問題概要長さの整数列を 3 箇所で切って、4 つの連続する数列に切り分ける。このとき、4 つの区間の値の和をとするとき、の最小値を求めよ。制約考えたことこういうの、連続する区間が 4 個だけであることを活かす解法…

2018-08-05

AtCoder ABC 104 D - We Love ABC (青色, 400 点)

DP 数え上げ問題ナップサックDP 3つのものの真ん中に着目する ABC-D AtCoder400点 AtCoder DP状態:フェーズ(耳DP) ワイルドカード問題文字列青色diff 0と1と2の問題解空間:O(N^2)通りの選択肢 DP状態:照合文字列の何文字目まで到達したか典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題

これ好き！！！問題へのリンク問題概要 "BCABBACCBCCACA" のような A, B, C のみからなる文字列 S の「ABC 数」とは、 S[i] = 'A' S[j] = 'B' S[k] = 'C' i < j < k を満たすような (I, j, k) の組の個数のことである。今、 ????C?????B??????A??????? の…

2018-06-03

2018 codeFlyer 予選 C 徒歩圏内 (400 点)

しゃくとり法数え上げ問題 unrated公式コン AtCoder AtCoder400点 3つのものの真ん中に着目する前処理数列一直線上のN点の問題典型要素を詰め合わせた教育的問題 3つ組(i<j<k)の問題【問題集】累積和・二分探索法・しゃくとり法解空間:O(N^2)通りの選択肢補集合を考えるある量を固定して考える累積和テク:左右両端からの累積和や累積結果を前処理累積和テク:累積和や累積結果を前処理しておく

実装力って大事だなと。 Before: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2601840 After: https://beta.atcoder.jp/contests/bitflyer2018-qual/submissions/2603569 問題へのリンク問題概要長さの単調増加数列が与えられる。…

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

3つ組(i<j<k)の問題