けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

格子点

AtCoder ARC 167 E - One Square in a Triangle (銅色, 800 点)

天才構築ゲー。これ完全自力で一発 AC できて嬉しかった!! 問題へのリンク 問題概要 正の整数 が与えられる。次の条件を満たす三角形が存在するかどうかを判定し、存在すれ場合は 1 つ求めよ。 頂点がすべて格子点であり、座標値は 以上 以下である すべて…

AtCoder ABC 330 C - Minimize Abs 2 (3Q, 茶色, 300 点)

文字を固定したり、数式処理したりなど、総合力が問われる問題! 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…

TTPC 2023 E - R-Connected Components

大好き!!ガウス整数の問題リストがまた 1 個増えた! 問題へのリンク 問題概要 1 つの正の整数 が与えられる。 二次元平面上の任意の格子点を頂点としたグラフにおいて、距離の平方が であるような 2 点間に辺を張っていく。 こうしてできたグラフの連結成…

AtCoder ABC 265 F - Manhattan Cafe (黄色, 500 点)

次元空間という、いかめしいものが出てくるけど、あまり関係ない。DP 高速化が本質。 問題へのリンク 問題概要 次元空間上に 2 つの格子点 , が与えられる。 これらとのマンハッタン距離がともの 以下であるような格子点の個数を 998244353 で割ったあまりを…

AOJ 3217 Cafe au lait (OUPC 2020 I)

数学っぽい問題好き!!! 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

AtCoder AGC 036 A - Triangle (緑色, 400 点)

ちょっと面白い感じの構築問題! 問題へのリンク 問題概要 正の整数 が与えられる。 以下の条件を満たす 3 つの格子点 の組を一つ求めよ。 座標値はすべて 以上 以下の整数値 3 つの格子点からなる三角形の面積を 2 倍すると に一致 制約 考えたこと 仮に 1 …

CS Academy 076 DIV2 D - Pyramids

えーーーーー、どうしてバグに気づかなかった。。。orz 問題へのリンク 問題概要 x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。 制約 1 <= N <= 10…

TopCoder SRM 401 DIV1 Hard - NCool (本番 5 人)

最近、ABC 201〜300 の D 問題埋めを推奨している身としては、僕も同様のトレーニングとして SRM 401〜650 辺りの DIV1 Hard 埋めを始めてみようと思い立った。 問題へのリンク editorial へのリンク 問題概要 二次元平面上において、以下の条件を満たす線分…