全探索思考に慣れてさえいれば、 の解法ならすぐに思いつく。少し工夫して、 の解法になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の部分数列 であって が等差数列である である という条件を満たすものを考える。それらの数列の最大長…

これ実は「アルファベット文字の変換テーブルを愚直に作る」という素朴な方法が解けるけど、意外と盲点になりそうだ！ 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。次の 回の操作を実行後の文字列を出力せよ。 【操作】 文字 …

実験していくうちにシンプルな構造がわかった。 問題へのリンク 問題概要 英文字からなる長さ の文字列 が与えられる。この文字列に対して、次の操作を 回行ってできる文字列を考える。 【操作】 文字列 に対して、英小文字と英大文字を入れ替えてできる文字…

座標平面上の 本の線分の順序を探索して、さらに各線分のどちら側からどちら側になぞるかも探索する。 問題へのリンク 問題概要 座標平面上に 本の線分がある。 本目の線分は、座標 の点と座標 の点を結んでいる。 最初、原点にレーザーがある。レーザーは印…

差分のみ更新していく系の典型問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。次の 回のクエリに答えよ。 【クエリ】 整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。 制約 考えたこと…

操作によってできるものの個数を数え上げる系の問題の最も基本的な問題！ 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の操作を 1 回行ってできる文字列が何種類あるかを求めよ。 を満たす を好きなように選んで、 の 文字目と 文字目を swap …

実はとても単純な解法に落とし込めるのだけど、発想がちょっと難しい 問題へのリンク 問題概要 AtCoder 王国の 1 週間は 日あり、最初の 日が休日、後半の 日が平日である。 高橋君は 日分の予定があり、それぞれ 日目に予定がある。 これらの予定日がすべて…

とても重たくて大変な問題。いろんな整理の仕方があると思う。 問題へのリンク 問題概要 下図のように、座標平面が 1 x 2 の長方形に区切られている。 座標 から座標 へと至るまでに、通過する必要のある長方形の境界の個数の最小値を求めよ。 制約 考えたこ…

面白かった！ 問題へのリンク 問題概要 整数 が与えられる。 整数 の十進法表記を 個 concat してできる整数を 998244353 で割った余りを求めよ。 制約 考えたこと まず、整数 が 桁だとしよう！ このとき、求めたい値は次のように表現できる。 よって、 と…

はじめての「〜が 以下になる瞬間」を捉えるというシミュレーション問題。 問題へのリンク 問題概要 高橋君は 種類の薬を処方された。薬 は、 日目まで、毎日 錠ずつ飲むこととなる。 1 日に飲む錠剤の個数がはじめて 錠以下になる日を求めよ。 制約 考えた…

いろんな方法がありそう。こういうのを工夫して解き切る腕力はいつだって大事になる。 問題へのリンク 問題概要 個のペア値 が与えられる。 ある について かつ を満たすとき、ペア値 を削除する操作を繰り返す。 最後に残るカードの集合を求めよ。 制約 考…

「差分更新」の良い練習問題！ 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…

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