NoviSteps2Q
いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…
左右からの累積和・累積 max を前処理で求めておくのは、よくある典型!! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 個のクエリに答えよ。 【クエリ】 区間 が与えられるので、数列からその区間を除外した領域について、整数値の最…
二次元いもす法の練習問題 問題へのリンク 問題概要 二次元平面上に 枚の長方形の紙がある。 枚目の紙の左下の座標は であり、右上の座標は である。 紙に覆われている部分の面積を求めよ。 制約 考えたこと 二次元いもす法の練習。 github.com コード #incl…
二次元いもす法! 問題へのリンク 問題概要 のグリッドにおいて、 日間雪が降った。 日目には、マス を左上とし、 を右上とする長方形領域に雪が 1 cm だけ降った (溶けないとする)。 最終的な各マスの積雪量を求めよ。 制約 解法 二次元いもす法をします。…
二次元累積和の練習問題! 問題へのリンク 問題概要 二次元平面上に 個の点がある。 番目の点の座標は である。 「x 座標が 以上 以下で、y 座標が 以上 以下であるような点は何個あるか?」 というタイプの 回のクエリに答えよ。 制約 解法 x, y 座標の値が…
二次元累積和! 問題へのリンク 問題概要 のグリッドがあり、マス には値 が書かれている。次の 個のクエリに答えよ。 【クエリ】 左上が 、右上が であるような長方形領域が与えられるので、領域内のマスに書かれた整数の総和を求めよ。 制約 解法 鉄則本に…
yukicoder で「構築」練習することにした! 問題へのリンク 問題概要 英小文字からなる文字列 であって、次の条件を満たすものを求めよ。 文字数は 以下である どの隣接する文字も相異なる の連続する部分文字列であって、回文であるものがちょうど 個存在す…
次の問題にとても似ていた! drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
まず、これをグラフの問題として捉えるところに、一つ山がある印象だけど、みんなあっさり超えていてすごい! 問題へのリンク 問題概要 以下の正整数からなる長さ の数列 、 が与えられる。これらの数列の組が次の条件を満たすかどうかを判定せよ。 0 と 1 …
C 問題としてはかなりハードな問題であった。 問題へのリンク 問題概要 個の文字列 のうち、文字列 との編集距離が 1 以下であるものの個数を求めよ。 なお、文字列 と文字列 の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。 である …
発想の転換が必要になる。与えられた数の順列を考えるのではなく、平方数の方を列挙していく。 問題へのリンク 問題概要 数字のみからなる長さ の文字列 が与えられる。 を並び替えて得られる文字列であって、平方数を表すものが何通りあるかを答えよ。 制約…
あまりにも色んな解法がある問題 問題へのリンク 問題概要 の順列 と正の整数 が与えられる。 各 に対して、順列の先頭から 個の値の中での 番目に大きい値を求めよ。 制約 考えたこと 次の問題の下位互換と言える。 drken1215.hatenablog.com この上位互換…
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
久しぶりの、再帰関数を書きたくなるタイプの全探索! 問題へのリンク 問題概要 各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。 番目の 321-like 数を求めよ。 制約 321-like 数の個数 解法 (1):異常 10 重 for 文 この解法は本当に根性で…
どうなっているのかを観察して計算量を減らす系。観察力が問われる! 問題へのリンク editorials 問題概要 個の碁石を左から順に並べていく。 番目に並べる碁石の色は である ( 以上 以下の数値)。碁石を並べるときの規則は次のようになる。 番目の碁石を 番…
Library Checker というと難しいイメージがあるけど、この問題のように基本的な問題もある。でも、「最短路の復元」を要求する問題は意外と少ないので、とても貴重な問題! 問題へのリンク 問題概要 頂点数 、辺数 の単純な重み付き有向グラフが与えられる。…
ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…
最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…
「最適解の個数」を求めるという超典型! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…
幾何の問題。特に「線分と線分の交差判定」に関する問題! 問題へのリンク 問題概要 凸とは限らない 角形 が与えられる。 番目の頂点の座標は である。 この多角形 の外部に 2 点 , がある。この 2 点を結ぶことによって、多角形 をいくつかのピースに分ける…
グラフで考えよう! 問題へのリンク 問題概要 階建てのビルがあります。 ハシゴが 個あり、 個目のハシゴは 階と 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。 高橋くんは最…
ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる! 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…
データの持ち方をうまく工夫することで、計算量を改善する系の問題! 問題へのリンク 問題概要 長さ の数列 が与えられる。 個のクエリが与えられるので、それらを順に処理せよ。クエリは次の 3 種類ある。 x:数列 をすべて に書き換える i x: に を足す i…
緑色下位 diff かなと思っていたのですが、これが茶色なのすごいですね! 問題へのリンク 前提知識 エラトステネスのふるい 二分探索 問題概要 素数 を用いて と表される数を「250 に似た数」であると言います。 整数 が与えられますので、 以上 以下の「250…
ビット全探索もついに茶色 diff ですね! 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです! drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…
「競プロ典型 90 問 001 - Yokan Party」とよく似た問題! 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…
DFS (深さ優先探索) の動きをシミュレーションする問題。 問題へのリンク 問題概要 頂点番号が であるような木が与えられます。 今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。 いまいる頂点に隣接する頂点のうち、まだ訪れたことが…
ABS (AtCoder Beginner Selection) の 9 問目に選んだ問題! 問題へのリンク 問題概要 英子文字からなる長さ の文字列 が与えられます。 をいくつかの連続する文字列に分割して、かつそれらの文字列がすべて "dream", "dreamer", "erase", "eraser" のいずれ…
Union-Find や、DFS、BFS などで解ける問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフ が与えられます。 グラフ の辺 が橋であるとは、その辺を除去したときに、グラフが連結でなくなることを指すものとします。 グラフ におい…