最適化の考察：探索候補を絞る
にょぐた君と一緒に考察した。面白かった。公式解説は多面体で考えているけど、ここでは LP 双対で解いてみる。 問題へのリンク commentary 問題概要 種類の水溶液がある。水溶液 は、 として、 水溶液全体の重さが g 1 g あたりの溶質の重さが g 以上 g 以…
探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…
グリッドが幅広いが、黒色マスの周辺でしか「3 x 3 内部に黒色マスがある」という状況が発生しないことを活用する！ 問題へのリンク 問題概要 グリッドの各マスは白色または黒色である。 個のマスが黒色である（座標が与えられる）。 このグリッド内部の各 3…
「実は各点から左右に見て最も近い点だけ見れば良い」という点気考察をする！ 問題へのリンク 問題概要 数直線上に 個の絵がある。 番目の絵のある位置の座標は であり、'J', 'O', 'I', 'G' のいずれかの文字 が書かれている。 これらの絵に対して、以下の …
平行移動量の候補を絞る考え方を使う！ 問題へのリンク 問題概要 座標平面上に 個の星を表す点 が与えられる（星座を成している）。また、それとは別に座標平面上に 個の点 が与えられる。 点 を一斉にある量だけ平行移動すると、それらすべてが、上に述べた…
実は愚直に文字列 を作っても解ける！ 問題へのリンク 問題概要 文字列 を、"oxx" を 個連結した文字列とする。 与えられた文字列 が、 の部分文字列であるかどうかを判定せよ。 制約 考えたこと 一般に、文字列 が文字列 を部分文字列にもつかどうかは次の…
いろんな解法がある！ 問題へのリンク 問題概要 以上 以下の整数のうち、 との差の絶対値が最も小さいものを求めよ。 制約 解法 (1)：for 文 一番確実な方法は、for 文を用いて、 をすべて調べることだと思われます。 が最小となるような を求めればよいでし…
すごく面白い問題！ いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
めっちゃ面白い問題！！ 実はよく似た類題として次の問題がある！ atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
この見た目で「幾何」になるの、面白い！ 問題へのリンク 問題概要 高橋君は 種類の泳ぎ方ができる。 種類目の泳ぎ方では、1 秒間に体力を だけ消費して、 メートル進むことができる。このとき、次の 回のクエリに答えよ。 【クエリ】 正の実数 が与えられる…
この時代は Greedy が多かった。そして、実はすごく単純なことに気がつくかどうかが問われる問題！ 問題へのリンク 問題概要 数直線上 (東西方向) に 個の町があり、それぞれの町の座標は である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手が…
ちょっと頭を使う系の問題。この時期の ABC-A にはこういうものが多かったね。 問題へのリンク 問題概要 りんごをちょうど 個買いたい 円払って 個買う 円払って 個買う のいずれかによって、ちょうど 個買うための最小コストを求めよ。 解法 以下のいずれか…
頑張って頭を整理しよう！ 問題へのリンク 問題概要 整数 が与えられる。 , となるように整数 を選ぶとき、 の最大値を求めよ。 解法 を最大にするためには、 を最大にする を最小にする ようにすればよい。よって、 , のときに は最大であり、最大値は であ…
文字を固定したり、数式処理したりなど、総合力が問われる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…
発想の転換が必要になる。与えられた数の順列を考えるのではなく、平方数の方を列挙していく。 問題へのリンク 問題概要 数字のみからなる長さ の文字列 が与えられる。 を並び替えて得られる文字列であって、平方数を表すものが何通りあるかを答えよ。 制約…
高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…
すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…
シンプルながらも、学べるポイントがたくさんある問題ですね 問題へのリンク 公式解説へのリンク 問題概要 JOI 市には から までの番号が付けられた 人の住民がいて、住民 () の年齢は 歳です。 JOI 市の住民の年齢 が与えられます。 に対して、住民 と他…
古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった！ 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …
手を動かしてみると、どうなってるかが見えてくる！ 問題へのリンク 問題概要 人がそれぞれ座標 に並んでいる (単調増加、負もありうる、各 は偶数)。そして時刻 0 において、 人はそれぞれ正の方向 ( で与えられる) または負の方向 ( で与えられる) に 1 秒…
意外とすぐにわからなかったんやけど... 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。以下の条件をみたす最大の正整数 を求めよ。 を空でない 個の文字列へと分割したとき、連続する文字列は相異なる 制約 Greedy は嘘 パッと思い浮かぶ …
とても面白い問題です！ 問題へのリンク 問題概要 頂点数 、辺数 の、連結な重み付き無向単純グラフ が与えられる。 このグラフの「最小全域木」はさまざまなものが考えられるが、そのすべてに含まれるような辺の集合を考える。 その集合の要素数と、その集…
本当にただ全探索するだけ！！！ でも意外とこういうのが思いつかれにくいかもしれない。 問題へのリンク 問題概要 (意訳) 長さ の整数列 が与えられる。今、整数 を 1 つ選ぶ。そして整数列をすべて に書き換える。それに要するコストは で与えられる。適切…
ボロノイ図！！ 問題へのリンク editorial 問題概要 頂点の凸多角形と、 個の点が与えられる。以下の条件を満たす最小の正の実数 を求めよ。 個の点を中心とした半径 の円を考える 凸多角形の周および内部のどの点も、いずれかの円に包含される 制約 考えた…
面白かった！ 問題へのリンク editorial 問題概要 次の問題が ケース分与えられる。 二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。 どの点に対しても、 との距離が等しい 制約 考えたこと …
比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …
こういう重たい実装を確実にこなせるように...なりたい！ 問題へのリンク 問題概要 個の文字列 が与えられる。これらを好きな順序で好きな回数だけ concat して回文を作りたい。ただし 番目の文字列を使用するコストは 1 回あたり である。 回文を作れるかど…
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
