C 問題としてはかなり難しいですね。 問題へのリンク 問題概要（一部意訳） 小さい飴は 1 個 円、大きい飴は 1 個 円である（ である）。 人がいて、人 は、飴を合わせて 個買おうとしている。ただし、 人全員の購入金額がちょうどぴったり一致するようにし…

面白かった！ 問題へのリンク editorials 問題概要 3 つの文字 B, Y, K からなる長さ の文字列 が与えられる。 この文字列をいくつかの区間に分割する。各区間について、 ランレングス圧縮すると、B -> Y -> K の順になるもの：区間の長さだけスコアを獲得 …

人生で初めて「マージテク」を学ぶなら、この問題！！！ 問題へのリンク 問題概要 箱 がある。箱 には最初色 のボールが入っている。以下の 回のクエリに答えよ。 整数 が与えられる 箱 のボールをすべて箱 に移動させる その後、箱 に入っているボールの色…

for 文を使うと少し楽。 問題へのリンク 問題概要 8 種類の方角を表す文字列 が与えられる。次のいずれかである。 北：N 東：E 西：W 南：S 北東：NE 北西：NW 南東：SE 南西：SW 与えられた文字列の反対の方角を表す文字列を出力せよ。 解法 8 通りの場合を…

種類数に関する面白い問題！ 問題へのリンク 問題概要 2 つの文字列 は、 である を左右反転してできる文字列 について、 である といういずれかの条件を満たすとき、似ているとみなす。 与えられた 個の文字列 について、似ている文字列は同一視することに…

バケットの練習を兼ねた、インタラクティブ問題！ 問題へのリンク 問題概要（インタラクティブ） 最初に、正の整数 が与えられて、ゲームをする。あなたは高橋君で先手である。相手は青木君で後手である。 交互に、1 以上 以下の整数を言っていく。ただし、…

「変数を固定する考え方」と「set の活用」を組み合わせる練習問題！ 問題へのリンク 問題概要 整数 と、 個の整数 が与えられる。 を満たす [tex i, j] ( でもよい) が存在するかを判定せよ。 制約 考えたこと この問題のように、 という 2 つの変数を考え…

set の練習問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 重複を除くと何種類の文字列があるでしょうか。 制約 文字列長さは 10 以下 考えたこと 重複を除外したいとなったら、集合型（C++ ならば set 型）が使える！ 具体的には、set<string> 型の変数</string>…

set の練習問題！ 問題へのリンク 問題概要 個の文字列 と、 個の文字列 が与えられる。 について、 の中に と一致するものがあるかどうかを判定せよ。 制約 各文字列の長さは 10 以下 考えたこと set 型のよい練習問題。 を格納する集合（C++ であれば set<string> </string>…

よくある priority queue の使い方！ 問題へのリンク 問題概要 個の正の整数 から重複を許して何個か選んだ総和として考えられる値のうち、小さい方から 番目の値を求めよ。 制約 考えたこと この手の priority queue の使い方はよくある。「小さい順に 個を…

順列を題材とした面白い問題。トポロジカルソートの問題でもある。 問題へのリンク 問題概要 の順列であって、以下の 個の条件を満たすもののうち、辞書順最小のものを求めよ。 【 番目の条件】 は よりも先に来る 制約 考えたこと グラフの問題として考えて…

面白かった。priority queue と、「全体に反映させる値を別にもつ」テクニックを学べる問題。 問題へのリンク 問題概要 はじめ、何も入っていない袋がある。次の 回のクエリに答えよ。 クエリタイプ 1：袋に、 と書かれたボールを入れる クエリタイプ 2：袋…

いろんな解法がある。ここでは、ソートで解いてみよう！ 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。 各数列から要素 を選んだときの差 の最小値を求めよ。 制約 考えたこと 本当にいろいろな解き方がある。その中でも易しいのは、…

Greedy の基本でもある。 問題へのリンク 問題概要 駅 があって、駅 から駅 へと、時刻 以降、 秒ごとに発車する列車があって、移動に 秒かかる。他の駅間を移動する列車はない。また、 は の倍数であることが保証される。 各 に対して、駅 を時刻 0 に出発…

たまたま作れた！！！ 個人的傑作の自作構築問題。 問題へのリンク editorials 問題概要 正の整数 が与えられる。 のマス目に 1 以上 以下の整数を入れる方法であって、次の条件を満たすものを構築せよ。 【条件】 について、 行目または 列目のマスは 個あ…

if 文の練習問題 問題へのリンク 問題概要 ビ太郎は JOI 鉄道に乗って旅行をする。JOI 鉄道の運賃ははじめの km までは 1 km あたり 円で、それ以降の運賃は 1 km あたり 円で計算される。 km 乗車するとき、運賃はいくらになるか出力せよ。 解法 距離が 以…

中1レベルの数学の素養が必要になる。文字式の扱いに慣れていれば解けるはず！ 問題へのリンク 問題概要 ビ太郎は 秒間，秒速 m で走った。 何 m 走ったか出力せよ。 解法 答えは、数式で書くと となる。 これをプログラムで書いてみよう。整数値 を整数型変…

にょぐた君と一緒に考察した。面白かった。公式解説は多面体で考えているけど、ここでは LP 双対で解いてみる。 問題へのリンク commentary 問題概要 種類の水溶液がある。水溶液 は、 として、 水溶液全体の重さが g 1 g あたりの溶質の重さが g 以上 g 以…

小谷の蟻の問題！ 問題へのリンク 問題概要 の直方体の表面上で、1 つの頂点から最も遠い点への距離を求めよ。 下の図は 1 x 1 x 2 の例であり、とくに「小谷の蟻の問題」と呼ばれている。 制約 考えたこと 1 x 1 x 2 のときに、直方体の反対側の頂点が答え…

初歩的な Greedy の問題と言える。 問題へのリンク 問題概要 以上 以下の整数からなる数列 であって、 は で割り切れる という条件を満たすものを考える。そのような数列の長さの最大値を求めよ。 制約 考えたこと 基本的には、なるべく小さい値でスタートし…

整数の「各桁の和」を求める問題 問題へのリンク 問題概要 1 以上 以下の整数のうち、10 進法での各桁の和が 以上 以下であるものの総和を求めてください。 考えたこと まず、整数 の各桁の和を求める方法を確認しておこう。それについては、この記事に書い…

整数値の各桁の値の和を求める方法を確認しておこう！ 問題へのリンク 問題概要 整数 を十進法で表したときの各桁の数字の和が、 を割り切るとき、 をハーシャッド数という。 与えられた整数 がハーシャッド数であるかどうかを判定せよ。 解法 整数 の各桁の…

異常コーナーケース祭りのやばい問題だった 問題へのリンク 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。このグラフの頂点 にそれぞれ駒 が置いてある。次の操作を繰り返す。 駒 のうちの一方を選ぶ 選んだ駒を隣接する頂点のいずれかに動…

バケットを用いた集計処理や、Greedy の練習！ 問題へのリンク 問題概要 個の整数 が与えられる。いくつかの整数を他の好きな整数に書き換えることで、数列に含まれる整数値の種類数が 以下となるようにしたい。 書き換える整数の個数の最小値を求めよ。 制…

ビット全探索の練習問題。少し問題内容を理解するのに手こずるかもしれない。 問題へのリンク 問題概要 すでに 個の店が出店している商店街で、新たに店を開こうとしている。 どの店についても 10 個の時間帯があり、それぞれについて open・close を選ぶこ…

全探索しよう！ こういう問題で、ただちに「全探索しよう」と思えるかどうかがすごく大事！ 問題へのリンク 問題概要 長さの等しい文字列 が与えられる。 に対して、次の操作を高々 1 回実行することで、 に一致させられるかどうかを判定せよ。 (操作) の隣…

A 問題としては、少し難しめな感じ。 問題へのリンク 問題概要 1, 2, 3, 4, 5 を並び替えて得られる数列 が与えられる。この数列に対して 「隣接する様子を swap する」 という操作をちょうど 1 回だけ行って、単調増加にできるかどうかを判定せよ。 考えた…

ずっと、「2 個分開いているかっこについて、1 個閉じてから、また 1 個開く」というパターンを見落として、WA 12 個がとれなかった！！ 問題へのリンク 問題概要 1 - 20 - 13 + 14 - 5 のような、 個の正の整数を「+」「-」で連結した計算式が与えられる。…

ABC-C の最易候補！ ビット全探索でもいいが、8 通りだけなので if 文の羅列でも OK。 問題へのリンク 問題概要 4 つの整数 が与えられる。 □ □ □ = 7 となるように、□ に + または - を入れよ。 制約 考えたこと □ は 3 個ある。それぞれに「＋」と「－」の…

面白かった！ 問題へのリンク 問題概要 英小文字および文字 '?' からなる文字列 が与えられる。 の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。 (条件) 文字列 を連続する部分文字列として含む 制約 考え…