操作:2つのものを1つにマージ
で解けた！ 同じ値が連続する場合の対処に苦慮した。 問題へのリンク 問題概要 強さが のスライムが一列にこの順に並んでいる。 に対して、次の問に答えよ。 【問】 初期状態で左から 番目にいるスライムが高橋君である。高橋君が下記の行動を好きな回数だけ…
すごく悩んだけど、なんとか解けた！ 問題へのリンク（仮） 問題概要 次の図のように、木を、文字 (、)、1 からなる文字列で表す（異なる木が同じ文字列になることもある）。文字列の生成規則は次のように表される。 E ::= ‘1’ | ‘(’ E E ‘)’ 詳細は問題文を…
連想配列で集計するといい感じに解ける！ 問題へのリンク 問題概要 枚の靴下があって、靴下 の色は という整数値で表される。 色の等しい靴下をペアにするとき、最大で何ペア作れるか？ 制約 考えたこと 次のように考えたい。 色ごとに靴下が何個あるかを整…
スタックのいい練習問題！ 問題へのリンク 問題概要 空の列と 個のボールがある。 番目のボールの大きさは である。これから 回の操作を行う。 回目の操作では、 個目のボールを列の一番右に付け加えた後、次の手順を繰り返す。 列にあるボールが 1 つ以下な…
こういう値を順次更新していくようなシミュレーションは慣れておきたい！ 問題へのリンク 問題概要 元素 がある。 元素 を合成すると、 のときは元素 になり、 のときは元素 になる。 元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素…
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです！ 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…
ビットベクターで高速化するのは、いつも見落としてしまう！ 問題へのリンク 問題概要 円環状に 個の魔法石があり、 番目の魔法石は、価値が 、色が である。色は 1 以上 50 以下の整数で表される。 今、これらの魔法石に対して、隣り合う魔法石の色の差が …
平衡三進法！ 問題へのリンク 問題概要 次の条件を満たすサイズ 9 の整数列 を求めよ。 である 以上 以下の任意の整数 に対して、次の操作を繰り返す操作列が存在して、整数列中に整数 が存在する状態にできる 操作 1：数列から 2 つの要素 を選び、その 2 …
下手を打つと密なグラフになって TLE してしまう！！ スーパーノードを作ることでグラフを sparse にするテク！ 問題へのリンク 問題概要 以上 以下の整数値からなる 個の有限集合 が与えられる。 以下の操作を最小回数繰り返すことによって、「 と をともに…
これをグラフの問題だと思えるかどうか！ 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…
コンテスト中に間に合わなかった。あと、僕の考察は XOR の言葉ではなかったけど、よく考えたら XOR と等価だった。 問題へのリンク 問題概要 "A", "B", "C" のみからなる長さ の文字列 が与えられる。この文字列に以下の操作を好きな順序で好きな回数だけ行…
こどふぉ特有の、ややギャグ要素ありの楽しい問題。結構好き。 問題へのリンク 問題概要 長さ の正の整数からなる広義単調増加な数列 が与えられる。以下の操作を何度か行うことで、広義単調増加ではない状態にしたい。 数列の隣接する 2 つの要素を選んで、…
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
操作が「Euclid の互除法」っぽくなっている系の問題！！！そういう系の問題は次の一覧で示してる drken1215.hatenablog.com 問題へのリンク 問題概要 個の正の整数 に対して次の操作を繰り返し行う。 個の整数の最大値を 、最小値を とする。 なら手続きを…
一瞬コーナーケースがないかと怖くなる 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。 文字列の各…
実装を柔軟にしたい 問題へのリンク 問題概要 体のスライムがあって、初期状態では、それぞれの色は となっている。以下の操作を繰り返すことで全てスライムを消滅させたい。そのために必要なコストの最小値を求めよ。 色 のスライムを消滅させる (コストは …
区間 DP な問題って、あまり見なくなったなと。貴重なので記録。 問題へのリンク 問題概要 長さ の数列 が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 隣接する二項を選び、それらの値が等しいとき (v とする)、その 2 つの値を削除して、…
復元つらい 問題へのリンク 問題概要 黒板に 個の整数 が書かれている。 書かれている数字から 2 個選んで として、これらを消して を新たに書き加える という操作を 回行って最後に残る整数の最大値を求めよ。またそれを達成する操作列を復元せよ ( を毎タ…
教育的！！！ 問題へのリンク 問題概要 個の正の整数 が与えられる。今、以下の操作を好きな回数だけ行う。 個から 2 つの正の整数 () を選んで、 を で置き換える この操作を行うと、最終的には 個の と 1 個の正の整数が残る。残る整数の最小値を求めよ。 …
2 日目：AGC 027 E - ABBreviate (1300 点)https://t.co/mvWcvtxfRz3 で割った余りについて不変量であることは既出。重複を除くために「文字列の部分文字列の数え上げ」的な考え方をするのも恐らく典型。自力で詰め切るのはまだ辛いけど「赤くならないうちは…
の Kruskal 法ではダメで、 な Prim 法なら OK という稀有なパターンの問題。Dijkstra 法でも priority_queue を使ったやつは 愚直なやつは と二種類の実装があって前者の方が速いと言及されるケースも多いけど、密グラフ ( なグラフ) では後者の方が速い。P…
