補集合を考える
グリッドが幅広いが、黒色マスの周辺でしか「3 x 3 内部に黒色マスがある」という状況が発生しないことを活用する！ 問題へのリンク 問題概要 グリッドの各マスは白色または黒色である。 個のマスが黒色である（座標が与えられる）。 このグリッド内部の各 3…
操作によってできるものの個数を数え上げる系の問題の最も基本的な問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。 を満たす を好きなように選んで、 の 文字目と 文字目を swap …
set を使おう！ 問題へのリンク 問題概要 長さ の整数列 と、正の整数 が与えられる。 以上 以下の整数のうち、数列 に一度も含まれないものについての総和を求めよ。 制約 考えたこと まず、 となる。 この値から「1 以上 以下の整数のうち、数列 に一度以…
関数 max() や min() を扱う練習！ 問題へのリンク 問題概要 物理、化学、生物、地学、歴史、地理のテストで 点を得た。 物理、化学、生物、地学から 3 科目 歴史、地理から 1 科目 を選択したときの総得点の最大値を求めよ。 制約 考えたこと 結局、「物理…
楽しい問題！ 問題へのリンク 問題概要 3 個の整数 が与えられる。 これらの整数のうち、大きい方から 2 個の和を求めよ。 解法 から、「一番小さい数」を引けば良いでしょう。 のうち一番小さい数は、C++ では、関数 min() を用いて min({A, B, C}) と表せ…
木の直径の問題！ 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…
for 文の練習問題！ 問題へのリンク 問題概要 個の商品があって、それぞれ価格は 円である。これらをすべて購入する。 ただし、最高価格のものは半額となる。このとき、支払い金額の総和を求めよ。 制約 は偶数 解法 について、 総和を 最大値を としよう。…
上手に考えよう！ 問題へのリンク 問題概要 2 × 2 グリッドが与えられる。各マスは白黒に塗られている。 黒色マスの文字は '#' で与えられ、白色マスの文字は '.' で与えられる。黒色マスがすべて連結しているかどうかを判定せよ。 解法 まず、2 × 2 のグリ…
共通テスト数学 IA にも似た問題が出ていた！ 問題へのリンク 問題概要 頂点数が のサイクルグラフが与えられる。このグラフの各頂点を色 のいずれかの色で塗る。 どの隣接する頂点対も異なる色で塗られるようにする方法の個数を 998244353 で割った余りを求…
頭を柔らかくして考えよう。 問題へのリンク 問題概要 3 個の整数 から 2 個選んで和をとる。 この和の最大値を求めよ。 解法 3 個の整数 から 2 個選んだ和は の 3 通りがある。これらの最大値を求めればよい。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…
ジャンケンの問題。何気に将来非常によく出てくる構造を問う問題でもある。 問題へのリンク 問題概要 3 人でジャンケンをしたらあいこになった。3 人のうちの 2 人の出した手がわかっている。残り 1 人の手を答えよ。 なお、0 はグー、1 はチョキ、2 はパー…
算数！ 問題へのリンク 問題概要 サイコロの 6 面のうち、3 面の数 が見えている。 隠れている残り 3 面の数の和を求めよ。 解法 6 面の数の和は なので、これから を引けばよい。 #include <bits/stdc++.h> using namespace std; int main() { int a, b, c; cin >> a >> b </bits/stdc++.h>…
発想ゲー。 問題へのリンク 問題概要 1, 2, 3 のうちの 2 つの整数 が与えられる。 残りの整数を答えよ。 解法 色んな解法が考えられる。 の値で場合分けして解くこともできる。 しかし、最も簡単なのは、合計値が なのだから、そこから と を引く方法であろ…
過去に似た問題があった。その応用問題と言える。 問題へのリンク 問題概要 の白色のマス目がある。 行と 列を選んで、すべて黒色に塗った。 白色のマス目は何個残るか。 解法 白い部分をかき集めると、 の長方形となる。 #include <bits/stdc++.h> using namespace std; in</bits/stdc++.h>…
データ構造をいい感じに設計する地力が問われる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…
Polynomial Taylor Shift が使えた！ 問題へのリンク 問題概要 頂点数 の木が与えられる。各 に対して、次の問いに答えよ。 頂点から 個の頂点を選ぶ 通りの方法それぞれについて その 個の頂点をすべて含む連結な部分グラフのサイズとして考えられる最小値…
最近話題の Functional Graph の問題！ 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…
一般にグラフの問題を解くときは「連結成分ごとに解けば良いのではないか」と考えるのが有効なことがある！ その意識がしっかりしていれば、「グラフが非連結の場合に気づかなかった」という罠を回避できる！！ 問題へのリンク 問題概要 頂点数 、辺数 の単…
面白かった！！ より一般化した問題 (グラフの頂点集合の任意の部分集合に対して、それらを連結にする辺の選び方の数え上げ) を考えた方が考えやすいね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフ が与えられます。 の辺集合の部分集合 ( 通…
コンテスト中にアダマール変換を思い出せたのはよかった！ 問題へのリンク 問題概要 整数 と 個の整数 が与えられます。次の条件を満たすような Nim をすべて考えます。 山の個数は のいずれかである 各山の石の個数は のいずれかである このような Nim の盤…
包除原理の一番簡単な場合を試せる問題 問題へのリンク 問題概要 個の整数 が与えられる。以下の条件を満たす整数 の組の個数を求めよ。 制約 考えたこと まず、 という条件がないバージョンを考えてみよう。そのときは単に 個のものから 2 個選ぶ場合の数を…
約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1)：約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…
間に合わなかった！！！悔しい！！！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…
むずかしかった！！！ でも、約数列挙でありがちな「 まで試せば良い」という考え方がちゃんと理解できているかを問う良問だった！！ 問題へのリンク 問題概要 整数 が与えられる。 1 以上 以下の整数のうち、 2 以上の整数 を用いて と表せないものはいくつ…
lower_bound の練習に！！！ あと、「3 つのものを考えるときは、真ん中を固定して考える」という考え方の典型。 問題へのリンク 問題概要 3 つの数列 (長さ ) が与えられる。各数列から要素 を選ぶ方法のうち、 を満たすものの個数を求めよ。 制約 考えたこ…
これの応用問題って感じだった！！ drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…
ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…
面白かった！！ 問題へのリンク 問題概要 すぬけくんは長さ の文字列 を持っている。最初、 のすべての文字は 0 である。 すぬけくんは，以下の 2 種類の操作を好きな順序で好きな回数行うことができます． の連続する 文字を選んで，それらをすべて 0 にす…
こういう数え上げ、大好きすぎる！！！ 問題へのリンク 問題概要 長さ の数列 がある。初期状態ではすべての値が 0 となっている。この数列に以下の操作をちょうど 回行って得られる数列が何通りあるか、998244353 で割ったあまりを求めよ。 となる を選んで…
これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…
