パリティ
ずっと前にこれを作問して出題していたので記録を。 時は流れて AGC 026 D - Histogram Coloring でよく似た設定の問題が出たときはビックリした (実際はそんなに似てない)。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '0', '1', '?' のい…
これ、てんぷら君のおかげで随分とシンプルな問題になった！ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…
こないだの ARC でめっちゃ似た問題が出たので！これは、SolveMe を含む、りんごさんによる伝説のセット。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 のグラフが与えられる (入力は の隣接行列で与えられ、初期状態では非連結である)。この…
これの原案だった！！ 「対称戦略」が印象的なゲームの問題を作ろうとして作った 問題へのリンク editorial 問題概要 1 × 1 × 1 の立方体を の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。 交互に、直方体のある面のあるマスを選んで…
とてもシンプルな設定で面白かった！でもバグらせてそうで、提出するのは怖かった。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。初期状態では頂点 1 と頂点 は非連結である。 先手と後手が、交互に 1 本ずつ辺を追加していく。た…
これ結構好き！ 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき)：コインが入…
kirika さんの「整数論テクニック集」より。 問題へのリンク 問題概要 二次元平面平面上において から の合計 8 方向に移動できる。今、 個のクエリが与えられる。各クエリは座標 が与えられる。原点から出発して、上述の移動を好きな順序で好きな回数だけ繰…
きちんと細部まで詰めるのが大変かもしれない 問題へのリンク 問題概要 時刻 に座標 にいるとき、以下のいずれかの行動をすることができる。 が偶数または が偶数のとき、時刻 に に移動する が奇数または が偶数のとき、時刻 に に移動する が偶数または が…
こういうの楽しいよね！ 問題へのリンク 問題概要 個のマスが横一列に並んでいます。各マスは赤、青、黄、緑のいずれか 1 色で塗られている ("RBYG" からなる長さ の文字列 で与えられる)。 以下の操作を好きな順序で好きな回数だけ行えます。文字列 を作る…
ちょっと場合分けが怖い問題だけど、最後の動きは「ちょうどゴールにならないと、上がれないすごろく」を思い出すと納得できそう！ 問題へのリンク 問題概要 現在、座標 にいる。以下のいずれかの操作をちょうど 回行う。 座標 にいるとき、 に移動する 座標…
XOR について完全理解することが求められる...！ 問題へのリンク 問題概要 を偶数とする。 個の 0 以上の整数 であって、以下の条件を満たすものを求めよ。 個の整数のうち 番目を除外した 個の整数の XOR 和が となる 制約 考えたこと が偶数というのが不気…
考え方自体は典型的ではある 問題へのリンク 問題概要 個の整数 が与えられる。 これらから 2 個選んで XOR をとって得られる整数 ( 個ある) の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと XOR をみたら、とにかく「各桁ごとに考える」とい…
最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…
これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…
誤読したーーーーーー操作は 1 回しか行えないものと思って悩んでた 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を好きな回数だけ行うことで、 と とが一致する状態にすることが可能かどうかを判定せよ。 1 以上 以下の整数 を定める …
こういうの大好き！ 問題へのリンク 問題概要 の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ S の黒マスはすべて縦横に連結である T の黒マスはすべて縦横に連結である …
答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！ 受験数学では定番のテクニックだ！！！ 問題へのリンク 問題概要 長さ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、 隣接する要素の差を書き出す という操作を、…
シンプルで楽しい感じ 問題へのリンク 問題概要 要素からなる数列 がある (互いに相異なる)。交互に以下の操作を行う 数列から 2 つの整数を選んで、その差を数列の末尾に追加する ただし、「その差の値」がすでに数列中に含まれる場合は、この操作を行うこ…
インタラクティブ...でも問題自体は「単調性が成り立たなくても二分探索できるよ！」という教育的なものだった！ 問題へのリンク 問題概要 円形状に並んだ 個の椅子がある ( は奇数)。各椅子は 男性がいる 女性がいる 空席 のいずれかである。どの隣り合う 2…
先頭と末尾の両方から push できるデータ構造といえば、deque！！！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個の操作を行ってできる文字列を出力せよ type 1： 文字列 を左右反転する type 2： 値 F と文字 c が与えられ、F = 1 のと…
微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか？ ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…
まさか残り 25 分で通し切れるとは思わなかった！ 問題へのリンク 問題概要 長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ 各クエリは left, right, len からなる 部分文字列 A = S[left : left + len], B = S[right: rig…
遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…
面白かった 問題へのリンク 問題概要 の盤面の各マスを 0 か 1 かで埋めたい。すでに 個のマスについては数字が埋まっている。以下の条件を満たすように残り マスを埋める方法は何通りあるか、998244353 で割ったあまりで求めよ。 一辺の長さが 2 以上な部分…
Union-Find を使いこなす！！！ 問題へのリンク 問題概要 (意訳) 個の 0-1 変数 が与えられていて、最初はそれらの値について特に制約はない。いま、 個の制約が順に与えられる。各制約はそれぞれ 1 つの変数 と 0 か 1 の値 w を指定して、 とする 2 つの変…
半分エスパー 問題へのリンク 問題概要 列目の高さが であるようなヤング図形が与えられる。 これを 1 × 2 のドミノを重ならないように敷き詰めたい。最大で何個置けるか？ 制約 考えたこと ドミノ敷き詰め系の問題は、市松模様に塗るのが基本ではある。そし…
実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…
隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」…
200 点となってるけど、他の 300 点と同じくらいに感じた！ 頭の整理が大変だった...けど、面白い 問題へのリンク 問題概要 個の根付き木が与えられる。それぞれの木の頂点数は となっている。これらの木を使って、ゲームを行う。 最初、駒がスタート地点 (…
区間反転操作問題シリーズ！！！ それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …
