2024-01-01から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" と出力せよ）。 制約 …
ちょっと工夫が必要な感じ 問題へのリンク 問題概要 長さ 正整数列 と、正の整数 が与えられる。 数列の区間であって、総和を で割った余りと、区間内に含まれる要素の個数とが等しいものの個数を求めよ。 制約 考えたこと 結構ややこしい。落ち着いて条件を…
上手に式変形しよう！ 問題へのリンク 問題概要 正の整数からなるサイズ の数列 が与えられる。次の条件を満たす組 の個数を求めよ。 制約 考えたこと 条件が不思議だ。普通は よりも の方が大きいことが多いのに、 となる条件を問うとは。 さて、この手の数…
条件を上手に言い換えよう！ 問題へのリンク 問題概要 個の整数 が与えられる。 が平方数 という条件を満たすような組 の個数を求めよ。 制約 考えたこと これは「条件の言い換え」を頑張る問題。「 が平方数」という条件を扱いやすいように言い換えよう。こ…
「区間の値の和」を見たら、累積和をとろう！！ 問題へのリンク 問題概要 数列 と整数 が与えられる。 数列の連続する区間であって、その総和が に一致するものが何個あるかを求めよ。 制約 考えたこと 0-indexed で考える。 数列 の累積和を としよう。この…
for 文の練習問題 問題へのリンク 問題概要 長さの等しい 2 つの文字列 が与えられる。 に含まれる各文字 '@' について、'a', 't', 'c', 'o', 'd', 'e', 'r' のいずれかに置き変えることで、 が一致するようにできるかを判定せよ。 制約 [tex 1 \le |S| = |T…
すごく面白い問題！ 問題へのリンク 問題概要 個の文字列 が与えられる。 これらの文字列から異なる 2 つの文字列を選ぶ方法であって、それらの文字列が互いにアナグラムとなっているものの個数を求めよ。 制約 考えたこと まずは、問題の条件をわかりやすく…
連想配列の良い練習問題！ 問題へのリンク 問題概要 正の整数からなる数列が良い数列であるとは、数列に含まれる任意の整数値 について、数列中に がちょうど 個含まれていることをいう。 与えられた数列 に対して、いくつかの要素を削除することで、よい数…
素朴な map の練習問題 問題へのリンク 問題概要 りんごさんは 個の問題案を持っており、 個目の問題案の難易度は である。 ここから、配点が であるような 問からなる問題セットを作ることは可能か？ 制約 考えたこと 連想配列 (C++ ならば map) の練習問題…
