Suffix Array の典型問題 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列として登場しうる文字列をすべて考える。重複は除外する。これらの文字列の長さの総和を求めよ。 制約 考えたこと 次の問題とほと…

競プロ典型90問の問題 001 の類題。「最大値の最小化」をする二分探索の典型問題ですね。 問題へのリンク 問題概要 二次元平面上に 個の円が与えられます。またそれらとは別に 個の点が与えられます。円同士は互いに交わることはなく、点が円に包含されるこ…

面白かった！セグ木を使ったけど、区間を複数個にする必要がないことから、しゃくとり法で線形でできるね！ 問題へのリンク 問題概要 の順列 が与えられる。以下の操作を繰り返すことで、単調増加となるようにしたい。 区間 の要素をすべて削除する (コスト…

Grundy 数がフラクタルっぽい構造を示していた！ 問題へのリンク 問題概要 個の石の山がある。各山には 個の石がある。先手と後手が交互に以下の操作を繰り返す。 山を一つ選ぶ。その山には石が 個あるとする。 その山の石の個数が 個または 個となるように…

なぜか埋め込みにこだわってしまい、本番 AC できなかった... 問題へのリンク 問題概要 整数 が与えられる。以下の条件を満たす最大の正の整数 を求めよ (存在しない場合は -1、無限個存在する場合は -2)。 確率 % で表が出るサイコロを 回振るとする 表が出…

昔はこういうの苦手だったけど、今ならできる！ 問題へのリンク 問題概要 階建ての建物があって、後述するエレベータの建設をなくしては、下への移動は自由にできるが、上への移動は自由にできない。 個のエレベータ建設計画がある。 番目の計画では、 日目…

とてもよくある区間分割していくタイプの DP 問題へのリンク 問題概要 個の正の整数 がこの順に一列に並んでいる。これらの整数を 個以下の区間に分割したい。 このとき、「各区間の値の平均値の総和」として考えられる最小値を求めよ。 制約 考えたこと 「…

数学っぽい問題好き！！！ 問題へのリンク editorials 問題概要 個のカフェオレがある。 番目のカフェオレは、コーヒーが mg、ミルクが mg だけ入っている (ともに整数)。 これらを混ぜて作れるカフェオレのうち、コーヒー量 とミルク量が がともに正の整数…

半分全列挙 + Binary Trie！！ あるいは、Binary Trie 自体を意識しなくても、上の位から順に桁 DP 的発想で考えていると、それが自然に Binary Trie 上の探索そのものとみなせる！ すごくいい Binary Trie の経験になった！！ 問題へのリンク editorial 問…

|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった！ 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …

初手実験に走れたのは割とよかった。そういう戦い方もできるようになってきた。 問題へのリンク editorial 問題概要 正の整数 を 先頭に 0 を含まないように 進数表現したときの各位の数を、小さい位から順に要素とした数列を とする。次のような感じ。 正の…

最初与えられる文字列が高橋くんの手だと勘違いして、サンプル 2 が無限にわからないとなっていました。 clar でお騒がせいたしました...ありがとうございます。 問題へのリンク editorial 問題概要 高橋くんと青木くんがジャンケンを 回行う。青木くんの出…

ABC C にありそうな教育的問題！ 問題へのリンク editorial 問題概要 正の整数 が与えられる。 かつ を満たすすべての整数組 についての の総和を 1000000007 で割ったあまりを求めよ。 制約 (テストケース数) 考えたこと 結局、 を計算すればよい。それぞれ…

二部マッチングの復元にてこずって、間に合わなかった... 問題へのリンク editorial 問題概要 個の正の整数 の部分集合であって、以下の条件を満たすもののうち、要素数が最大のものを 1 つ求めよ。 どの要素も 6 で割ったあまりが 1 ではない どの要素も約…

これの原案だった！！ 「対称戦略」が印象的なゲームの問題を作ろうとして作った 問題へのリンク editorial 問題概要 1 × 1 × 1 の立方体を の直方体形状に積み上げたものがある。これを使って 2 人でゲームする。 交互に、直方体のある面のあるマスを選んで…

ガウス整数が使える問題と聞いて！！！ 問題へのリンク editorial 問題概要 二次元平面上に 個の格子点 がある。これに最小個数の格子点を追加することで、格子点全体が「正方形グリッド」の模様を形作るようにしたい。追加すべき格子点の個数を求めよ。 制…

信じる心が大切ですね 問題へのリンク 問題概要 組の文字列 が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 側と 側とをそれぞれ連結した文字列 ができる。 このとき、 が の部分文字列 (連続でなくてよい) とすることができるかどうかを判…

パズルだ！！ 問題へのリンク 問題概要 正の整数 が与えられる。 個の正の整数 を用意して、 がそれぞれ 個ずつあるとして それらの足し引きによって までの整数がすべて作れる という条件を満たすような最小の を求めよ。 制約 考えたこと の場合は結構な有…

今日の会社のバチャでやった。面白かった。 問題へのリンク 問題概要 のグリッドに 'A', 'B', 'C' の各文字を書き込む。以下の条件を満たすものを一つ求めよ。 以下のような に対して である: 隣接する 2 マスの組であって一方が 'A' で他方が 'B' であるも…

二乗の木 DP のいい練習問題！！！！！ ついでに DP で最適化したい対象を入れ替えるタイプの問題でもある。そのようなタイプとして難しい問題としては、以下がある。 drken1215.hatenablog.com 問題へのリンク 問題概要 頂点の重みつきの根つき木が与えられ…

これ好き！！！ しばらく、CPSCO の良さげな問題を解説するターンをやってみたい。 問題へのリンク 問題概要 石の山が 2 個あって、それぞれ初期状態では 個積まれている。ここから先手と後手が交互に 残っている石の山から 1 つ選び、その石の個数を とする…

燃やす埋めるを本気で整理する！！！ すごく面白い問題だった！！！ 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... .......... は下のよ…

楽しいけど重くて、重いけど楽しい 問題へのリンク 問題概要 要素から成る数列 が与えられる。 個から 2 個選んでできる 通りのペア のうち、以下の条件を満たすものを数え上げよ。 容量が の容器を用意して、以下の操作によって水の量 を汲み取れる 操作 1:…

RUPC 2018 の思い出。桁 DP なん。 問題へのリンク 問題概要 ごちうさ数とは、10 進法表記において「5?13」を含む正の整数のことである。? は 0〜9 のいずれでもよい。 以下の正の整数のうち、ごちうさ数が何個あるかを求めよ。 制約 解法 桁 DP。 一目、51?…