グルーピングの最適化
面白かった！ 問題へのリンク 問題概要 個の正の整数 を 個のグループに分ける。ただし、どのグループの要素数も 1 個以上 2 個以下でなければならない。 最適なグループ分けをしたときの、各グループの要素の総和の二乗の総和の最小値を求めよ。 制約 考え…
企業合コンで解いた。ギャグ系だった。 問題へのリンク 問題概要 円周上に 個の点があって、2 個ずつ 組のペアを作って線分で結ぶ。 すでに 組のペアができていて、線分が結ばれている。残りの点についてペアを作って線分を作っていったときの交差数の個数の…
な bit DP としてよく知られている問題ですね！ 問題へのリンク EDPC U - Grouping の類題と言える！ atcoder.jp 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。頂点集合を、いくつかの頂点部分集合に分割したい。ただし、分割してできる各部分グラ…
DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…
半分エスパー 問題へのリンク 問題概要 列目の高さが であるようなヤング図形が与えられる。 これを 1 × 2 のドミノを重ならないように敷き詰めたい。最大で何個置けるか？ 制約 考えたこと ドミノ敷き詰め系の問題は、市松模様に塗るのが基本ではある。そし…
ペアリング系の問題 問題へのリンク 問題概要 以下の問題が 問出題されるのでそれぞれ答えよ: コーダーが 人、数学に強い人が 人、なんでもない人が 人いる ここからコーダー 1 人以上、数学強い人が 1 人以上を含む 3 人チームを最大何組できるか求めよ 考…
面白かった！ 問題へのリンク 問題概要 組の 2 整数 () があたえられる。 を満たす。この 組の 通りの順序すべてを考えたときの以下のように定義される「悲しみ」の最小値を求めよ。 「これまでに登場した整数」を表す集合を とする 各 i について、 がとも…
誤読して大きく出遅れた... 問題へのリンク 問題概要 個の整数 があたえられる。これを何個かのグループに分けて、各グループについて「グループ内のすべての整数がグループ内の最小値で割り切れる」という条件を満たすようにしたい。 これを実現するための…
ペアリングを場合分けしてルールベースで頑張る系の問題、過去に何度もやらかしていて苦手意識が強い 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを任意の順序で連結してできる 通りの文字列のうち、その中に "AB" を連続部分列として含んで…
たったこれだけの問題でも、学ぶべきことがすごくあるイメージ！！！ 問題へのリンク 問題概要 2 つのボタンがあってそれぞれ大きさが である。 大きさ のボタンを押すとコインが 円もらえて、ボタンの大きさが 1 減って になる。 2 回だけ好きなボタンを押…
これほとんど drken1215.hatenablog.com と同じ問題！！！ 問題へのリンク 問題概要 を整数として 個の整数 が与えられる。これらを 3 個ずつ 組のペアを作る。 ペアリングのスコアは、各ペアにおいて 2 番目に大きい値の総和で決まる。ペアリングのスコアを…
伝説の始まり 問題へのリンク 問題概要 個の整数 が与えられる。 これらを 個ずつ 組作り、各組についての「小さい方の値」の総和を最大にしたい。 制約 考えたこと 小さすぎる値と大きすぎる値とを組合せてしまうと、大きい値が小さい値に吸収されてしまっ…
一見 な bitDP だけど、これはアレだ！！！ よくある にできるやつだ！！！！！ 問題へのリンク 問題概要 個の数 がある。これを最小個数のグループに分けて、各グループの合計値が 以下となるようにせよ。 制約 解法 とりあえず一見 な bitDP に見える。AGC…
