操作:挿入
公式解説の方がシンプルだった。 問題へのリンク 問題概要 の順列 と、整数 が与えられる。 の連続する 個の要素からなる区間（ 通りある）をランダムに選び、さらにその区間をランダムシャッフルする。 最終的な順列の転倒数の期待値を mod 998244353 で求…
「全体に足す」のは難しいから、足す値を別途持っておくというスキル！！！ 問題へのリンク 問題概要 以下の 個のクエリに答えよ。 クエリタイプ 1：新たに要素 0 を挿入する（重複もあり） クエリタイプ 2：すでに挿入されているすべての要素に を足す クエ…
苦手系の問題だけど、解けてよかった。 問題へのリンク 問題概要 正の整数 が与えられる。はじめ空である集合 が与えられるので、次のクエリに答えよ。 クエリタイプ 1 x：集合 に整数値 がない場合は挿入し、ある場合は削除する クエリタイプ 2 x：集合 に…
「戻す DP」または「FPS」で！ 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…
考察に時間をかけすぎた 問題へのリンク 問題概要 文字 'A' と 'B' のみからなる長さ の文字列 が与えられる (先頭の文字を 0 文字目とする)。各 について、次の問に答えよ。 Alice と Bob が交互に、以下の操作を合計 回行う。Alice が先手である。なお、最…
opt さん、とよさんと一緒に解いた。楽しかった！ 問題へのリンク 問題概要 数列 に対して、最大 回の操作を繰り返すことで順列 を作りたい。 回目の操作では、値 ( 以上 以下) を選ぶと、コスト がかかる 値 を選んだとき、数列の末尾 を取り出して、順番を…
とても面白かった。文字列に操作を 回施して、操作後の文字列の辞書順最小のものを求める問題。Suffix Array のよい練習問題でもある。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。この文字列に対して、以下のいずれかの作業…
よくあるデータ構造問題！！ めっちゃ色んな解法がある！ 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…
この問題、深く考えずに for 文回した人も多いと思う。実際それでも問題なく解ける！ 問題へのリンク 問題概要 英小文字のみからなる 2 つの文字列 が与えられる。 は に英小文字を 1 つ挿入して作られたことがわかっている。 挿入された文字は の先頭から何…
こういうの最初は手で様子を掴むようにしているのだけど、どのタイミングで PC 実験開始しようか悩む。 問題へのリンク 問題概要 整数 と 4 つの文字 が与えられる (いずれも "A" または "B") すぬけ君は文字列 を持っている。 ははじめ "AB" である。すぬけ…
「3 つのものの真ん中に着目する」という典型が学べる。面白かった！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…
こういう条件を言い換えながら数え上げる問題好き！ 問題へのリンク 問題概要 タプリスちゃんは現在、長さ 1 の数列 を持っている。 タプリスちゃんは に対して、以下のいずれかの操作を選んで行うことを 回繰り返すことにした。 の末尾に または を追加する…
とてもシンプルな設定で面白かった！でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…
実は、元の文字列の形はどうでもよくて、文字列の長さだけが重要という！！！ 問題へのリンク 問題概要 長さ の英子文字からなる文字列 が与えられる。これに以下の操作をちょうど 回行ってできる文字列が何通り考えられるか、1000000007 で割ったあまりを求…
少しでも実装を楽にしたい 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。以下の操作を最小回数行って回文にしたい。その最小回数を求めよ。不可能な場合は -1 を出力せよ。 のどこかに 'x' を挿入する 制約 考えたこと まず可…
超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…
本番フローで無理矢理解いた！！！ でも DP が本筋だね。 問題へのリンク 問題概要 の順列 が与えらえる。これを 整数 を選んで区間 [ ) を左シフトする、すなわち をそれぞれ へ置き換える、これにコスト がかかる 整数 を選んで区間 [ ) を右シフトする、…
順列において、要素をどこかに挿入する系の操作をする問題は典型ではある。こういうのをしっかり押さえたい。 問題へのリンク 問題概要 の順列が与えられる。 以下の操作を繰り返してソートされた状態にしたい。最小回数を求めよ。 要素を 1 つ選んで、任意…
好き！！！！！でも A 問題としてはかなり難しいね。 問題へのリンク 問題概要 数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に …
