問題概要 個の商品があり, 各商品の値段は基本 円である. 長さ の数列 が与えられ, これは 番目の商品を 個だけ購入する必要があることを示している. 上記とは別に, 個のセール情報 が与えられる. 番目のセール情報は, 日目に 番目の商品が 円で購入できるこ…

問題概要 長さ の数列 が与えられる. この中から任意の個数の数を取り出し, 自由に並び変えたうえで円環状に配置する. このとき, 隣り合う数の絶対値の差が 以下になるようにしたい. このような並べ方のうち, 最大のものは何か？ 問題へのリンク 制約 解法 …

問題概要 頂点の木が与えられ, この木の辺を様々な色で塗っていきたい. ある頂点について同じ色で塗られている頂点があるとき, その頂点は悪い頂点である. 悪い頂点を 個以下にするには, 最低で何色必要か？（構築せよ. ） 問題へのリンク 制約 解法 まず, …

問題概要 二種類の文字列 について, 辞書順でちょうど の真ん中な文字列を求めよ. 問題へのリンク 制約 と の間にある文字列は奇数個 解法 文字列を 進数の数とみれば, を出力するだけです. ただし, 桁の数を扱うのは無理があるので, 上手に計算する必要があ…

問題概要 の行列が与えられる. この行列について, 行を自由に入れ替える. この結果できた行列を としたとき, 数列 を として定める. このとき, ある に対して, 全ての について が成り立つとき, は良い数列であるという. 与えられた行列に対し, 良い数列が存…

問題概要 頂点のグラフ が与えられる. 番目の頂点には数字 が割り当てられており, 最初は辺が張られていない. このとき, に対して辺を張ることによって, 全域木を作成したい. このとき, 頂点 と 頂点 を結ぶのにはコスト がかかる. ただし, 個の辺があたえら…

問題概要 の赤い正方形が 個, 青い正方形が 個与えられる. 個の正方形を敷き詰めることにより長方形を作るが, このとき少なくとも赤か青の一方の正方形だけでも長方形が完成されているようにしたい. このような敷き詰め方のうち, 周の長さが最小値はいくらか…

問題概要 長さ の数列があり, 番目の要素は である. この数字を 人に 個ずつ配る. 番目の人は数字 を好んでおり, 配られた数字の中の の個数が ならば幸福度 を得る. 自由に数列を配れるとき, 全体の幸福度の最大値はいくらか？ 問題へのリンク 制約 解法 数…

問題概要 頂点数 の有効グラフが与えられる. 頂点 からすべての頂点に到達可能にするには最小であと何本有向辺を追加すればよいか？ 問題へのリンク 制約 解法 強連結成分分解をしたうえでトポロジカルソートをすれば, どの頂点に優先して辺を張ればいいかが…

問題概要 頂点の木が与えられる. 頂点 には値 が割り当てられている. 頂点 に対し関数 を と定義する. を自由に選べるとき, の最大値はいくらか？ 問題へのリンク 制約 解法 典型的な全方位木dpの問題です. 全方位木dpがわからない方はまずググってください.…

問題概要 長さ の整数列 が与えられる. この中からちょうど 個の整数を選択するが, その時少なくとも連続する 個の中の一つが選ばれてなければならない. この時, 選んだ整数の合計の最大値はいくらか. 問題へのリンク 制約 解法 dp をしましょう. ( 個の整数…

問題概要 長さ の数列 が与えられる. この中から総和が等しい区間を複数選ぶとき, 最大でいくつ選べるか？(構築せよ. ) ただし区間同士が重なってはならないものとする. 問題へのリンク 制約 解説 数列の長さが短いので, 区間の数が比較的少なく, 区間和とし…

問題概要 '(' と ')' で構成された長さ の文字列 が与えられる. この文字列のちょうど一文字を変更することで, が正しい括弧列になるような index は何個あるか？ https://codeforces.com/contest/1095/problem/E 制約 解法 正しい括弧列の判定方法は stack …

問題概要 数字 と の連結を, 文字列として と を連結したときにできる数とする. たとえば と の連結は である. 長さ の数列 と が与えられる. このうち, と ( ) の連結が で割り切れるような順序付きペア の個数を求めよ. 問題へのリンク 制約 解法 と の連…

問題概要 書くのだるいので, サイトの文章を読んでください.... 問題へのリンク 制約 解法 こういうのと全く一緒です. まず, 星の数は最小化する必要がなく, また重なってもいいということから, 作れる星は全部作ってしまうのがよいです(作れるのに作らない…

問題概要 数直線上の 個の点 が与えられる. この中から適当な個数の点を選び, 選んだ点を としたとき任意のペアについて が の累乗になるようにしたい. このとき, 最大何個の点を選ぶことができるか？構成とともに示せ. 制約 解法 明らかに 点のみを選ぶこと…

問題概要 から の数直線上の整数の点どうしを移動し, ちょうど 回の移動で総移動距離を にしたい. これは可能か？可能なら構成例を示せ. ただし, 一回の移動では必ず 以上移動しなければならない. 問題へのリンク 制約 解説 こういう問題が好きな人, この世…

問題概要 個の区間が与えられる. この中から一つの区間を取り除くことができるとき, 残された区間の共通部分の長さの最大値はいくらか. 問題へのリンク 制約 解法 個から一個除いた時の解は？という問題で, もし累積的に計算可能な構造をしている場合, 左右…

問題概要 大きさ の箱が 個あり, これに 個の荷物を詰め込んでいく. 番目の荷物の大きさは である. 箱詰めは以下のアルゴリズムにより進行する. まず, 空箱を手に取る 残っている荷物の中で番号が最も小さい荷物を箱に入れようと試みる. もし箱の残り容量が…

問題概要 あるトピックについて出題される問題が 個ある. 番目の問題はトピック について述べている. これらの問題をまとめて, 数日にわたるコンテストを開く. コンテストに出題する問題の制約は以下である : それぞれの日程について, その日一日に出題され…

問題概要 長さ の数列 と非負整数 が与えられる. に対して, 長さ の数列 の Cutting Out を以下のように定める : の各要素を一回ずつ から削除する. もし 削除できない要素がひとつでもある場合, Cutting Out はできない. の要素は重複することができるため,…

問題概要 人が円になって並んでおり, 人 について つ先の人, 及び つ先の人は である. なお, は順番が逆のこともある( が二つ先の人を表していることもある). もとの順番 を復元せよ. 問題へのリンク 制約 解は必ず一つ以上存在する. 解説 最初を人 としまし…

問題概要 長さ の数列 に対し, 長さ の数列が以下の条件を満たすとき は Monotonic Renumeration であるという : である に対して ならば が成り立つ(逆, つまり ならば は成り立たなくてもよい). 任意の に対して もしくは が成り立つ. 与えられた に対して…

問題概要 杯のコーヒーがあり, 番目のコーヒーは だけのカフェインを含有している. このコーヒーを飲むことで, 個ののタスクをこなしたい. ある一日で 番目のコーヒーを飲んだとすると, だけのタスクをこなすことができる. このとき, 最小で何日ですべてのタ…

問題概要 頂点 辺の単純連結無向グラフが与えられる. ここから適当に辺を削除することでグラフを木にするが, このとき頂点 の次数がちょうど になるようにしたい. これは可能か？可能ならば構成例を示せ. 問題へのリンク 制約 解法 まず, 頂点 の次数が 未満…

問題概要 人が 人おり, 番目の人の能力は である. この中から 個以下のチームを作りたい. チーム作成の制約は各チーム内の任意のペアについてそのスキルの絶対値の差が 以下であることである.( 人のチームを作ることも可能である). 最大で何人をいずれかのチ…

問題概要 数字 と長さ の数列 が与えられる. 回目では となるとき, 初めて が 以下になるのは何回目か？(永遠に正の場合は を出力) 問題へのリンク 制約 解法 累積和における最小値を とします. もし なら, 普通にシミュレーションすればいいです. そうでは…

問題概要 無向単純連結グラフ が与えられます. の辺に向きをつけて を有向グラフにするが, このとき のすべてのパスの長さが になるようにしたいです. このように向きをつけることは可能ですか？可能なら構成の一例を示してください. 問題へのリンク 制約 解…

問題概要 人の人間が横一列に並んでおり, 番目の人間は能力値 を持つ. このとき, は長さ の順列になっている. この 人を, 以下に従って二つのチームに分ける. チーム番号 を として初期化する. の中で最大の能力を持つ人間を探し, その人間をチーム に分類す…

問題概要 長さ の数列 が与えられます. の各要素は 以上 以下です. 数列 を, として定めます. の各要素を自由に入れ替えて, が辞書順最小にしてください. 問題へのリンク 制約 解法 辞書順最小と言われれば, やっぱり貪欲法です. の小さい方から見ていくこと…