AtCoder200点
各文字がどこにあるのかを求めると楽になる。 問題へのリンク 問題概要 'A' から 'Z' までの文字を 1 つずつ含む文字列 が与えられる。 内部での 'A' から 'B' への移動距離 (index の差分) 'B' から 'C' への移動距離 (index の差分) 'C' から 'D' への移動…
mod を練習できる問題！ 問題へのリンク 問題概要 正の整数 が与えられる。 を 1000000007 で割った余りを求めよ。 考えたこと まず「1000000007 で割った余り」といったものを考えるための、基本的な知見を次の記事にまとめた。 qiita.com 結論として、 を …
少し実装が重たい全探索問題！ 問題へのリンク 問題概要 の白黒グリッド と、 の白黒グリッド が与えられる ()。 グリッド のパターンがグリッド の中に含まれるかどうかを判定せよ。 制約 考えたこと グリッド のすべてのマス について、次の判定をしていけ…
三進法をテーマにした問題！ 問題へのリンク 問題概要 正の整数 が与えられる。以下の条件を全て満たす正の整数 と非負整数列 を 1 つ求めよ。 制約 考えたこと 問題文が一見わかりにくいかもしれない。こういうときは具体的にやってみよう。 たとえば のと…
制約が なのがびっくり。素直に連続部分列をすべて調べると TLE してしまう。そのような問題は B 問題で登場するイメージがないので、現代なら などとしそうだ。 問題へのリンク 問題概要 文字列 の連続する部分文字列であって、先頭が 'A' で末尾が 'Z' で…
バケットを活用する練習問題！ 問題へのリンク 問題概要 AtCoder 王国には 家がある。どこかの家で順に 人の赤子が生まれた。 人目の赤子は家 で生まれ、性別は （'M' または 'F'）であった。 各赤子が長男であるかどうかを判定せよ。 制約 考えたこと 人目…
for 文を回す処理を 回やる問題 問題へのリンク 問題概要 個の整数からなる数列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 が与えられる。 を に変更したときの、 の値を答えよ。（なお、クエリごとに変更は引き継がれない。） 考えたこと …
「白い部分」が常に長方形であることから、その位置を上手に管理しよう。 問題へのリンク 問題概要 座標平面上で、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…
こういう値を順次更新していくようなシミュレーションは慣れておきたい！ 問題へのリンク 問題概要 元素 がある。 元素 を合成すると、 のときは元素 になり、 のときは元素 になる。 元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素…
愚直シミュレーション問題！ 問題へのリンク 問題概要 A さん、B さん、C さんの 3 人が以下のようなカードゲームをプレイしています。 最初、3 人はそれぞれ 'a', 'b', 'c' いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた…
このようなシミュレーションをサッと書けるようになりたいところ！ 問題へのリンク 問題概要 横一列に 100 個の鍵盤からなるピアノがある。各鍵盤には順に と番号が振られている。 鍵盤を 回押す。 回目の鍵盤の位置は であり、 = 'L' のとき左手で押し、 = …
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…
三平方の定理を思い出そう！ 問題へのリンク 問題概要 座標平面上の 3 個の格子点 が与えられる。 これら 3 点 が直角三角形をなすかどうかを判定せよ。 制約 座標値は -1000 以上 1000 以下 考えたこと 3 点 A, B, C が直角三角形をなす条件は のいずれかを…
