ABC-B
近年の B 問題では最も簡単かもしれない。 問題へのリンク 問題概要 文字 .、@ からなる長さ の文字列 が与えられる。後ろから順に 個の @ を . に変えたものを出力せよ。 考えたこと for 文を用いて、添字を という降順に回していき、 S[i] == '@' のとき …
for 文の練習問題 問題へのリンク 問題概要 長さの等しい 2 つの文字列 が与えられる。 に含まれる各文字 '@' について、'a', 't', 'c', 'o', 'd', 'e', 'r' のいずれかに置き変えることで、 が一致するようにできるかを判定せよ。 制約 [tex 1 \le |S| = |T…
初歩的な構文解析問題 問題へのリンク 問題概要 "|---|-|----|-|-----|" のような、文字 '-' を文字 '|' で separate された文字列 が与えられる。 各 '-' 区間の '-' の個数を順に出力せよ。 制約 考えたこと ここでは for 文で解いてみよう。次の変数を管…
チェスを題材とした問題 問題へのリンク 問題概要 8 x 8 のチェス盤のいくつかのマスにルーク（上下左右にどこまでも行く）が置かれている。 これらのどのルークにも取られないマスの個数を求めよ。 考えたこと 8 x 8 の盤面に対応する二次元配列を用意して…
ランレングス圧縮！ 問題へのリンク 問題概要 文字 'O', 'X' からなる長さ の文字列 が与えられる。 「'O' のみからなる連続 個の文字をすべて 'X' に書き換える」という操作を最大で何回行えるか？ 制約 考えたこと ランレングス圧縮が有効な問題。ランレン…
この問題は、for 文でも解けるし、map でも解ける。ここでは map で解いてみよう。 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 これに対して文字列を考えて、その文字列に対するスコアは ( に含まれている分の個数) - ( に含まれて…
ちょっと整理が大変な複雑な問題。 問題へのリンク 問題概要 ルーレットによって 0 から 36 までのいずれかの整数が出される。 人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。 実際に出た整数は であった。 に賭けていた人のうち、賭けた整…
演算子「%」を上手に使う系の数学問題。 問題へのリンク 問題概要 種類のゴミがある。ゴミ は、 で割って 余る日に捨てることができる。 次の 個のクエリに答えよ。 【クエリ】 ゴミ を、 日目以降に捨てたい。最短で捨てることのできる日を答えよ。 制約 考…
ちょっとした算数・数学の問題！ 問題へのリンク 問題概要 考えたこと A, B, C, D, E をそれぞれ 0, 1, 2, 3, 4 と対応させよう（0 始まりにするのがコツ）。このとき、対角線の長さは、対角線の両端に対応する数値の差で表すことができる。 たとえば、線分 …
探索アプローチでも解けるし、整数論的考察で解くこともできる。 問題へのリンク 問題概要 の倍数であって正の整数であるものをいくつか用意する。 その総和を で割った余りが となることはありうるか？ 制約 考えたこと まず、「いくつかの正の の倍数を足…
巨大な整数値の大小比較の問題 問題へのリンク 問題概要 2 つの正の整数 （101 桁以下）が与えられるので、その大小比較をせよ。 考えたこと は 100 桁にも及ぶことがあるので、long long 型などで受け取ることもできない。そこで、string 型で受け取ろう。…
2 つの文字列の長さが等しかったり、異なったりするのが少しイヤだが、難しくはない。 問題へのリンク 問題概要 文字列 が与えられる。 または である。 の各文字を先頭から順に交互にとって得られる文字列を出力せよ。 考えたこと まずは、 に対して、 と …
多重 for 文の練習問題！ 問題へのリンク 問題概要 二次元平面上に 人の学生と、 個のチェックポイントがある。学生 は座標 にいて、チェックポイント は座標 にいる。 各学生について、その学生からマンハッタン距離が最も近いチェックポイントを求めよ (タ…
文字列 のサイズが異なる場合の処理などがちょっとだけややこしい。 問題へのリンク 問題概要 文字列 が与えられる。次のいずれかの条件を満たす最小の を求めよ。ただし、 である場合は 0 と答えよ。 かつ であって、 である ] かつ である ] かつ である …
ちょっと幾何チックな問題 問題へのリンク 問題概要 考えたこと この手の問題では、 の大小関係が定まっていると考えやすい。そして、 でも でも、どちらでも一般性を失わないので、 として考えよう。 このとき、次のように整理できる。 ならば：すでに連結…
各文字がどこにあるのかを求めると楽になる。 問題へのリンク 問題概要 '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…
