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

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

NoviSteps4Q

AtCoder ABC 357 C - Sierpinski carpet (4Q, 灰色, 250 点)

いろんな方法で実装できそう! 問題へのリンク 問題概要 非負整数 に対して、レベル のカーペットを再帰的に定義する。 レベル のカーペットは、"#" からなる 1 × 1 のグリッドである に対して、レベル のカーペットは のグリッドであり、 このグリッドを の…

AtCoder ABC 265 C - Belt Conveyor (4Q, 灰色, 300 点)

二次元グリッド上を上下左右に動いていくシミュレーション問題。無限ループの判定が少しややこしい。 問題へのリンク 問題概要 のグリッドがあり、各マスには U, D, L, R のいずれかが書かれている。それぞれ、上、下、左、右へと進む指示を表している。 た…

AtCoder ABC 231 C - Counting 2 (4Q, 灰色, 300 点)

鉄則本 B11 とほぼ同じ問題! 問題へのリンク 問題概要 身長が であるような 人がいる。以下の 回のクエリに答えよ。 【クエリ】 整数 key が与えられるので、身長が key 以上の人が何人いるかを答えよ。 制約 考えたこと 0-indexed で考えます。 最初に、 …

鉄則本 B11 - Binary Search 2 (4Q, ★3)

lower_bound() の練習!! 問題へのリンク 問題概要 長さ の配列 が与えられる。この配列に対して 回のクエリに答えよ。 【クエリ】 整数 が与えられるので、配列 の中に より小さい要素が何個あるかを求めよ。 制約 解法 github.com コード #include <bits/stdc++.h> using</bits/stdc++.h>…

AtCoder ABC 207 C - Many Segments (4Q, 灰色, 300 点)

これはちょっと整理が大変な問題。時々問題文に登場する 0.5 という数値がなんなのかを知れる問題とも言える。 問題へのリンク 問題概要 個の区間がある。各区間は 4 タイプあり、 タイプ 1:区間 タイプ 2:区間 タイプ 3:区間 タイプ 4:区間 となってい…

鉄則本 B06 - Lottery (4Q, ★2)

累積和をやって、その次にやる類題として、そりゃこれを出すよね!! って感じの問題ですね。 問題へのリンク 問題概要 回くじびきを引いた。 回目の結果は であった ( のときアタリ、 のときハズレ)。 次の 回のクエリに答えよ。 【クエリ】 が与えられるの…

鉄則本 A06 - How Many Guests? (4Q, ★2)

累積和に関する問題!! 問題へのリンク 問題概要 日間にわたるイベントを開催し、日 には 人が来場した。次の 回のクエリに答えよ。 【クエリ】 各クエリでは が与えられるので、 日目から 日目までの間に合計何人が来場したかを答えよ。 制約 解法 累積和…

AtCoder ABC 168 C - : (Colon) (4Q, 灰色, 300 点)

余弦定理を使うか、座標を求めるか、、、いずれにしても三角関数の素養を要求する問題。 問題へのリンク 問題概要 時計の時針と分針があって、それぞれ長さは , となっている。 時 分の段階において、時針の先端と分針の先端との距離がどのようになっている…

競プロ典型 90 問 007 - CP Classes(4Q, ★3)

とても教育的な二分探索の問題ですね! この問題は、より高度な問題では部分的に何度も登場するような、極めて典型的な問題なので、そのまま覚えてしまうくらいでいいと思います!!! 問題へのリンク editorial 問題概要 個の整数 が与えられます。 この数…

競プロ典型 90 問 004 - Cross Sum(4Q, ★2)

グリッドの縦方向の情報と横方向の情報を前処理するのは典型ですね!! 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 のグリッドの各マス目に数値が書かれている。 各マス に対して、「そのマスと行または列が等しいマスの数値の総…