絶対値やminを扱う問題
いろんな解法がある！ 問題へのリンク 問題概要 以上 以下の整数のうち、 との差の絶対値が最も小さいものを求めよ。 制約 解法 (1)：for 文 一番確実な方法は、for 文を用いて、 をすべて調べることだと思われます。 が最小となるような を求めればよいでし…
の計算量までなら比較的すぐできる！ 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…
行列累乗した。デバッグに手こずった。 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を 回行う。 を選んで と を swap する 操作列は 通り考えられるが、それぞれについての の総和を 998244353 で割った余りを求めよ。 制約 考えたこと の期待…
頭を柔らかくして考えよう。 問題へのリンク 問題概要 3 個の整数 から 2 個選んで和をとる。 この和の最大値を求めよ。 解法 3 個の整数 から 2 個選んだ和は の 3 通りがある。これらの最大値を求めればよい。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…
3-point shot で逆転できるという条件を、上手に数式に落とし込もう！ 問題へのリンク 問題概要 バスケの試合で両チームの得点は 点である ( である)。 どちらかのチームに 3 点追加されたときに、逆転が起こるかどうかを判定せよ。 解法 のどちらが大きいか…
この問題は意味を理解するのが大変だと思う！ 問題へのリンク 問題概要 3 つの整数 が与えられる。これらを適切に並び替えたときの 1 番目と 2 番目の差 2 番目と 3 番目の差 の和として、考えられる最小値を求めよ。 解法 実際に幾つかのケースで手を動かし…
ちょっと整理するのが大変な問題。 問題へのリンク 問題概要 一直線上の座標 の点に、それぞれ A さん、B さん、C さんがいる。 2 人は、距離が 以内にいるとき、直接的に通信ができる。 A さんと C さんが、直接的に、あるいは間接的に、通信ができるかどう…
整数 の差は、絶対値記号を用いて と表せる。絶対値は、たとえば C++ では関数 abs() が使える！ 問題へのリンク 問題概要 座標軸上で、店 A, B がそれぞれ座標 にある。 今、すぬけ君は座標 の地点にいる。すぬけ君にとって、店 A, B のどちらに近いかを判…
すごく典型盛り合わせな教育的問題！ 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…
問題の理解がちょっと大変。数学の素養がないと厳しいかもしれない。 問題へのリンク 問題概要 正の整数 ( を満たす) が与えられる。 また、 個の整数 が与えられるので、各 について、次の条件を満たす整数 を求めよ。 である 以上 以下の任意の整数 に対し…
Wavelet Matrix の prev_value や next_value が使える問題！ 問題へのリンク 問題概要 サイズ の数列 が与えられる。次の 個のクエリに答えよ。 が与えられるので、数列の区間 の値のうち、 との差の最小値を答えよ。 制約 考えたこと Wavelet Matrix の関…
いわゆる「愚直シミュレーション」と呼ばれる分野の問題ですね。問題文で指示されたことを、とにかく愚直に忠実に実装できるかが問われています。地味な印象を受けるかもですが、大切なスキルです！ 問題へのリンク 問題概要 黒板に、はじめ 個の整数値 が書…
つい最近 CodeQUEEN 決勝 E 問題でも出てきた「最大値の最大化」典型テクニック！！！！ 問題へのリンク 問題概要 長さ の 2 つの数列 と が与えられる。今、互いに disjoint な区間群 をとる ( は自由)。ただし、区間の長さの総和がちょうど となるようにす…
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた！ 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…
次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…
シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 が与えられます。 に対して、住民 と他…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
EDPC C - Vacation と良く似た問題だと思う！！ あと、幅が狭いグリッドでは DP が疑われることが結構多い！ 問題へのリンク 問題概要 長さが の数列が 2 つ ( と ) 与えられます。 各 に対して、 と のいずれかを選ぶことで、新たに数列 を作ります。 こう…
自明な上界を達成できるパターンだった！ 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…
この問題、実は、北大合宿 HUPC の有志コン枠で原案として挙げていた問題とまったく同じだった！！！！！！ 問題へのリンク 問題概要 の順列 の奇妙さを と定義する。奇妙さが であるような順列の個数を 1000000007 で割ったあまりを求めよ。 制約 考えたこ…
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった！ 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …
本番は「どのように に分けても絶対値和は等しい」ということに気づかず、ものすごくエグい二項係数計算を頑張って綺麗な表式を得た。 問題へのリンク 問題概要 長さが の数列 が与えられる。 数列を 個ずつのペア (順序の違いは考慮する) に分ける方法は 通…
これ！！！！！HUPC 2019 day2 セットで出したやつや！！！ 問題へのリンク 問題概要 二次元平面上に 個の点 がある。 これらのうちの 2 点のマンハッタン距離として考えられる最大値を求めよ。 制約 考えたこと 2 点の位置関係としては、以下の 2 パターン…
資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った！ 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…
テスターだった。 簡単枠の Easy ヴァージョンに対して「制約あげられるね」と提案して、正式に問題セットになった！ 問題へのリンク editorial 問題概要 のグリッドがあって、各マスは '.' か 'B' から成っている。'B' マス間のマンハッタン距離として考え…
探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…
操作の仕方が Euclid の互除法そのものになっているタイプの問題。 問題へのリンク 問題概要 要素数 の数列 が与えられる。これに対して以下の操作を好きな回数だけ行うことができる: 整数を 2 つ選び、その差の絶対値をとり、それを数列に新たに挿入する 整…
答えが 0, 1, 2 の三通りしかないとなれば、mod で絞るのをやりたくなる！ 受験数学では定番のテクニックだ！！！ 問題へのリンク 問題概要 長さ の、1, 2, 3 のみからなる数列が与えられる。この数列に対して、 隣接する要素の差を書き出す という操作を、…
