区間の交差
「白い部分」が常に長方形であることから、その位置を上手に管理しよう。 問題へのリンク 問題概要 座標平面上で、2 点 を対角線とする長方形領域が与えられる。はじめ、全体が白く塗られている。この領域に対して、次の 回の操作を行なった。 【操作】 3 つ…
「2 つの区間の交差している部分の長さ」を求める問題は典型。それが 3 次元になってもやることは一緒。 問題へのリンク 問題概要 3 次元空間内の直方体であって、2 点 を結ぶ線分を対角線とし、全ての面が xy 平面、yz 平面、zx 平面のいずれかに平行なもの…
これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1：区間 タイプ 2：区間 タイプ 3：区間 タイプ 4：区間 となってい…
区間の交差を求めるのは頻出の典型処理だし、実務でも使えるテクニックなので、このまま覚えてしまって良いと思う！ 問題へのリンク 問題概要 数直線において、 から までの部分をすべて赤色で塗り から までの部分をすべて青色で塗った このとき、赤色と青…
区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…
Z-algorithm や Suffix Array が使える面白い文字列検索問題！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たす文字列 の組が何個あるかを答えよ。 はいずれも空文字ではない である 制約 考えたこと この手の問…
これ、「重なるものを数える」という風に考えれば、縦方向と横方向を独立に考えれば良いことに気付けるかが結構ポイントっぽい 問題へのリンク 問題概要 整数 が与えられます。 辺の長さが の白い正方形を座標平面の に 4 頂点が重なるように置きます。 次に…
実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…
条件反射でいもす法をしたけれど、もっと楽にできた 問題へのリンク そして手前味噌ながら類題 atcoder.jp 問題概要 個の区間 があたえられる。 を満たしている。 この区間が 重に交わっている部分の長さを求めよ。 制約 解法 1：区間の交差 区間 と の交差…
いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…
