緑色diff
とても重たくて大変な問題。いろんな整理の仕方があると思う。 問題へのリンク 問題概要 下図のように、座標平面が 1 x 2 の長方形に区切られている。 座標 から座標 へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。 制約 考えたこ…
面白かった! 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう! このとき、求めたい値は次のように表現できる。 よって、 と…
すごく教育的問題! 問題へのリンク 問題概要 非負整数 が与えられるので、次の値を 998244353 で割った余りを求めよ。 & 制約 考えたこと この手の問題は「主客転倒」して、上記の総和を各桁ごとに考えればよいと相場が決まっている!!! 具体的には、次の…
この時代は Greedy が多かった。そして、実はすごく単純なことに気がつくかどうかが問われる問題! 問題へのリンク 問題概要 数直線上 (東西方向) に 個の町があり、それぞれの町の座標は である。町 1 から出発して、すべての町を訪れたい。次の 2 つの手が…
素因数分解を上手に活用しよう! 問題へのリンク 問題概要 正の整数 が与えられる。 の正の約数の個数を 1000000007 で割った余りを求めよ。 制約 考えたこと 「約数の個数」をまともに考察する場合には、素因数分解が役にたつことが多い。一般に正の整数 が…
昔ながらの典型考察 Greedy 問題。 問題へのリンク 問題概要 本の刀がある。 刀 を振ると、敵に だけダメージを与える。何度でも振ることができる 刀 を投げると、敵に だけダメージを与える。刀 を失うので、もう投げることも振ることもできなくなる 敵に …
データ構造をいい感じに設計する地力が問われる! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…
next_combination を使った! 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
発想の転換が必要になる。与えられた数の順列を考えるのではなく、平方数の方を列挙していく。 問題へのリンク 問題概要 数字のみからなる長さ の文字列 が与えられる。 を並び替えて得られる文字列であって、平方数を表すものが何通りあるかを答えよ。 制約…
問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題! 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…
素朴なシミュレーションが通るものの、それを正確に実装するのも結構大変 問題へのリンク 問題概要 種類のスライムがいる。 種類目のスライムは、サイズが であり、 体いる。 一般にサイズが であるスライムを 2 体合体させて、新たにサイズが のスライムを …
chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…
「二分探索 lower_bound()」「累積和」を活用する、とてもとても典型的かつ教育的な問題ですね。 問題へのリンク 問題概要 サイズ の数列 と、サイズ の数列 が与えられる。 これらの数列から 1 個ずつ選んでできる 通りの各ペア についての、 の総和を求め…
色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…
考察に時間をかけすぎた 問題へのリンク 問題概要 文字 'A' と 'B' のみからなる長さ の文字列 が与えられる (先頭の文字を 0 文字目とする)。各 について、次の問に答えよ。 Alice と Bob が交互に、以下の操作を合計 回行う。Alice が先手である。なお、最…
壁にぶつかるまで動く設定の迷路問題! 問題へのリンク 問題概要 のグリッドがある。各マスは壁 (文字 '#') か通路 (文字 '.') かのいずれかである。グリッドの外周のマスはすべて壁であることが保証されている。 プレイヤーは最初、マス にいる (0-indexed)…
今なお色褪せることのない、DFS・BFS の入門にいい感じの練習問題!!! 問題へのリンク 問題概要 次のような、 のサイズのグリッドの入力が与えられます。各マスの文字は 'o' か 'x' かのいずれかです。 あなたは、グリッド内部の文字を 1 つ選んで 'o' に…
人生で最初に解きたい BFS の問題! 問題へのリンク 問題概要 のグリッドが与えられます。各マスは壁 (文字 '#')、通路 (文字 '.') のいずれかです。通路マスに入ることはできますが、壁マスに入ることはできません。 スタートマス (入力で与えられる) から…
最小回数を求めるには BFS!!(素振り) 問題へのリンク 問題概要 黒板に整数値 が書かれています。次のいずれかの操作を最小回数繰り返すことによって、整数値 の値を にしたいとします。 を 倍して にする を十進法表記したときに、末尾の値を先頭に持って…
グラフの入門に! 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 各頂点 に対して、「友達の友達」、つまり頂点 からの距離が 2 であるような頂点の個数を求めてください。 自分自身や、友達 (距離が 1 である頂点) は含めないも…
Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…
「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン! 問題へのリンク 問題概要 二次元平面上で、左下の頂点が 、右上の頂点が であるような長方形状のケーキがあります。 このケーキ上には 個のいちごが乗っていて、 番目の…
「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …
DFS などの探索をしても解けるし、単に次数を見るだけでも解ける。 問題へのリンク 問題概要 個の葉をもつスターグラフを、レベル のスターと呼ぶことにする。 高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は …
なんかユーザー解説の数がすごいことになっててビビる! 問題へのリンク editorials 問題概要 以下の正の整数 の組であって、 が平方数であるようなものの個数を求めよ。 制約 考えたこと この手の問題では「ある変数を固定して考える」という常套手段がある…
「ある量を固定して考えるとよい」「 まで調べればよい」という 2 つの典型を組み合わせて解ける問題ですね! 問題へのリンク 問題概要 正の整数 が与えられる。 以上の整数のうち、 以上 以下の 2 つの整数 の積 として書ける最小の整数を求めよ。 そのよう…
基本的に Greedy にやればよさそうなのに、意外とやりづらい問題。基本に忠実にやれば解ける! 問題へのリンク 問題概要 文字 '0', '1', '?' のみからなる文字列 が与えられる。 中の各 '?' をそれぞれ '0' または '1' に置き換えて得られる文字列を二進法表…
ほどよい全探索問題! 約数列挙のアルゴリズムなどをちゃんと理解していれば解ける! 問題へのリンク 問題概要 以下の正整数のうち、 なる素数 を用いて と表せるものはいくつあるか? 制約 前提知識 この問題を見てまったく見当もつかないという場合には、…
上手に整理すれば、とてもシンプルな問題! 問題へのリンク 問題概要 正の整数 が与えられる。 を で割った商 を で割ったあまりを求めよ。 制約 考えたこと で割るような操作を 2 回しているので、 を で割った余りを考えるとよいのだろうなというあたりを…