NoviSteps3D
面白かった！ 問題へのリンク editorials 問題概要 3 つの文字 B, Y, K からなる長さ の文字列 が与えられる。 この文字列をいくつかの区間に分割する。各区間について、 ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得 …
ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった！！ 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…
面白かった！！ 問題へのリンク 問題概要 人がいて、それぞれ正直者であるか、嘘つきであるかのいずれかである。また、各人は混乱していないか、混乱しているかのいずれかである。 混乱していない正直者は、常に正しいことをいう 混乱している正直者は、常に…
「二項係数の和」は結構なんとかなることを学んだ！ 備忘録程度に書く。 問題へのリンク 問題概要 下の図のように、 グリッドを、レベル の L 字で隙間なく埋め尽くす (レベル の L 字の定義は問題文参照)。 マス を指定したとき、次の 回のクエリに答えよ。…
実装が少し大変だった。そして、両端から Greedy で追い詰めていけばよいのは思いつかなかった。チームメイトが思いついていた。 問題へのリンク 問題概要 1 から までの整数が書かれたカードが合計で 枚あり、整数 の書かれたカードは 枚ある。各 に対して…
で解けた！ 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…
とても面白かった。場合分けを詰め切るが大変だった。 問題へのリンク 問題概要 橋がただ 1 つだけ存在するような連結で単純な無向グラフをハシポンとよぶ。 頂点数 、辺数 の連結で単純な無向グラフが与えられる。このグラフに辺を追加することで、ハシポン…
"142857" はエニアグラムやっていたら毎日目にする。エニアグラムは競プロの役に立つ！ 問題へのリンク 問題概要（output only） 正整数 と文字列 の組であって以下の条件を全て満たすものを 1 つ挙げよ。 は 0 から 9 までの数字からなる長さ 5000 以下の文…
面白かった！ カタラン数的なものが登場する。 問題へのリンク 問題概要 制約 考えたこと まずすぐにわかったことは、 の中に、1 が 2 個以上あってはダメ の中に、1 が末尾以外の場所にあってはダメ ということだった。そうすると、 は次のいずれかの形にな…
公式解説の方がシンプルだった。 問題へのリンク 問題概要 の順列 と、整数 が与えられる。 の連続する 個の要素からなる区間（ 通りある）をランダムに選び、さらにその区間をランダムシャッフルする。 最終的な順列の転倒数の期待値を mod 998244353 で求…
すごく面白かった！ 問題へのリンク 問題概要 二次元平面上に点 と という 個の点がある。同一直線上に 3 点が乗ることはない。 の順列 であって、次の条件を満たすものが存在するかどうかを判定し、存在するならば 1 つ示せ。 【条件】 に対して、2 点 , を…
繰り上がりがあるから、ただの「桁 DP」よりは難しい。でも少しの工夫で解ける！ 問題へのリンク 問題概要 1 個の正の整数 が与えられる。次の条件を満たす整数 が存在するような整数の組 の個数を 1000000007 で割った余りを求めよ。 xor = 制約 考えたこと…
Euler Tour して、遅延評価セグ木（区間加算 + 区間 min）に乗せて......という解法を考えていたところに、あまりにもシンプルな想定解法を目にして、感動した！ 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる。 に対して、次の問に答えよ。 個…
面白かった！ 問題へのリンク 問題概要 人がいて、人 の考察力、実装力、運はそれぞれ である。 これら から 3 人を選ぶ。ただし、3 人全員について「考察力・実装力・運のうちのいずれかについては他 2 人よりも真に高い」という条件を満たさなければならな…
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
平面走査の典型問題だけど、とにかく重くて辛かったのと、コーナーケースになかなか気づけなかった。 問題へのリンク 問題概要 数直線上に 個の区間がある。区間 は である ()。 = 区間 が、与えられた 個の区間のうち何個と交差するか としたときに、 の範…
苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x：集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x：集合 に…
「回数の期待値」は、(k 回以上の確率) の総和に一致する！！ あとは有名な「 個の一次関数の積は二分木のような計算順序で の計算量で求められるという話！ 問題へのリンク 問題概要 色が であるような靴下が 枚ずつある。いずれも 2 種類以上ある。 これら…
これは面白かった。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすものの個数を 998244353 で割った余りを求めよ。 について、 である 制約 考えたこと グラフの問題として考えることにした。つまり、0-indexed で表現すると 頂点数 、…
本当に色んな解法がある問題っぽい！！ 問題へのリンク 問題概要 頂点 の 頂点からなる無向グラフがあり、最初は辺がない。以下の 2 種類のオンラインクエリに答えよ。 クエリタイプ 1：頂点 間に辺を結ぶ クエリタイプ 2：頂点 の双方に隣接する頂点がある…
いかにも JOI にありがちな添字の持ち方をする DP！ 問題へのリンク 問題概要 英小文字と英大文字からなる長さ の文字列 と、長さ の文字列 が与えられる。また 0 以上 3 以下の整数 が与えられる。 次の条件を満たす文字列 の長さの最小値を求めよ。 は、英…
モノグサでバチャやって、なんとか通した！ 問題へのリンク 問題概要 の順列 が与えられる。この順列に対して「2 個の要素を選んで swap する」という操作を実行して、 「順列から誘導される Functional Graph の連結成分の個数が 1 個」 という状態を実現し…
Project Selection がピッタリハマる問題！ 問題へのリンク 問題概要 個の家 がある。家 に入るためには のコストがかかるが、その代わり の利得が得られる。また、各家 に対して、次の 個の制約条件が付随している。 家 に入ることなくして、家 に入ること…
Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…
大好き！！ガウス整数の問題リストがまた 1 個増えた！ 問題へのリンク 問題概要 1 つの正の整数 が与えられる。 二次元平面上の任意の格子点を頂点としたグラフにおいて、距離の平方が であるような 2 点間に辺を張っていく。 こうしてできたグラフの連結成…
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
点素パスのパッキング系の問題、出ないな〜〜と思っていたら出た！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。3 頂点 が指定される。 2 頂点 を端点とする単純パスであって、頂点 を通るものが存在するかどうか判定せよ。 制約 …
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
D 問題の MaxFlow に続いて、これまた、人生で一度は解くべき超典型問題ですね。そして、D 問題とは違うやり方で、二部グラフを作ることにも注目です！ 問題へのリンク 問題概要 のグリッドがあり、各マスには数値が書かれています。 これらのマスからいくつ…
セグ木上二分探索使ったというコメントをよく見たけど、僕の方針でも使うことになった 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き無向グラフが与えられる。 日目、 個の頂点 がウィルスに感染した。一度ウィルスに感染した頂点はずっと感染し…
