AGC-C
11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…
想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは，次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…
面白かった！！ 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます． の連続する 文字を選んで，それらをすべて 0 にす…
この回の前の回の LCMs といい、約数系包除がこの時期流行ってたのかな。 問題へのリンク 問題概要 整数 が与えられる。 以上 以下のすべての整数 に対し、 に以下の操作を繰り返すことによって次に に戻るまでの操作回数 (戻らない場合 0) を足し合わせた値…
これまた楽しい数え上げ！！！ 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた！！！ 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
構築楽しかった 問題へのリンク editorial 問題概要 のグリッド上に のドミノを互いに重ならないように配置していく。 どの行・列を見ても、その行・列上にある のドミノの個数が互いに等しいような配置を求めよ。存在しない場合は "-1" を出力せよ。 制約 …
こういう問題めっちゃ好き！！！ 問題へのリンク editorial 問題概要 '0' と '1' のみからなる長さ の文字列が与えられる。以下の操作を 回以上 回以下まで行うことができる。 i < j であって S[ i ] = '0'、S[ j ] = '1' であるような (i, j) を選ぶ S[ j ]…
面白かった！ 問題へのリンク 問題概要 頂点数が の木であって、各頂点 から最も遠い頂点への距離がそれぞれ であるような木が存在するかどうかを判定せよ。 制約 考えたこと 面白そう！！！！！！似た見た目の問題としては、次の問題もあった。 drken1215.h…
添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…
AGC っぽくない気がするけど、好き 問題へのリンク 問題概要 とする (素数である)。 個の非負整数 が与えられる。 の値を求めよ。 制約 考えたこと 「和を で割ったあまり」ではなく、「 で割ったあまりの和」であることに注意。それでも、とりあえず以下の…
こういうの大好き！ 問題へのリンク 問題概要 の盤面 A が与えられる。各マスは白か黒かのいずれかである。次の条件を満たす、同じ大きさの白黒の二つの盤面の組 (S, T) を構築せよ S の黒マスはすべて縦横に連結である T の黒マスはすべて縦横に連結である …
これはマジで天才やと思うやが... いや本当にどこから Grundy 数を導けるのか、わからぬ... 問題へのリンク 問題概要 頂点数 のグラフが 3 つ与えられる。それらのグラフのカルテシアン積を考える。この頂点数 のカルテシアングラフの独立集合のうち、以下の…
操作を 回行った結果を求める系、苦手意識あるけど克服したい！ 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…
ペアリングを頑張る問題として高難易度なすごく楽しい問題。 結構注意力がいる。割とやばいケースがある。 問題へのリンク 問題概要 下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れ…
気づけばすぐな感じかな 問題へのリンク 問題概要 本のロープがあってそれぞれの長さは で与えられる。最初、ロープ の右端とロープ の左端が結ばれている。今、 長さが 以上のひとつながりのロープを選び、その中に結び目があればどれか 1 つ選んでほどく …
楽しかった 問題へのリンク 問題概要 長さ の数列 が与えられる。どの 2 要素も互いに相異なることが保証される。これに対し 隣り合う 2 要素を swap する 連続する 3 要素を反転する という操作を行ってソートしたい。ただし、1 の使用回数を最小にしたい。…
これ大好き！！！ 問題へのリンク 問題概要 頂点のツリーが与えられる。 初期状態ではすべての頂点に 1 枚ずつコインが乗っている。先手と後手が交互に コインが 1 枚以上乗っている頂点を 1 つ選び、その頂点のコインを取り除き その頂点以外の全頂点につい…
コンテスト中に真剣に考えて解けなかった 700 点問題！！！ 問題へのリンク 問題概要 個の整数 があたえられる。 個の整数の部分和は空集合に対応するものを除くと 個ある。 このうちの中央値を求めよ。 制約 考えたこと とりあえず部分和問題みたいなことを…
見るからにコーナーケースが怖い... atcoder.jp 問題概要 頂点 本の辺からなる単純かつ連結な無向グラフが与えられます。 全ての辺をちょうど一回ずつ使って つのサーキットを作ることが可能かどうかを判定してください。 制約 考えたこと 輪っかを 3 つ作る…
証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…
ツリーの問題！！！！！！！！ 見るからにツリー DP っぽいのだけど、なかなかに頭が混乱する感じ。 この問題の心得は「最適解はどんな形をしているんだろう」を考えることかなと思う。それによって「こういうものだけ探索すれば良い」というのが見えて来る…
弱かった。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 文字列の列 であって の文字数が である 辞書式順序で < < < を満たすもののうち、登場文字数の最小値を求めよ。 制約 考えたこと が狭義単調増加だったら、"a" の個数だけで行けるので…
蟻さんぐるぐるなのん 問題へのリンク 問題概要 (AGC 013 C) 長さ の円周上を 匹の蟻が動く。どの蟻も 1 秒間に 1 だけ動く。互いに反対方向に動いている 2 匹の蟻がぶつかったら、互いに向きを反転させて動く。 匹の蟻は最初 の地点にいた。どの蟻が最初に…
なんかこれは TL で「 という制約が意味するものは...！？」という感じの TL を先に見てしまった。。。 とはいえ確かに半分全列挙一択ではあるか... 問題へのリンク 問題概要 (AGC 026 C) 長さ の、英小文字のみからなる文字列 が与えられる。 の各文字を赤…
コンテスト本番における 僕のコード: https://beta.atcoder.jp/contests/agc025/submissions/2612210 tourist のコード: https://beta.atcoder.jp/contests/agc025/submissions/2609185 解けたとはいえ、反省点も多い感じですね。。。 問題へのリンク 問題概…
