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

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

ABC-C

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

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

AtCoder ABC 329 C - Count xxx (灰色, 300 点)

ランレングス圧縮の典型題! なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…

AtCoder ABC 328 C - Consecutive (灰色, 300 点)

すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…

AtCoder ABC 326 C - Peak (灰色, 300 点)

lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…

AtCoder ABC 327 C - Number Place (灰色, 250 点)

9 × 9 に並んだ数字が「数独」の解になっているかを判定する問題 問題へのリンク 問題概要 下のような 9 × 9 グリッドが与えられる。各マスの値は 1 から 9 までの整数値である。 このグリッドが数独の要件を満たすかを判定せよ。 1 2 3 4 5 6 7 8 9 4 5 6 7…

AtCoder ABC 325 C - Sensors (茶色, 300 点)

またまた登場!! グラフの連結成分の個数を求める問題! 問題へのリンク 問題概要 下図のような のグリッドが与えられる。このグリッドにおいて、上下左右と斜めに隣接している '#' は一つの塊とみなす。 このとき、グリッド内に何個の '#' の塊があるかを…

AtCoder ABC 308 C - Standings (茶色, 300 点)

伝説の誤差問題!! 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…

AtCoder ABC 324 C - Error Correction (茶色, 300 点)

C 問題としてはかなりハードな問題であった。 問題へのリンク 問題概要 個の文字列 のうち、文字列 との編集距離が 1 以下であるものの個数を求めよ。 なお、文字列 と文字列 の編集距離が 1 以下であるとは、以下のいずれかが成り立つことを指す。 である …

AtCoder ABC 323 C - World Tour Finals (灰色, 250 点)

1 つ 1 つの要素は難しくないが、実装がとにかく重たい!落ち着いて整理して考えたい問題。 問題へのリンク 問題概要 プレイヤー が、配点が である 個の問題からなるコンテストに挑んでいる。なお、 は 以上 以下の の倍数である。 プレイヤー には最初から…

AtCoder ABC 322 C - Festival (灰色, 300 点)

for 文を回していくときに「前回の値を活用する」というテクが登場する問題。このテクは、後に「累積和」や「DP」を学ぶ際の大切な基礎となる。 問題へのリンク 問題概要 日間のうち、 日目には花火が上がる。 各日について、何日後に最初の花火が上がるかを…

AtCoder ABC 321 C - 321-like Searcher (茶色, 300 点)

久しぶりの、再帰関数を書きたくなるタイプの全探索! 問題へのリンク 問題概要 各桁の数値が狭義単調減少になっている数を 321-like 数と呼ぶ。 番目の 321-like 数を求めよ。 制約 321-like 数の個数 解法 (1):異常 10 重 for 文 この解法は本当に根性で…

AtCoder ABC 284 C - Count Connected Components (灰色, 300 点)

グラフ探索の問題として、人生で最初に解きたい問題!! 問題へのリンク 問題概要 頂点数 、辺数 の単純な無向グラフが与えられる。 このグラフの連結成分の個数を求めよ。 制約 解法 まず、単純グラフや連結成分という概念についてはこちら! algo-method.c…

AtCoder ABC 313 C - Approximate Equalization 2 (茶色, 400 点)

ちゃんと証明しないと、なかなか安心して提出できない系 問題へのリンク 問題概要 整数列 が与えられる。次の操作を繰り返し行って、 の最大値と最小値の差が 1 以下となるようにしたい。実現のための操作の最小回数を求めよ。 を選んで、 に 1 を足し、 か…

AtCoder ABC 311 C - Find it! (茶色, 350 点)

Functional グラフのサイクル検出問題! 問題へのリンク 問題概要 頂点数 のグラフが与えられる。頂点 からは頂点 への辺が接続していて、辺数は全部で 本ある。 このグラフにおいて、同一頂点を複数回含まない有向サイクルをひとつ求めてください。具体的に…

AtCoder ABC 306 C - Centers (灰色, 250 点)

バケットを使ってもいいし、set や map を使ってもいいかもしれない 問題へのリンク 問題概要 が 3 回ずつ表れる長さ の数列 が与えられる。 を「数列 において 2 回目にその値が登場する index」が小さい順にソートせよ。 制約 考察:まず問題を掴む 最初の…

AtCoder ABC 305 C - Snuke the Cookie Picker (灰色, 300 点)

楽な実装がないかと探す系の問題 問題へのリンク 問題概要 のグリッドにおいて、以下の操作が施されたものが入力として与えられます。 はじめ、グリッドのすべてのマスの文字は '.' である グリッドの部分長方形であって縦横のサイズがそれぞれ 2 以上である…

AtCoder ABC 068 C - Cat Snuke and a Voyage (ARC 079 C) (茶色, 300 点)

今の時代なら確実に灰色 diff ですね。 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。 頂点 と頂点 とを結ぶ辺は存在しないことがわかっている。 ある頂点 から 2 本の辺を辿ることで頂点 に到達できるかどうかを判定せよ。 制約 …

AtCoder ABC 277 C - Ladder Takahashi (茶色, 300 点)

グラフで考えよう! 問題へのリンク 問題概要 階建てのビルがあります。 ハシゴが 個あり、 個目のハシゴは 階と 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。 高橋くんは最…

AtCoder ABC 274 C - Ameba (灰色, 300 点)

木を探索する練習問題。頭を柔らかくするのが肝心。 問題へのリンク 問題概要 あなたはアメーバの観察記録をつけました。最初 匹のアメーバがおり、番号は です。 観察記録は時系列順に 個あり、 番目の観察記録は 番号 のアメーバが分裂して消滅し、 新たに…

AtCoder ABC 304 C - Virus (灰色, 300 点)

単純な DFS / BFS 系はいよいよ灰色 diff になったのですね。 問題へのリンク 問題概要 二次元平面上に 人がいます。 番目の人は座標 にいます。 今、 番目の人がウィルスに感染しました。ウイルスに感染した人から距離が 以内にいる人にウイルスは次々とう…

AtCoder ABC 297 C - PC on the Table (灰色, 300 点)

前から "PC" 詰めしていけば OK!! 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 '.' か 'T' が書かれている。今、次の操作をできるだけ多く行いたいとする。 左右に 2 文字連続した "TT" を "PC" に置き換える 操作回数の最大化を目指…

AtCoder ABC 303 C - Dash (灰色, 300 点)

set をちゃんと使えるかを試す問題! 問題へのリンク 問題概要 高橋くんは最初、体力は であり、二次元平面上の座標 にいる。 高橋くんは今から 回の移動を行う。高橋くんの移動方法は長さ の文字列 で表される。1 回の移動は、上下左右のいずれかであり、そ…

AtCoder ABC 302 C - Almost Equal (茶色, 300 点)

「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える! 問題へのリンク 問題概要 個の長さ の文字列 が与えられる。 これらを並び替えて得られる文字列 であって、 「 と が 1 文字違いである」() とい…

AtCoder ABC 227 C - ABC conjecture (茶色, 300 点)

これ、一見すると の計算量が必要に思えてしまうね! 問題へのリンク 問題概要 正の整数 が与えられる。 かつ であるような正の整数の組 の個数を求めよ。 制約 の範囲を絞る 約数列挙アルゴリズムなどでもお馴染みの、大小関係から整数の範囲を絞って探索す…

AtCoder ABC 292 C - Four Variables (茶色, 300 点)

これも最近よく見る「整数の式で表された条件を扱う探索問題」の一味ですね! 問題へのリンク 問題概要 整数 が与えられる。 正の整数 の組であって、 を満たすものの個数を求めよ。 制約 考えたこと もし計算時間をまったく気にしなくてよいならば、次のよ…

AtCoder ABC 272 C - Max Even (灰色, 300 点)

ちょっと面白い問題! 競プロ始めたばかりの方々に、計算量のことを意識させるのに良い問題かもしれない。 問題へのリンク 問題概要 どの 2 つの値も互いに相異なるような、長さ の数列 が与えられる。 この数列 の異なる 2 要素の和として表せる値の中に偶…

AtCoder ABC 301 C - AtCoder Cards (灰色, 300 点)

結構整理するの大変! 茶色あっても良さそうだと思ったけど、灰色上位問題だった。 問題へのリンク 問題概要 2 つの長さ の文字列 が与えられる。これらは英小文字または文字 '@' のみからなる。 の各文字 '@' は、"atcoder" に含まれるいずれかの文字に変え…

AtCoder ABC 300 C - Cross (茶色, 300 点)

実装が難しい系。僕は DFS をした。「島の個数」を数える問題なので、何も考えずに DFS すればいいと思った。 問題へのリンク 問題概要 下図のような のグリッドの入力が与えられる。 「# で作られた x の形からなる島」が何個あるかを、島の大きさごとに答…

AtCoder ABC 299 C - Dango (灰色, 300 点)

「要するに o の最長連続箇所を求めればいい (ただし例外あり)」って感じに、シンプルに整理する力が問われる問題! 問題へのリンク 問題概要 正の整数 に対して、 レベル のダンゴ文字列とは、以下の条件を満たす文字列である。 o と - からなる長さ の文字…

AtCoder ABC 298 C - Cards Query Problem (茶色, 300 点)

クエリ形式の問題に慣れたり、クエリに答えるためのデータ構造を考えたりすることに慣れたりするための練習問題! 問題へのリンク 問題概要 1 から までの番号のついた 個の箱と、何も書かれていない無数のカードがある。今、 個のクエリが与えられるので、…