ずっと前にこれを作問して出題していたので記録を。 時は流れて AGC 026 D - Histogram Coloring でよく似た設定の問題が出たときはビックリした (実際はそんなに似てない)。 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '0', '1', '?' のい…
本当にただ全探索するだけ！！！ でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…
5 + 7 + 5 = 17 なの、よくできてる！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の数値からなる長さ の数列 であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 整数 が存在して、 の区間 の総和が の区間 の…
記念すべき新体制 AtCoder になってからの初の rated ABC の C 問題！！！ 問題のリンク 問題概要 以上の整数のうち、 種類の数値 のいずれも含まない最小のものを求めよ。 制約 考えたこと 真っ先に思い浮かぶ方法は、単純に と順々に試していって「 をいず…
これかなりいい問題だと思う！！！ テスターをしていて、最初は 3 人じゃなくて 人だったけど、3 人にしたことでいい感じに 300 点問題になった！ 問題へのリンク 問題概要 人がいて、それぞれレーティングは となっている。 人の中から 3 人を選ぶ方法のう…
一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…
これすごく好き！！！普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…
テスターしてました！難しかった。 問題へのリンク 問題概要 ラスク君は木を持っていましたが、なくしてしまいました。 この木は、頂点に 1 以上頂点数以下の相異なる整数の番号がついていて、各辺には 以上 以下の整数の重みが定まっていました。 頂点数は …
桁 DP 苦手すぎる... 問題へのリンク 問題概要 整数 が与えられる。整数の組 であって、 xor = を満たすものの個数を求めよ。 (というテストケースが 個与えられる) 制約 考えたこと とりあえず、 xor = という条件は 「 と を二進法表現したときに、ともに …
最初は文字列 を文字列 にできるかを問うつもりだった。てんぷら君のおかげで、 を真っ白にすることで、シンプルな問題になった！ 問題へのリンク 問題概要 マスがあって最初はすべて白く塗られている。ここに "RGB" のスタンプを押していく。スタンプを押す…
これ、てんぷら君のおかげで随分とシンプルな問題になった！ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…
資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…
このセットの writer をしていました 問題へのリンク 問題概要 を並び替えてできる数列 は 通りあるが、そのうち以下の条件を満たすものが何通りあるかを、1000000007 で割ったあまりを求めよ。 を満たすような がちょうど 個 を満たすような がちょうど 個 …
これが生まれて初めての作問だった！！！ AOJ-ICPC で ☆4 個ついてて嬉しい！ 問題へのリンク editorial 問題概要 虫食算が与えられる。解の個数を 1000000007 で割ったあまりを求めたい。 より正確には長さ の 3 個の文字列 が与えられる。これらは '?' か …
高速ゼータ変換を思いつくのに時間かかった 問題へのリンク editorial 問題概要 あなたは 人の従業員を持つ店の店長です。 番目の従業員は今日から「 日連続で働いた後 日連続で休む」ことを繰り返します。 あなたは今日から毎日出勤し、その日に出勤してい…
コンテスト本番、こっちをやればよかった...ところで解説が天才すぎる！ 問題へのリンク editorial 問題概要 個の部品と、 個の接続用部品とがある。これらを用いてフィギュアを作ろうとしている。 番目の部品には 個の穴がついている。接続用部品は、2 個の…
ARC 106 F に関連して、頂点次数制約のついた全域木の個数を求める問題がまさにあったので、その解説を。 問題へのリンク editorial 問題概要 (New Year Contest 2015 E - ひも) 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものが…
(x - a)(x - b) ... (x - z) みたいなやつの計算 問題へのリンク 問題概要 個の箱がある。箱 には色 のボールが入っている。以下の 個のクエリに答えよ。 各クエリは 以下の整数 が与えられる 各箱から 個ずつボールを取り出す方法であって、取り出されたボ…
形式的冪級数すごい 問題へのリンク 問題概要 個の整数 が与えられる。各 に対して を 998244353 で割ったあまりを求めよ。 制約 考えたこと いっそ 次までではなく、無限級数にしてしまう。そして として、 の各次数の係数を求めたい。ここで、 と計算でき…
問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。各頂点 には値 が書かれている。以下の操作を好きな順序で好きな回数だけ行うことで、各頂点 の数値が であるような状態にすることが可能かどうかを判定せよ。 辺 を選んで、以下のいずれ…
面白かった 問題へのリンク 問題概要 以下の条件を満たすような 個の区間 ( 番目を とする) を構築したい。 はすべて互いに相異なる整数 これらの区間の中から「どの 2 個も交差しないように最大で何個の区間を選べるか」という問題に対して、高橋君と青木君…
「要素を 1 個ずつ追加していくときに値がどう変化していくか」を観察する方向でずっと考えていて迷走してしまった... 問題へのリンク 問題概要 正の整数 と、 個の整数 が与えられる。 に対して、 の値を 998244353 で割ったあまりを求めよ。 制約 解法 個…
めちゃくちゃ面白かったし勉強になった！ 問題へのリンク editorial 問題概要 文字列 が与えられる。それとは別に 個の文字列 が与えられる。 文字列 をいくつかの連続する区間に分割する方法であって、各区間をなす部分文字列が のいずれかに一致するような…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
多倍長整数を活用した、重み付き二部マッチング 問題へのリンク editorial 問題概要 のグリッドが与えられる。各マスにはアルファベット (英大文字と英小文字) が描かれている。今、次の条件を満たすように 個の文字を抜き出す 各行から選ぶマスはちょうど 1…
LCA ライブラリを持っていれば書くだけ！ 問題へのリンク editorial 問題概要 頂点の根付き木が与えられる (根は頂点 0)。この木上で幅優先探索を行う (隣接する頂点のうち、頂点番号が小さい順にキューに push する)。 このとき、探索順序が であったとした…
頭整理するのが大変だった 問題へのリンク editorial 問題概要 個の格子点 (、、) がある。 これらの格子点を以下のルールに則って 色 () で塗る。 点 の、 とのマンハッタン距離が であるとき 点 を、色 % で塗る 各 について、その色で塗られた格子点が何…
素直に考えるとグラフの辺数が のオーダーになってしまうので、いかに削減するかを考える問題だった 問題へのリンク editorials 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。各頂点 には値 が振られている。今、各頂点にスコア を割り振りたい。…
英文だし、題意をちゃんと読み解くのがちょっと大変 問題へのリンク editorial 問題概要 L と R のみから構成された文字列 が与えられる。ロボットは最初北方向を向いている。文字列 を左から順番に読んで次のように処理していく。 L のとき、ロボットは 90 …
この手の、単純だけど for 文ネストがエグい全探索、案外 AtCoder で見ないかもしれない 問題へのリンク 問題概要 の二次元グリッドが与えられる。各グリッドには 0 以上 9 以下の整数値が書かれている。 グリッド上で、以下の条件を満たす長方形領域を考え…
