茶色diff
少し考察が必要になる問題。結局隙間なく作れる。 問題へのリンク 問題概要 最初、黒板に 0 という数が書かれている。 秒後には、黒板に書かれた数 を以下のいずれかに置き換えることができる。 黒板に書かれた数を にできるのは最短で何秒後か？ 制約 考え…
二部グラフ判定を書いたことがあれば、その要領で解ける！ 問題へのリンク 問題概要 頂点数 、辺数 の重み付き有向グラフが与えられる。各頂点 に値 を書き込む方法であって、どの辺 に対しても を満たすようなものを 1 つ求めよ (そのようなものが存在する…
まともに計算すると桁数がとんでもないことになるので、「LU で消す」「RU で消す」を活用しよう！ 問題へのリンク 問題概要 頂点数が十分多い完全二分木が与えられる。根の番号は 1 であり、一般に頂点 の左子頂点の番号は 、右子頂点の番号は である。 最…
この時代多く見られた「グルーピング」の問題！ 問題へのリンク 問題概要 S 型ピース 1 個と c 型ピース 2 個を使って、下図のように Scc を 1 個作ることができる。 また、c 型ピース 2 個を使って S 型ピース 1 個を作ることもできる。 今、S 型ピースが …
ちょっとした算数の問題！ 問題へのリンク 問題概要 サイコロを転がしていく。サイコロの上の目の値を足していく。 その総和が 以上となるまでの最小回数を求めよ。 制約 考えたこと 6, 5, 6, 5, ... と繰り返していくのが最適である。それを求めるために、…
綺麗な言葉で条件を言い換えよう！ 問題へのリンク 問題概要 一列に白色碁石と黒色碁石が合計 個並んでいる。 左右のいずれかに白色碁石と黒色碁石を置いていく。このとき、オセロのルールに基づいて石の色がひっくり返る。 すべての色を同色にするのに必要…
高校数学ではお馴染みの塗り分け問題！ 問題へのリンク 問題概要 個のボールが一列に並んでいる。これらのボールを 色を使って塗り分ける。ただし、隣り合うボールの色は異なる色にしなければならない。何通りの塗り方があるか？ 制約 答えは 以下 考えたこ…
愚直シミュレーション問題！ 問題へのリンク 問題概要 A さん、B さん、C さんの 3 人が以下のようなカードゲームをプレイしています。 最初、3 人はそれぞれ 'a', 'b', 'c' いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた…
操作によってできるものの個数を数え上げる系の問題の最も基本的な問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。 を満たす を好きなように選んで、 の 文字目と 文字目を swap …
制約が小さいのでなんとでもなる。C++ なら文字列の末尾を削除する関数 pop_back() を知っていると楽だと思われる。 問題へのリンク 問題概要 エディター上で、'0'、'1'、'B' という 3 種のタイピング入力を行う。 '0' と打つと、エディターに表示された文字…
何気にちゃんと証明しようとすると、結構大変な問題な気もする！ 問題へのリンク 問題概要 長さが である 個の文字列 が与えられる。 これらを好きな順番ですべて結合して得られる文字列のうち、辞書順最小のものを求めよ。 制約 考えたこと 直感的には、 を…
とっても教育的な DP の問題！！！ 問題へのリンク 問題概要 高橋君の前に 個の料理が順に配られる。高橋君はその都度「食べる」「下げてもらう」を選択することができる。 番目の料理は、 のとき、解毒剤入りの、美味しさが の料理 のとき、毒入りの、美味…
スタックを活用する系の問題！ 問題へのリンク 問題概要 値 の書かれたボールをこの順に筒に挿入していく。 挿入された際に、同じ数 が 個連続したら、それらがすべて消えるものとする。 個目のボールが挿入された瞬間の、筒内のボールの個数を逐次答えよ。 …
部分和問題・ナップサック問題とほとんど同じ DP で解ける！ 問題へのリンク 問題概要 数直線上で座標 0 から出発して、 回のジャンプをする。 回目のジャンプでは、正の方向に または の移動をする。 回のジャンプの末に座標 に到達することが可能かどうか…
カッコ列に関連してシミュレーションしていく問題！ 問題へのリンク 問題概要 英小文字と文字 '('、')' からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返す。 「文字 '(' と ')' に挟まれた部分文字列であって、カッコ文字を含ま…
問題の意味を理解するのが難しいが、理解してしまえばビット全探索で解けることは比較的分かりやすいと思う！ 問題へのリンク 問題概要 本の鍵 があり、それぞれ本物であるか、ダミーであるかのいずれかである。ドア X があり、鍵のうちの 本以上の本物が使…
ものすごく教育的な典型問題！ 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…
とても教育的な Greedy 問題！ 問題へのリンク 問題概要 個の非負整数からなる数列 が与えられる。この数列に対して、 「正の整数である要素を 1 つ選び、-1 する」 という操作を繰り返すことで、どの隣接する 2 個の要素の和も 以下となるようにしたい。 こ…
この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！ 問題へのリンク 問題概要 台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。 【クエリ】 トナカイが 匹いるときに、最大で何台…
色んな方法があるが、できるだけ楽にやりたい！ 問題へのリンク 問題概要 単調増加な 要素からなる数列 がある。この数列について、次の 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、 のどれとも異なる数値 (よい数と呼ぶこととする) のうち、…
いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…
古き良き、ABS にも入れた代表的問題。 問題へのリンク 問題概要 10000 円、5000 円、1000 円が合計 枚ある。 このとき、これらの合計金額が 円になることがありうるかどうかを判定し、ありうるならばそれを 1 つ答えよ。 制約 解法 次の記事に解法を書いて…
慎重に解いた。ノーペナで解けたのは収穫。 問題へのリンク 問題概要 のグリッドに、以下の条件を満たすように 個のルークと 個のポーンを配置することが可能かどうかを判定せよ (ルークとポーンを合わせて駒と呼ぶ)。 どのルークについても、それと同じ行・…
次の問題にとても似ていた！ drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…
文字を固定したり、数式処理したりなど、総合力が問われる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…
stack を使ってカッコ列判定をする問題の亜種！ 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…
まず、これをグラフの問題として捉えるところに、一つ山がある印象だけど、みんなあっさり超えていてすごい！ 問題へのリンク 問題概要 以下の正整数からなる長さ の数列 、 が与えられる。これらの数列の組が次の条件を満たすかどうかを判定せよ。 0 と 1 …
またまた登場！！ グラフの連結成分の個数を求める問題！ 問題へのリンク 問題概要 下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。 このとき、グリッド内に何個の '#' の塊があるかを…
伝説の誤差問題！！ 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…
C 問題としてはかなりハードな問題であった。 問題へのリンク 問題概要 個の文字列 のうち、文字列 との編集距離が 1 以下であるものの個数を求めよ。 なお、文字列 と文字列 の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。 である …
