「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！ 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1：新たに要素 0 を挿入する（重複もあり） クエリタイプ 2：すでに挿入されているすべての要素に を足す クエ…

カッコ列に関連してシミュレーションしていく問題！ 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題！ 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…

データの持ち方をうまく工夫することで、計算量を改善する系の問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x：数列 をすべて に書き換える i x： に を足す i…

これを機会に SA-IS を整備した！ 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…

undo 付き Union-Find ってなんぞ！？ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。色が 種類あって、各頂点は のいずれかの色で塗られている。このとき、以下の条件を満たすような色の組 () の個数を求めよ。 個の頂点のうち、色…

mex！！！それにしても、ならし計算量解析系が来たのびっくり！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…

えーーー、300 点！？ 問題へのリンク 問題概要 二次元平面上に 点が与えられる。これらの点の x 座標、y 座標を抽出すると、それらは の順列となっている。 各 に対して、点 から 自分よりも x 座標と y 座標がともに大きな点 自分よりも x 座標と y 座標が…

早速遅延セグ木があればできる問題来た！！ AC Library の出番かと思った！！！ 問題へのリンク 問題概要 縦 マス、横 マスのグリッドがあり、はじめグリッドの中央 マスには黒い石が 1 個ずつ置いてあり、下辺と右辺の計 マスには白い石が 1 個ずつ置いてあ…

勉強になった...けど、これ知らずにできるもんなの！？ 問題へのリンク あと、LCM の最小値バージョンもある！ drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。 制約 …