けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

差分更新

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

AtCoder ABC 338 G - evall (橙色, 600 点)

人目見て「頑張れば解けそう」と思えたので、コンテスト中になんとか頑張って通した! 問題へのリンク 問題概要 "1+2*34" のような文字列が与えられる。 この文字列の連続する部分文字列をすべて考えて 数式として成立しているなら、その数式を計算した値 数…

JOIG 2023 E - 運河 (難易度 7)

UnionFind を使って、差分更新を頑張る! UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います! 問題へのリンク 問題概要 のグリッドがあって…

JOIG 2023 D - コイン集め 2 (難易度 6)

データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

AtCoder ABC 329 D - Election Quick Report (灰色, 350 点)

「差分更新」の良い練習問題! 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…

AtCoder ABC 322 C - Festival (灰色, 300 点)

for 文を回していくときに「前回の値を活用する」というテクが登場する問題。このテクは、後に「累積和」や「DP」を学ぶ際の大切な基礎となる。 問題へのリンク 問題概要 日間のうち、 日目には花火が上がる。 各日について、何日後に最初の花火が上がるかを…

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…

AtCoder ABC 250 F - One Fourth (黄色, 600 点)

くしらっちょ君と一緒に解いた! 実装が辛い。 問題へのリンク 問題概要 頂点数が である凸多角形が与えられる。この凸多角形の面積を とする。 今、凸多角形の隣接しない 2 頂点を結ぶ直線によって凸多角形を 2 つの多角形に分ける。そして、2 つの多角形う…

AtCoder ABC 302 E - Isolation (緑色, 425 点)

「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …

AtCoder ABC 278 D - All Assign Point Add (茶色, 400 点)

データの持ち方をうまく工夫することで、計算量を改善する系の問題! 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x:数列 をすべて に書き換える i x: に を足す i…

AtCoder ABC 281 E - Least Elements (水色, 500 点)

よくあるデータ構造問題!! めっちゃ色んな解法がある! 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

AtCoder ABC 280 G - Do Use Hexagon Grid 2 (赤色, 600 点)

ハニカムにそんな性質があるなんて!!! 45 度回転する技術のアナロジーが炸裂する。 あと、x 座標が最小となる点で場合分けする際に、同一の x 座標を持つものに対してダブルカウントを除去する工夫が大変だった。 問題へのリンク 問題概要 2 次元平面上に…

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…

AtCoder ABC 213 F - Common Prefixes (黄色, 500 点)

これを機会に SA-IS を整備した! 今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。 問題へのリンク 問題概要 2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。 長さ の文字列 が与えられます。 の 文字…

AtCoder ABC 186 F - Rook on Grid (青色, 600 点)

「横移動 + 縦移動」で行けるところをすべて求めるのは簡単だし、「縦移動 + 横移動」で行けるところをすべて求めるのも簡単。しかし、両方の方法で行けるマスの扱いが難しい。 問題へのリンク 問題概要 のグリッドがあり、そのうちの 個のマスは壁になって…

JOI 本選 2014 A - JOI紋章 (AOJ 0598, 難易度 6)

ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…

JOI 本選 2016 B - スタンプラリー 2 (AOJ 0626, 難易度 6)

「3 つのものの真ん中に着目する」という典型が学べる。面白かった! 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…

JOI 本選 2017 A - フェーン現象 (AOJ 0636, 難易度 6)

差分だけ更新していく系の問題!!! 問題へのリンク editorial 類題集 (めちゃむずいのもある) drken1215.hatenablog.com 問題概要 正の整数 が与えられる。長さ の数列 のスコアが次のように定まる。 各 に対して以下の値を合算する のとき: のとき: を…

AtCoder ABC 170 E - Smart Infants (水色, 500 点)

こういうの苦手すぎるので、素早く綺麗に実装できるようになりたい 問題へのリンク 問題概要 AtCoder に参加している幼児が 人おり、 から の番号が付けられている。また、幼稚園 がある。幼児 のレートは であり、はじめ幼稚園 に所属している。 これから …

AtCoder AGC 049 B - Flip Digits (緑色, 600 点)

簡単なバグを埋め込んでしまった... 問題へのリンク 問題概要 長さ の "0" と "1" のみからなる 2 つの文字列 が与えられる。 に対して以下の操作を繰り返し行うことで に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。 中の "01" …

AtCoder AGC 040 C - Neither AB nor BA (橙色, 800 点)

これまた楽しい数え上げ!!! 解説があまりにも天才だけど、解説の方法が思いつかなくても一応できた!!! 問題へのリンク editorial 解説放送 問題概要 "A", "B", "C" のみからなる長さ の文字列であって、以下の条件を満たすものの個数を 998244353 で割…

AtCoder ABC 181 E - Transformable Teacher (緑色, 500 点)

頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…

AISing Programming Contest 2020 D - Anything Goes to Zero (水色, 400 点)

結構難しい!! 問題へのリンク 問題概要 正の整数 に対して、 := を二進法表現したときの各桁の総和を として を で割ったあまり := を で置き換える操作を繰り返したときに、何回で 0 になるか として定める。たとえば のとき、, より、 となる。 今、二進…

CPSCO2019 Session3 E - Enumerate Xor Sum (500 点設定)

これ、てんぷら君のおかげで随分とシンプルな問題になった! 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。各 に対して、 xor xor xor としたときの xor xor xor の値を求めよ。 制約 解法 XOR に関する問題は各桁ごとに考えるのは常套手段では…

HHKB プログラミングコンテスト 2020 C - Neq Min (灰色, 300 点)

mex!!!それにしても、ならし計算量解析系が来たのびっくり! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 に対して、0 以上の整数で のいずれとも等しくない値のうち最小値を求めよ。 制約 考えたこと とりあえず次のような配列を用意したく…

HHKB プログラミングコンテスト 2020 F - Random Max (橙色, 600 点)

時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…

AtCoder ABC 177 C - Sum of product of pairs (灰色, 300 点)

茶色 diff にはなると思ったけど、灰色 diff だった...「/2」が必要と感じて詰まる人も多いと思ったのに... 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての に対しての の総和を 1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AtCoder ABC 176 C - Step (灰色, 300 点)

Greedy の一番簡単なパターン 問題へのリンク 問題概要 人が 1 列に並んでおり、前から 番目の人の身長は です。 それぞれの人の足元に、高さが 0 以上の踏み台を設置し、全ての人が次の条件を満たすようにしたいです。 条件:踏み台を込めて身長を比較した…

AtCoder ARC 104 D - Multiset Mean (黄色, 700 点)

すごく NTT したくなる 問題へのリンク 問題概要 正の整数 が与えられる。 をそれぞれ 個以上 個以下とってくる方法のうち、平均が となるものの個数を素数 で割ったあまりを、各 に対して求めよ。 制約 考えたこと まず、平均制約を次のように言い換える。…