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

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

灰色diff

AtCoder ABC 047 B - すぬけ君の塗り絵 2 イージー (6Q, 灰色, 200 点)

「白い部分」が常に長方形であることから、その位置を上手に管理しよう。 問題へのリンク 問題概要 座標平面上で、2 点 を対角線とする長方形領域が与えられる。はじめ、全体が白く塗られている。この領域に対して、次の 回の操作を行なった。 【操作】 3 つ…

AtCoder ABC 347 B - Substring (6Q, 灰色, 200 点)

set の使い方を覚えよう! 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列として考えられるものの個数を求めよ。 制約 考えたこと の連続する部分文字列をすべて取り出して、それを set に格納して、そのサイズを求めれば良い。 の連…

AtCoder ABC 348 B - Farthest Point (6Q, 灰色, 200 点)

面白い探索問題 問題へのリンク 問題概要 座標平面上に 個の点がある。点 の座標は である。 各 に対して、点 の距離が最大であるような の値を求めよ(タイがある場合は が最小のもの)。 制約 考えたこと 各 に対して、別々の問題を解く。 に対して (X[i] …

AtCoder ABC 349 B - Commencement (5Q, 灰色, 200 点)

まずは各文字が何回ずつ使われるかを求めよう! 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たすかどうかを判定せよ。 【条件】 すべての に対して、 中にちょうど 回登場する文字が 0 種類または 2 種類である…

AtCoder ABC 363 B - Japanese Cursed Doll (6Q, 灰色, 200 点)

シミュレーションするか、ソートするかによって解ける典型問題! 問題へのリンク 問題概要 人の髪の長さは最初 であった。 各人の髪の長さは 1 日に 1 ずつ伸びる。 初めて髪の長さが 以上の人が 人以上となるのは何日後かを求めよ。 制約 解法 (1):シミュ…

AtCoder ABC 365 B - Second Best (6Q, 灰色, 200 点)

second best を求める系の問題 問題へのリンク 問題概要 個の相異なる整数 が与えられる。 この数列のうち 2 番目に大きいものについて、それが の何番目の要素であるかを求めよ。 制約 解法 (1):max と second max を管理する 1 つ目の方法として、最大値…

AtCoder ABC 366 B - Vertical Writing (5Q, 灰色, 200 点)

問題文がやたら難読すぎる!!! 問題へのリンク 問題概要(意訳) 個の文字列 が与えられる。これに対して、次のように縦横をひっくり返して、隙間を文字 * で埋めたようなものを出力せよ。 before red orang blue yellow green gray skyblue black after b…

AtCoder ABC 370 C - Word Ladder (4Q, 灰色, 300 点)

操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題! 問題へのリンク 問題概要 文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。 そのう…

AtCoder ABC 370 B - Binary Alchemy (5Q, 灰色, 200 点)

こういう値を順次更新していくようなシミュレーションは慣れておきたい! 問題へのリンク 問題概要 元素 がある。 元素 を合成すると、 のときは元素 になり、 のときは元素 になる。 元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素…

AtCoder ABC 370 A - Raise Both Hands (8Q, 灰色, 100 点)

else if 文と、論理演算子「&&」の練習。 問題へのリンク 問題概要 2 つの整数 が与えられる。 かつ のときは "Yes" かつ のときは "No" それ以外のときは "Invalid" を出力せよ。 考えたこと else if 文と、論理演算子「&&」を使って、次のように書ける。 #…

AtCoder ABC 344 C - A+B+C (5Q, 灰色, 250 点)

とても教育的な問題! ちゃんと解くには、計算量の理解が必要となる問題である。 問題へのリンク 問題概要 3 つの数列 が与えられる。これらの数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、 からそれぞれ 1 個ずつ選んで和を…

AtCoder ABC 283 C - Cash Register (5Q, 灰色, 300 点)

「0 が連続何個続くのか」を求めるタイプの問題 問題へのリンク 問題概要 数字からなる長さ の文字列 が与えられる。 「1」「2」「3」「4」「5」「6」「7」「8」「9」「0」「00」と書かれた文字列スタンプを順に押して行って、 を作りたい。 スタンプを押す…

AtCoder ABC 369 C - Count Arithmetic Subarrays (3Q, 灰色, 300 点)

とても教育的で典型的なしゃくとり法の問題! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1):しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…

AtCoder ABC 369 B - Piano 3 (6Q, 灰色, 200 点)

このようなシミュレーションをサッと書けるようになりたいところ! 問題へのリンク 問題概要 横一列に 100 個の鍵盤からなるピアノがある。各鍵盤には順に と番号が振られている。 鍵盤を 回押す。 回目の鍵盤の位置は であり、 = 'L' のとき左手で押し、 = …

AtCoder ABC 369 A - 369 (6Q, 灰色, 100 点)

偶数と奇数に関する理解も問われる問題。 問題へのリンク 問題概要 2 つの整数 が与えられる。 「 を並び替えると等差数列をなす」 という条件をみたすような整数 が何通りあるか求めよ。 制約 解法 (1):数学的に解く まず、 の大小関係で場合分けして考え…

AtCoder ABC 153 B - Common Raccoon vs Monster (8Q, 灰色, 200 点)

for 文の練習問題! 問題へのリンク 問題概要 HP が であるモンスターを倒したい。 種類の必殺技を順に使っていく。 種類目の必殺技はモンスターの HP を だけ減らすことができる。 モンスターの HP を 0 以下にすることができるかどうかを判定せよ。 考えた…

AtCoder ABC 149 B - Greedy Takahashi (7Q, 灰色, 200 点)

if 文や else if 文の練習! 問題へのリンク 問題概要 高橋君は 枚、青木君は 枚のクッキーをもっている。 高橋君は 回次の行動をとる。 自分のクッキーが残っていたら、それを 1 枚食べる 残っていなくて、青木君のクッキーが残っていたら、それを 1 枚食べ…

AtCoder ABC 148 B - Strings with the Same Length (8Q, 灰色, 200 点)

楽しい for 文の練習問題! 問題へのリンク 問題概要 ともに長さが である 2 つの文字列 が与えられる。 の 1 文字目、 の 1 文字目、 の 2 文字目、 の 2 文字目、... の順に文字を連結して得られる文字列を答えよ。 考えたこと 次のように考えれば良いだろ…

AtCoder ABC 142 B - Roller Coaster (8Q, 灰色, 200 点)

for 文の練習問題! 問題へのリンク 問題概要 個の整数 のうち、 以上であるものの個数を求めよ。 考えたこと for 文を用いて、 に対して、 以上であるかどうかを判定していこう。 以上:答えを表す変数を 1 増やす そうでない:何もしない というようにすれ…

AtCoder ABC 154 B - I miss you... (8Q, 灰色, 200 点)

文字列の易しい練習問題! 問題へのリンク 問題概要 文字列 が与えられる。 のすべての文字を 'x' で置き換えたものを出力せよ。 考えたこと まず、文字列 S の長さ N は次のように取得できる(C++)。 int N = S.size(); その先はいくつかやり方がある。 fo…

AtCoder ABC 096 B - Maximum Sum (7Q, 灰色, 200 点)

ちょっとした算数の問題 問題へのリンク 問題概要 3 個の整数 が黒板に書かれている。 今、「3 個の整数のうち 1 つを選び、それを 2 倍した値に書き換える」という操作を 回行う。 操作後の 3 個の整数の和の最大値を求めよ。 制約 考えたこと 基本的な戦略…

AtCoder ABC 160 B - Golden Coins (8Q, 灰色, 200 点)

算数的な問題 問題へのリンク 問題概要 高橋君は金色の硬貨が好きです。自分が持っている 500 円硬貨 1 枚につき 1000、5 円硬貨 1 枚につき 5 の「嬉しさ」を得る。 高橋君が 円もっているとき、高橋君の「嬉しさ」の最大値はいくらか? 制約 考えたこと コ…

AtCoder ABC 167 B - Easy Linear Programming (8Q, 灰色, 200 点)

上手に場合分けして解いていこう。 問題へのリンク 問題概要 1 が書かれたカードが 枚、0 が書かれたカードが 枚、 −1 が書かれたカードが 枚ある。 これらのカードから、ちょうど 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最…

AtCoder ABC 172 B - Minor Change (8Q, 灰色, 200 点)

この問題は、ハミング距離と呼ばれる超重要概念! 問題へのリンク 問題概要 2 つの長さが等しい文字列 が与えられる。次の操作を繰り返して を に変更するとき、操作回数の最小値を求めよ。 操作: の 1 文字を選んで別の文字に書き換える 制約 考えたこと …

AtCoder ABC 184 B - Quizzes (8Q, 灰色, 200 点)

for 文のいい練習問題! 問題へのリンク 問題概要 高橋君は 問のクイズに答える。最初 点であり、正解すると 1 点増加する。不正解だと 1 点減少するが、不正解前に 0 点である場合は減らない。 高橋君が各問題に正解したかどうかを表す文字列 が与えられる…

AtCoder ABC 069 B - i18n (8Q, 灰色, 200 点)

文字列の長さを取得する練習! 問題へのリンク 問題概要 3 文字以上の文字列 が与えられる。この文字列 を次の規則にしたがって変換したものを出力せよ。 (先頭の文字)(先頭と末尾を除外した文字列の長さを表す数値)(末尾の文字) たとえば、"internationaliz…

AtCoder ABC 346 C - Σ (5Q, 灰色, 250 点)

set を使おう! 問題へのリンク 問題概要 長さ の整数列 と、正の整数 が与えられる。 以上 以下の整数のうち、数列 に一度も含まれないものについての総和を求めよ。 制約 考えたこと まず、 となる。 この値から「1 以上 以下の整数のうち、数列 に一度以…

AtCoder ABC 362 B - Right Triangle (6Q, 灰色, 200 点)

三平方の定理を思い出そう! 問題へのリンク 問題概要 座標平面上の 3 個の格子点 が与えられる。 これら 3 点 が直角三角形をなすかどうかを判定せよ。 制約 座標値は -1000 以上 1000 以下 考えたこと 3 点 A, B, C が直角三角形をなす条件は のいずれかを…

AtCoder ABC 364 B - Grid Walk (6Q, 灰色, 200 点)

二次元グリッド上で、マス の上下左右のマスがなんであるかを学ぶ問題! 問題へのリンク 問題概要 の二次元グリッドが与えられる。グリッドの各マスは '.'(通路)または '#'(壁)である。 はじめ高橋くんはマス にいる。これから高橋君に 回の命令がくだる…

AtCoder ABC 348 C - Colorful Beans (5Q, 灰色, 250 点)

連想配列のいい練習問題! 問題へのリンク 問題概要 種類のビーンズがあって、 種類目のビーンズはおいしさが で色が である。ビーンズは混ぜられており、色でしか区別することができない。 あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒…