2024-07-07から1日間の記事一覧
実装問題! 問題へのリンク 問題概要 のグリッドがあって、各マスは白色または黒色に塗られている。今、「白色のマスを選んで黒色に塗る」という操作を高々 2 回まで実施できる。 操作後に、縦・横・斜めのいずれかに連続して 6 個のマスが黒色になるように…
「グラフ」の基礎になるような、配列上のシミュレーションの問題。 問題へのリンク 問題概要 整数 が与えられる。 このとき、ボタンを押すと、画面の数値 () が に変わる。 最初の数値が 0 であるとき、ボタンを 3 回押すと、どんな数値に変わるか? 考えた…
ビット全探索の要領で列挙できる。だが、実は、部分集合列挙には専用の書き方も存在する! 問題へのリンク 問題概要 非負整数 が与えられる。次の条件を満たす非負整数 を昇順にすべて出力せよ。 と をともに二進法で表すとき、 において値が 1 である桁につ…
ビット全探索の典型問題! 問題へのリンク 問題概要 ポップコーンには 種類の味 がある。 一方、ポップコーンを得る 個の店 がある。各店 でどの味のポップコーンを売っているかを表す文字列 が与えられる。文字 が 'o' であるとき、店 で味 を売っているこ…
とても重たくて大変な問題。いろんな整理の仕方があると思う。 問題へのリンク 問題概要 下図のように、座標平面が 1 x 2 の長方形に区切られている。 座標 から座標 へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。 制約 考えたこ…
面白い問題! 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
すごく面白い問題! いろんな嘘解法がありそうで怖い。 問題へのリンク 問題概要 長さ の数列 が与えられる。今、数列の 1 つの要素の値を自在に書き換えることができる。 操作後の数列の LIS の長さを求めよ。 制約 考えたこと この手の問題では、まずは操…
木の直径の問題! 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は、頂点 と頂点 を結んでおり、長さは である。 いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めよ。 制約 考えたこと もし仮…
よくある、パズルの最小手数を求める問題! この手の問題では、まず「あり得る状態」がどれだけあるかを見積もろう! 問題へのリンク 問題概要 マスがあって、最初、前から マスには白石か黒石のいずれかが置かれている。置かれ方は文字列 で表される。後ろ …
めっちゃ面白い問題!! 実はよく似た類題として次の問題がある! atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
「2 つの区間の交差している部分の長さ」を求める問題は典型。それが 3 次元になってもやることは一緒。 問題へのリンク 問題概要 3 次元空間内の直方体であって、2 点 を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なもの…
for 文の練習問題! 問題へのリンク 問題概要 個の商品があって、それぞれ価格は 円である。これらをすべて購入する。 ただし、最高価格のものは半額となる。このとき、支払い金額の総和を求めよ。 制約 は偶数 解法 について、 総和を 最大値を としよう。…
for 文の練習問題。 問題へのリンク 問題概要 長さ の整数列 が与えられる。 この数列の 番目の要素の直後に値 を挿入して得られる数列を出力せよ。 解法 (1):関数 erase() を利用する C++ では、vector 型変数 A に対して、 番目に値 を挿入する処理は A.i…
包除原理した! 問題へのリンク 問題概要 1 以上 以下の正整数 であって、ある正整数 と 2 以上の正整数 を用いて と表現できるものはいくつありますか? 制約 考えたこと まず考えたのは、 は素数のみ考えれば良いということだった。たとえば、 というよう…
方針を決めるのが大変な問題。 問題へのリンク 問題概要 二次元平面上の 個の格子点に碁石が置かれている。 このとき、碁石によって囲われている格子点の個数を求めよ。より正確には、「その空き格子点から上下左右の空き格子点への移動を繰り返して点 (-1, …