AtCoder400点
「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね！ 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…
基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける！ 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…
データの持ち方をうまく工夫することで、計算量を改善する系の問題！ 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x：数列 をすべて に書き換える i x： に を足す i…
ほどよい全探索問題！ 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける！ 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか？ 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
部分和問題の応用問題！ 問題へのリンク 問題概要 個の非負整数 が与えられれる。 これらの整数から 個選んで、総和が の倍数となるようにする。その値として考えられる最大値を答えよ。 の倍数にするのが不可能な場合は -1 を答えよ。 制約 前提知識 この問…
重み付き Union-Find が有効活用できる問題！ 問題へのリンク 問題概要 個の変数 の値を決定したい。 これらの値を決定するための 本の制約条件がある。このうち 個めの情報は 3 つの値 によって与えられ、 であるという制約条件を表す。 これら 本の制約条…
色々な考え方ができる楽しい問題ですね！ 3 通りの解法を自分なりに咀嚼して整理しました。 問題へのリンク 問題概要 2 以上の整数 が与えられる。 が の倍数となるような最小の整数 を求めよ。 制約 考えること：まずは素因数分解 この問題のように、「倍数…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね！ 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
前回の ABC に続いて、D 問題が数学っぽい。でも実際には今回は探索問題ですね。 問題へのリンク 問題概要 非負整数 を用いて と表せる整数 を「特別数」と呼ぶことにします。 非負整数 が与えられますので、 以上である最小の「特別数」を求めてください。 …
問題を見て「めっちゃ数学やん！！なにこれ！？？」となった人は多いと思う！！！ でも落ち着いて整理して取り組めば解けるので、落ち着くことが大事そう。 もしくは、ライブラリで殴る！！！！！！ 問題へのリンク 問題概要 つの多項式 次の多項式 次の多項…
DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…
Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…
古き良き全探索問題！！ 問題へのリンク 問題概要 二次元平面上に 個の点があります。 番目の点の座標を とします。 この二次元平面上で各辺が X 軸・Y 軸に平行であるような長方形であって、 個の点のうち 個以上の点を内部および周に含むようなものを考え…
とても教育的かつ典型的な貪欲法の問題ですね。 問題へのリンク 問題概要 二次元平面上に、赤い点と青い点が 個ずつあります。 個目の赤い点の座標は であり、 個目の青い点の座標は です。 赤い点と青い点は、 座標と 座標がともに赤い点よりも青い点の方が…
今や Union-Find やるだけだと茶色 diff (下手したら灰色 diff) だけど、ちゃんと考察要素を入れるとやっぱり緑色 diff になるのね。 問題へのリンク 問題概要 正の整数からなる整数列 が与えられる。以下の操作を好きなだけ行うことによって、 個の値がすべ…
自明な上界を達成できるパターンだった！ 問題へのリンク 問題概要 長さ の非負整数列 が与えられる。この数列はどの隣接する二項も値が異なる。 この数列をなるべく多くの 項の非負整数列へと分解せよ。分解とは 分解された各非負整数列の各項を足すと、も…
「決めてから、整合性を確認する」というタイプの問題の典型例ですね！ 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…
発想や考え方はそんなに難しくないんだけど、すごく頭がこんがらがってしまう問題だね... 問題へのリンク 問題概要 が表に書かれたカードが 枚ずつ、計 枚のカードがあります。 これらのカードをランダムにシャッフルして、高橋くんと青木くんにそれぞれ、4 …
ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…
数列をヒストグラム化することで解決できるタイプの問題！特に今回みたいに、数値の値も 以下と小さい場合はすごくそれっぽい！ 問題へのリンク 問題概要 長さが の正の整数からなる数列 が与えられる。以下の条件を満たす の個数を求めよ。 なる任意の に対…
これは難しい！！！ 誘惑されそうな嘘解法がたくさんある！！ 問題へのリンク 問題概要 件の日雇いアルバイトがあります。 件目の日雇いアルバイトを請けて働くと、その 日後に報酬 が得られます。 あなたは、これらの中から 1 日に 1 件まで選んで請け、働…
「大体こういう感じ」というところまではすぐに見えるけど、細かいところを詰めるのが大変な問題かもしれない。 問題へのリンク 問題概要 マスがあって、各マスには "L" または "R" が書かれている (左端は "R" で右端は "L" であることが保証される)。また…
一見すると かかるように思えるかもしれない。でも実は になる。 問題へのリンク 問題概要 個の整数 が与えられる (それぞれ 0 または 1)。このとき、 個の 0-1 変数 の値を、以下の条件を満たすように定めよ。 各 に対して、 を 2 で割ったあまりが に一致…
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
番兵を入れるとかすれば、怖いケースをあらかじめ除去できそう 問題へのリンク 問題概要 左右方向一列に 個のマスが並んでいます。 この 個のマスのうち、マス の 個のマスは青色で、それ以外のマスは白色です。 あなたは一回だけ、正整数 を一つ選んで幅 の…
本番 14 分かけたのは反省。 問題へのリンク 問題概要 "110" という文字列を 10000000000 個連結してできる文字列を とする。 長さ の文字列 が与えられる。 の中に が連続する部分文字列としていくつ含まれるかを求めよ。 制約 考えたこと こういう、端の処…
累積和の累積 max 問題へのリンク 問題概要 数列 が与えられます。 この数列は負の要素を含むかもしれません。 数直線上の座標 0 に置かれているロボットが、以下の動作を順に行います。 正の向きに 進む。 正の向きに 進み、正の向きに 進む。 正の向きに …
二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…
カッコ列系の問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。文字列に対して、以下の処理を繰り返し行う。操作の結果得られる文字列の長さの最小値を求めよ。 文字列中の "fox" を削除する 制約 考えたこと カッコ列でよく似た問題はすごく有…
