グルーピング(算数)
長さが大きい順に処理していこう！ 問題へのリンク 問題概要 長さが の棒がある。 これらの棒を 4 個選んで長方形を作りたい。作れる長方形の面積の最大値を求めよ。長方形を作れない場合は 0 と答えよ。 制約 考えたこと できるだけ大きい長さの棒を使いた…
これ系の問題、最近あまり見かけなくなった気がする。 問題へのリンク 問題概要 個の正の整数からなる数列 が与えられる。 この数列の項を適切に並び替えることによって、「どの隣接する 2 項の積も 4 の倍数」となるようにできるかどうかを判定せよ。 制約 …
場合分けを頑張ろう！ 問題へのリンク 問題概要 3 つの整数 をいくつかのグループに分けて、各グループに含まれる整数の総和を等しくできるかを判定せよ。 考えたこと 次の 2 つの場合が考えられる。 2 つのグループに分けて、総和を等しくする 3 つのグルー…
この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …
この切り上げ処理はぜひ憶えておこう！ 問題へのリンク 問題概要 高橋君は、全 ページから成る書類を両面印刷する。両面印刷では、1 枚の紙に 2 ページ分のデータを印刷することができる。 最小で何枚の紙が必要か求めよ。 解法 が偶数のときは、 は 2 で割…
ちょっと整理が難しい文章題。 問題へのリンク 問題概要 りんごが 個、りんごの欠片が 個ある。 1 個のりんごを砕くと、りんごの欠片が 個できる 2 個のりんごの欠片を使うと、アップルパイが 1 個できる 今ある材料から、最大で何個のアップルパイが作れる…
3 人一組になる問題 問題へのリンク 問題概要 人がいる。 人が 1 グループになることができる。作れるグループの個数は最大何個か？ 解法 を で割った商が答えとなる。その余りの人数だけ余ることになる。 #include <bits/stdc++.h> using namespace std; int main() { int </bits/stdc++.h>…
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
僕はめっちゃめんどい言い換えをして、めっちゃめんどい場合分けして無理矢理通した... 問題へのリンク 問題概要 二次元平面上の点 (0,0),(1,0),(0,1) に石がひとつずつ置かれています。 3 つの石が次の条件を満たしているとき、くの字に並んでいるといいま…
こういう個数合わせ系の問題は実は得意かもしれない 問題へのリンク 問題概要 長さ の数列 が与えられる。これに対して の順列 であって、 のどの隣接する二項も同じ数値でないようなものを考える。 そのような順列 のうち、 を満たさない の個数の最小値を…
本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…
これ灰色ってマジか！！ 問題へのリンク 問題概要 どの桁の値も 0 でないような正の整数 が与えられる。 に含まれるいくつかの数値を除去することで、 が 3 の倍数となるようにしたい。 除去すべき数値の個数の最小値を求めよ (最初から 3 の倍数の場合は 0 …
区間分割して考える系、AGC-A にめちゃくちゃ多いね 問題へのリンク 問題概要 文字列 が与えられる。 を 回繰り返してできる文字列を とする。 の文字をひとつ選んで他の文字に書き換える操作を繰り返すことで T のどの隣り合う 2 文字も相異なるようにする…
場合分けやコーナーケース回避がエグい問題！ 問題へのリンク 問題概要 .#..#.. のような長さ のマス目が与えられる。"#" は岩を表す。初期状態では、すぬけ君は マス目に、ふぬけ君は マス目にいる ()。 今、「2 人のうちのいずれかを選んで 1 マス右か 2 …
本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…
面白かった 問題へのリンク 問題概要 という 個の整数がある。これらを 2 個以上のグループに分ける。各グループの整数の総和が互いに等しくなるようにグループ分けすることが可能かどうかを判定し、可能ならば具体例を構築せよ。 制約 考えたこと こういう…
これかなりいい問題だと思う！！！ テスターをしていて、最初は 3 人じゃなくて 人だったけど、3 人にしたことでいい感じに 300 点問題になった！ 問題へのリンク 問題概要 人がいて、それぞれレーティングは となっている。 人の中から 3 人を選ぶ方法のう…
これすごく好き！！！普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
Union-Find の典型的な問題！！ でも、DFS や BFS でも解くことができる。 問題へのリンク 問題概要 人 から 人 までの 人の人がいます。 「人 と人 は友達である」という情報が 個与えられます。同じ情報が複数回与えられることもあります。 と が友達、か…
二乗の木 DP を応用したもの。このセットの運営チームだった。 問題へのリンク editorial 北大アーカイブ 問題概要 頂点からなる木が与えられる。 この木の 個の空でない部分グラフの組であって、各部分グラフがいずれも連結で、どの二つの相異なる部分グラ…
めちゃ好きだけど、実装重い 問題へのリンク 問題概要 頂点の重み付き無向完全グラフが与えられる。各 に対して、 頂点集合を 個の互いに disjoint な集合に分割する方法であって どの同族辺 (両端点が同一のグループに属する辺) の重みも、どの異族辺 (両端…
こういうのは包除原理しかない！ 問題へのリンク 問題概要 人の人がいる。 人 の身長は である。以下の条件を満たすように、 組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。 どの人もちょうど一つのペアに含まれる。 どのペアも、…
DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…
微妙なコーナーケースに注意 問題へのリンク 問題概要 の書かれたカードがそれぞれ 枚ある。以下の条件を満たすようにペアリングしていくとき、最大で何組できるか？ ペアとなるカードの数値の差は 1 以下 制約 考えたこと 一瞬、 値が等しいペアを作れるだ…
半分エスパー 問題へのリンク 問題概要 列目の高さが であるようなヤング図形が与えられる。 これを 1 × 2 のドミノを重ならないように敷き詰めたい。最大で何個置けるか？ 制約 考えたこと ドミノ敷き詰め系の問題は、市松模様に塗るのが基本ではある。そし…
バチャでは手が回らなかったけど、復習した。ちょっとこの多項式解法は今はよくわからないけど、覚えておこう... 問題へのリンク 問題概要 要素の数列 が与えられる。 の順列 に対して、それを巡回群の直積として表したときの、各巡回群に含まれる要素に対応…
伝説の良難問。 現在でこそ AC 数 30 人で解説記事も豊富にあるが、当時は AC 数 3 人という状況で解説も無い中で、必死に 1 週間かけて通した想い出の問題。 問題へのリンク 問題概要 正の整数 と 以上の整数 が与えられる。 {} から {} への写像 の組であ…
ペアリング系の問題 問題へのリンク 問題概要 以下の問題が 問出題されるのでそれぞれ答えよ: コーダーが 人、数学に強い人が 人、なんでもない人が 人いる ここからコーダー 1 人以上、数学強い人が 1 人以上を含む 3 人チームを最大何組できるか求めよ 考…
面白かった！ 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…
