灰色diff
「白い部分」が常に長方形であることから、その位置を上手に管理しよう。 問題へのリンク 問題概要 座標平面上で、2 点 を対角線とする長方形領域が与えられる。はじめ、全体が白く塗られている。この領域に対して、次の 回の操作を行なった。 【操作】 3 つ…
set の使い方を覚えよう! 問題へのリンク 問題概要 文字列 が与えられる。 の連続する部分文字列として考えられるものの個数を求めよ。 制約 考えたこと の連続する部分文字列をすべて取り出して、それを set に格納して、そのサイズを求めれば良い。 の連…
面白い探索問題 問題へのリンク 問題概要 座標平面上に 個の点がある。点 の座標は である。 各 に対して、点 の距離が最大であるような の値を求めよ(タイがある場合は が最小のもの)。 制約 考えたこと 各 に対して、別々の問題を解く。 に対して (X[i] …
まずは各文字が何回ずつ使われるかを求めよう! 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の条件を満たすかどうかを判定せよ。 【条件】 すべての に対して、 中にちょうど 回登場する文字が 0 種類または 2 種類である…
シミュレーションするか、ソートするかによって解ける典型問題! 問題へのリンク 問題概要 人の髪の長さは最初 であった。 各人の髪の長さは 1 日に 1 ずつ伸びる。 初めて髪の長さが 以上の人が 人以上となるのは何日後かを求めよ。 制約 解法 (1):シミュ…
second best を求める系の問題 問題へのリンク 問題概要 個の相異なる整数 が与えられる。 この数列のうち 2 番目に大きいものについて、それが の何番目の要素であるかを求めよ。 制約 解法 (1):max と second max を管理する 1 つ目の方法として、最大値…
問題文がやたら難読すぎる!!! 問題へのリンク 問題概要(意訳) 個の文字列 が与えられる。これに対して、次のように縦横をひっくり返して、隙間を文字 * で埋めたようなものを出力せよ。 before red orang blue yellow green gray skyblue black after b…
操作回数を最小化せよ、という問題だけど、実際には「複数ある場合は辞書順最小のものを求めよ」という部分に本質がある問題! 問題へのリンク 問題概要 文字列 は文字数が等しい。 に対して「1 文字変更する」という操作を繰り返すことで にしたい。 そのう…
こういう値を順次更新していくようなシミュレーションは慣れておきたい! 問題へのリンク 問題概要 元素 がある。 元素 を合成すると、 のときは元素 になり、 のときは元素 になる。 元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素…
else if 文と、論理演算子「&&」の練習。 問題へのリンク 問題概要 2 つの整数 が与えられる。 かつ のときは "Yes" かつ のときは "No" それ以外のときは "Invalid" を出力せよ。 考えたこと else if 文と、論理演算子「&&」を使って、次のように書ける。 #…
とても教育的な問題! ちゃんと解くには、計算量の理解が必要となる問題である。 問題へのリンク 問題概要 3 つの数列 が与えられる。これらの数列に対して、次の 個のクエリに答えよ。 【クエリ】 整数 が与えられるので、 からそれぞれ 1 個ずつ選んで和を…
「0 が連続何個続くのか」を求めるタイプの問題 問題へのリンク 問題概要 数字からなる長さ の文字列 が与えられる。 「1」「2」「3」「4」「5」「6」「7」「8」「9」「0」「00」と書かれた文字列スタンプを順に押して行って、 を作りたい。 スタンプを押す…
とても教育的で典型的なしゃくとり法の問題! 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。 が等差数列であるような組 の個数を求めよ。 制約 解法 (1):しゃくとり法 今回の問題のように、数列中で条件を満たす区間を考える問題では、しゃ…
このようなシミュレーションをサッと書けるようになりたいところ! 問題へのリンク 問題概要 横一列に 100 個の鍵盤からなるピアノがある。各鍵盤には順に と番号が振られている。 鍵盤を 回押す。 回目の鍵盤の位置は であり、 = 'L' のとき左手で押し、 = …
偶数と奇数に関する理解も問われる問題。 問題へのリンク 問題概要 2 つの整数 が与えられる。 「 を並び替えると等差数列をなす」 という条件をみたすような整数 が何通りあるか求めよ。 制約 解法 (1):数学的に解く まず、 の大小関係で場合分けして考え…
for 文の練習問題! 問題へのリンク 問題概要 HP が であるモンスターを倒したい。 種類の必殺技を順に使っていく。 種類目の必殺技はモンスターの HP を だけ減らすことができる。 モンスターの HP を 0 以下にすることができるかどうかを判定せよ。 考えた…
if 文や else if 文の練習! 問題へのリンク 問題概要 高橋君は 枚、青木君は 枚のクッキーをもっている。 高橋君は 回次の行動をとる。 自分のクッキーが残っていたら、それを 1 枚食べる 残っていなくて、青木君のクッキーが残っていたら、それを 1 枚食べ…
楽しい for 文の練習問題! 問題へのリンク 問題概要 ともに長さが である 2 つの文字列 が与えられる。 の 1 文字目、 の 1 文字目、 の 2 文字目、 の 2 文字目、... の順に文字を連結して得られる文字列を答えよ。 考えたこと 次のように考えれば良いだろ…
for 文の練習問題! 問題へのリンク 問題概要 個の整数 のうち、 以上であるものの個数を求めよ。 考えたこと for 文を用いて、 に対して、 以上であるかどうかを判定していこう。 以上:答えを表す変数を 1 増やす そうでない:何もしない というようにすれ…
文字列の易しい練習問題! 問題へのリンク 問題概要 文字列 が与えられる。 のすべての文字を 'x' で置き換えたものを出力せよ。 考えたこと まず、文字列 S の長さ N は次のように取得できる(C++)。 int N = S.size(); その先はいくつかやり方がある。 fo…
ちょっとした算数の問題 問題へのリンク 問題概要 3 個の整数 が黒板に書かれている。 今、「3 個の整数のうち 1 つを選び、それを 2 倍した値に書き換える」という操作を 回行う。 操作後の 3 個の整数の和の最大値を求めよ。 制約 考えたこと 基本的な戦略…
算数的な問題 問題へのリンク 問題概要 高橋君は金色の硬貨が好きです。自分が持っている 500 円硬貨 1 枚につき 1000、5 円硬貨 1 枚につき 5 の「嬉しさ」を得る。 高橋君が 円もっているとき、高橋君の「嬉しさ」の最大値はいくらか? 制約 考えたこと コ…
上手に場合分けして解いていこう。 問題へのリンク 問題概要 1 が書かれたカードが 枚、0 が書かれたカードが 枚、 −1 が書かれたカードが 枚ある。 これらのカードから、ちょうど 枚を選んで取るとき、取ったカードに書かれた数の和として、 ありうる値の最…
この問題は、ハミング距離と呼ばれる超重要概念! 問題へのリンク 問題概要 2 つの長さが等しい文字列 が与えられる。次の操作を繰り返して を に変更するとき、操作回数の最小値を求めよ。 操作: の 1 文字を選んで別の文字に書き換える 制約 考えたこと …
for 文のいい練習問題! 問題へのリンク 問題概要 高橋君は 問のクイズに答える。最初 点であり、正解すると 1 点増加する。不正解だと 1 点減少するが、不正解前に 0 点である場合は減らない。 高橋君が各問題に正解したかどうかを表す文字列 が与えられる…
文字列の長さを取得する練習! 問題へのリンク 問題概要 3 文字以上の文字列 が与えられる。この文字列 を次の規則にしたがって変換したものを出力せよ。 (先頭の文字)(先頭と末尾を除外した文字列の長さを表す数値)(末尾の文字) たとえば、"internationaliz…
set を使おう! 問題へのリンク 問題概要 長さ の整数列 と、正の整数 が与えられる。 以上 以下の整数のうち、数列 に一度も含まれないものについての総和を求めよ。 制約 考えたこと まず、 となる。 この値から「1 以上 以下の整数のうち、数列 に一度以…
三平方の定理を思い出そう! 問題へのリンク 問題概要 座標平面上の 3 個の格子点 が与えられる。 これら 3 点 が直角三角形をなすかどうかを判定せよ。 制約 座標値は -1000 以上 1000 以下 考えたこと 3 点 A, B, C が直角三角形をなす条件は のいずれかを…
二次元グリッド上で、マス の上下左右のマスがなんであるかを学ぶ問題! 問題へのリンク 問題概要 の二次元グリッドが与えられる。グリッドの各マスは '.'(通路)または '#'(壁)である。 はじめ高橋くんはマス にいる。これから高橋君に 回の命令がくだる…
連想配列のいい練習問題! 問題へのリンク 問題概要 種類のビーンズがあって、 種類目のビーンズはおいしさが で色が である。ビーンズは混ぜられており、色でしか区別することができない。 あなたはビーンズの色を 1 つ選び、その色のビーンズをどれか 1 粒…