ソートの練習！ 問題へのリンク 問題概要 個の整数 から 選んで総和をとる。 総和を取った値の最大値を求めよ。 制約 考えたこと 個の整数 を大きい順に並べておいて、大きい順に 個とって足せばよい。 C++ では、大きい順にソートするのは sort(l.begin(), …
完全に言われた通りに実装してしまうと、 の計算量となって TLE してしまうので、工夫しよう！ 問題へのリンク 問題概要 空の配列に対して、以下の操作を 回行う。 回目の操作では 配列の末尾に値 を挿入する 配列全体を reverse する を行う。 回操作後の配…
数学 IA でもありがちな問題！ 問題へのリンク 問題概要 匹の犬 と、 引の猿 を一列に並べる。 犬同士・猿同士がそれぞれ隣り合わないように並べる方法の数を 1000000007 で割った余りを求めよ。 制約 考えたこと 実は、 や の場合は、条件を満たすように並…
ちょっと発想が必要な問題。 問題へのリンク 問題概要 個の家が並んでいる。 個目の家は座標 にある。このすべての家にプレゼントを配る。 好きな場所から開始し好きな場所で終了することができるとき、最小の移動距離を求めよ。 制約 考えたこと 下の図のよ…
面白い問題。最近はこういうの、あまり見ないかもしれない。 問題へのリンク 問題概要 個の正の整数 が与えられる。 これらからいくつか選んで総和をとる。ただし、その値が 10 の倍数である場合には、その値は 0 になってしまう。 この値の最大値を求めよ。…
とても教育的な易しい問題！ 問題へのリンク 問題概要 英小文字からなる文字列 が与えられる。 の文字がすべて互いに相異なるかどうかを判定せよ。 解法 (1)：多重 for 文 最も素朴な方法は、 から 2 文字を選ぶ方法をすべて試して、「それらが異なっている…
こういう処理に慣れておくと、将来的に「番兵法」などにも使える。 問題へのリンク 問題概要 縦 ピクセル、横 ピクセルの画像があります。 各ピクセルは英小文字で表される。 この画像の周囲 1 ピクセルを # で囲んだものを出力してください。 制約 考えたこ…
「グラフ」の基礎問題！ グラフを知らなくても解ける。 問題へのリンク 問題概要 個の都市 () があり、 本の道路がある。 番目の道路は、都市 と都市 を結んでいる。同じ 2 つの都市を結ぶ道路は、1 本とは限らない。 各都市から他の都市に向けて、何本の道…
"142857" はエニアグラムやっていたら毎日目にする。エニアグラムは競プロの役に立つ！ 問題へのリンク 問題概要（output only） 正整数 と文字列 の組であって以下の条件を全て満たすものを 1 つ挙げよ。 は 0 から 9 までの数字からなる長さ 5000 以下の文…
これは比較的易しめだった。探索するだけ！ 問題へのリンク 問題概要 下図のように「計算過程」を表す二次元グリッドが与えられる。文字 . 以外の文字は木をなしていて、葉には数値がかかれている。演算子 +、-、*、/ はそれぞれ「大きい方から小さい方に演…
すごく悩んだけど、なんとか解けた！ 問題へのリンク（仮） 問題概要 次の図のように、木を、文字 (、)、1 からなる文字列で表す（異なる木が同じ文字列になることもある）。文字列の生成規則は次のように表される。 E ::= ‘1’ | ‘(’ E E ‘)’ 詳細は問題文を…
面白い問題だった。 問題へのリンク 問題概要 下の図のような木を「ユ木」と呼ぶ（正式な定義は問題文参照）。 頂点数 の木が与えられ、いくつかの頂点を削除して「ユ木」にしたい。削除する頂点の個数の最小値を求めよ。 制約 考えたこと 与えられた木にお…
難しくはないけど、重たい！ 順序付き set の練習問題。 問題へのリンク 問題概要 制約 考えたこと 順序付き set を上手く使う問題。この問題では、次の操作を実現したくなる。ここで、集合 は、初期状態では問題文で与えられる 個の家の座標を格納すること…
全探索思考に慣れてさえいれば、 の解法ならすぐに思いつく。少し工夫して、 の解法になる！ 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の部分数列 であって が等差数列である である という条件を満たすものを考える。それらの数列の最大長…
二次元グリッド上のシミュレーション問題！ 問題へのリンク 問題概要 のグリッドが与えられる。各マスは '.'：通路マス '#'：壁マス '@'：アイテムマス のいずれかである。最初、マス にいる。 今、グリッド上で文字列 に示す移動をする（U, D, L, R のいず…
場合分けを頑張ろう！ 問題へのリンク 問題概要 3 つの整数 をいくつかのグループに分けて、各グループに含まれる整数の総和を等しくできるかを判定せよ。 考えたこと 次の 2 つの場合が考えられる。 2 つのグループに分けて、総和を等しくする 3 つのグルー…
面白かった！ 一見 MST の問題に見えるけど、主客転倒すると Dijkstra だった。 問題へのリンク（仮） 問題概要 頂点数 、辺数 の連結な単純無向グラフが与えられる。頂点 には重み がついていて、辺 には重み がついている。このグラフの全域木のコストを次…
これ面白かった！ ABC-E で出題されて水色 Diff などがあり得そうな雰囲気。 問題へのリンク（仮） 問題概要 正の整数 が与えられる。 以上 以下の整数のうち、popcount が最小のものを求めよ。複数ある場合は、そのうちの最小の整数を求めよ。 制約 考えた…
制約的に でも通るが、スタックを用いて でも解ける！ 問題へのリンク（仮） 問題概要 マスからなるマス目があり、最初各マスには 0 が書かれている。このマス目に対して、以下の操作を行う。 正の整数値 と、連続するいくつかのマスを選ぶ（ただし、どのマ…
面白かった！ 解説 AC した！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられる。このグラフの辺の順列であって、次の条件を満たすものを 1 つ求めよ（なければ -1 を出力せよ）。 【条件】 頂点数 、辺数 のグラフに対して、上記の順序…
面白かった！ カタラン数的なものが登場する。 問題へのリンク 問題概要 制約 考えたこと まずすぐにわかったことは、 の中に、1 が 2 個以上あってはダメ の中に、1 が末尾以外の場所にあってはダメ ということだった。そうすると、 は次のいずれかの形にな…
B 問題としては易しめ。 問題へのリンク 問題概要 レーティングが の人が 回コンテストに参加した。 回目のコンテストでは、Div. のコンテストに参加して、もしレーティング更新対象者であれば、レーティングは だけ加算される（負値もありうる）。 ARC Div.…
これ 150 点なのは解釈一致だし、難しいと思うけど、Difficulty が 19 とすごく低いのが驚き！ 問題へのリンク 問題概要 今、時刻 0 で水は 0 L たまっている。 これから時刻 にそれぞれ水が L 注がれる。 なお、水が 1 L 以上あるとき、時刻が 1 経過するご…
for 文の基本問題 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の各文字について、文字 でないものをすべて文字 に置き換えたものを出力せよ。 考えたこと for 文の練習問題といえる。 for 文を用いて、 の各文字について、 であるかどうかを判定…
近年の B 問題では最も簡単かもしれない。 問題へのリンク 問題概要 文字 .、@ からなる長さ の文字列 が与えられる。後ろから順に 個の @ を . に変えたものを出力せよ。 考えたこと for 文を用いて、添字を という降順に回していき、 S[i] == '@' のとき …
ちゃんと整理するのは大変だ。落ち着いて整理しよう。 問題へのリンク 問題概要 長さ の文字列 が与えられる。 が "11/22 文字列" であるかどうかを判定せよ。 11/22 文字列であるとは、文字 1, /, 2 がこの順に並んでいて、1 と 2 の個数が等しいものをいう…
問題文がややこしい書き方をしているけど、「要するにこういうこと！」という言い換えができるといい。 問題へのリンク 問題概要 文字 ., @ からなる長さ の文字列 が与えられる。@ を左から順に 個だけ . に書き換える。 書き換えたあとの文字列に含まれる…
という制約がいかにも怪しい！ 問題へのリンク 問題概要 1 以上 20 以下の整数からなる、長さ の数列 が与えられる。 この数列の部分列 (連続でなくてよい) であって、任意の整数について、その部分列に含まれる個数が 0 個または 2 個であるものを考える。 …
集合型を学ぼう！ 問題へのリンク 問題概要 個の文字列 がこの順に与えられる。 初出の文字列に対して、その添字を出力せよ。 制約 解説 0-indexed で考えます。つまり、文字列を とします（出力するときには 1 を足します）。 まずは計算量のことを考えずに…
集計処理した上で、再度大きい順にソートする問題 問題へのリンク 問題概要 個の文字列 が与えられる。 この列に一回以上出現する単語を、その出現回数の多い順に並べたとき 番目の単語を出力せよ（一意に決まらない場合は "ambiguous" と出力せよ）。 制約 …
