ソート
競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。 1. 座標圧縮とは 数列 が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。 たとえば A = (8, 100…
二分探索法の教育的典型問題ですね！！ 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…
ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…
個のものから 個除いたものを考えるのは色々定石がある！ 問題へのリンク 問題概要 個の整数 が与えられる。 各 に対して、 を除外した 個の整数の最大値を求めよ。 制約 解法 (1)：アドホックに考える まずは素朴な解法を考えてみる。たとえば とかだったと…
まさに「座標圧縮」をしてください、という問題！ ジャッジページへのリンク 問題文へのリンク 問題概要 個の整数 が与えられる。それぞれについて、「大きい順に何番目か」を求めよ。 たとえば に対しては、答えは となる。 制約 考えたこと 今回の問題のよ…
いろんな方法が考えられそう！ 問題へのリンク 問題概要 個の整数 が与えられる。 を満たすすべての の組に対する の総和を求めよ。 制約 考えたこと 絶対値のままだと厄介。ちょっと工夫する。まず、数列 の並びを入れ替えたとしても答えが変わらないことに…
「転倒数 = N-1 で Yes とする」という嘘解法が大量に通ったらしい 問題へのリンク 問題概要 の順列 が与えられる。 と を swap する と を swap する ... と を swap する という 種類の操作を、それぞれちょうど 1 回ずつ行う必要がある。その結果がソート…
すごい面白い！！ 問題へのリンク 問題概要 体の敵がいて、敵に付随するスコアはそれぞれ で与えられる (負数になることもある)。 これらの敵を順に倒していきたい。Boss Score, Total Score と呼ばれる値が初期状態ではともに 0 となる。敵 を倒すとき、次…
二分探索でやればよさそう。本当は でもできるのかも。 問題へのリンク 問題概要 正の整数 が与えられる。 整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。 選んだ整数はいくつかの…
Greedy を考察して、さらに左右から累積和を求める！結構難しい！ 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数…
めちゃくちゃ面白かった 問題へのリンク 問題概要 この問題では、"(", ")", "[", "]" からなる文字列を考える。 文字列 は，以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。 は空文字列である ある良い括弧列 が存在し、"(", , ")" をこの順に連結す…
コーナーケースがエグい 問題へのリンク editorial 問題概要 個の非負整数 が与えられる。これらの並び替え であって が最大となるものを求めよ。複数通り考えられる場合には辞書順最小のものを答えよ。ただし、 とする。 制約 考えたこと エグい場合分けが…
頭整理が大変だけど、考え方はわかる。 問題へのリンク 問題概要 は正の奇数である。 個の整数 が与えられる。以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる 個の整数 を 2 個ずつペアにして 組のペアを作る それぞれのペアの「数値の差」の総…
これかなりいい問題だと思う！！！ テスターをしていて、最初は 3 人じゃなくて 人だったけど、3 人にしたことでいい感じに 300 点問題になった！ 問題へのリンク 問題概要 人がいて、それぞれレーティングは となっている。 人の中から 3 人を選ぶ方法のう…
一目二分探索ゲーだし、実際二分探索で解けるのだけど、実はもっとすごく楽に解ける！！ 問題へのリンク 問題概要 長さ の整数列 が与えられる。数列の退屈さとは「同じ値が連続している区間の長さの最大値」として定義する。 与えられた数列において、最大…
これすごく好き！！！普通に難しい。 問題へのリンク 問題概要 'o' と 'x' のみからなる長さ の文字列 を作りたい。部品として使えるのは以下のものたち ( となっている)。 "ox" が 個 "xo" が 個 "o" が 個 "x" が 個 これらを適切な順序で concat すること…
めちゃくちゃ面白かった！ 問題へのリンク editorial 問題概要 個のカッコ列 が与えられる。これらを並び替えて連結して 1 個の文字列を作る。 この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。 制約 考えたこと 大前提…
平均求めるだけ 問題へのリンク 問題概要 個の 0 以上の整数 が与えられる。これらの値のうち、最大値と最小値を除去する (複数あるときはそのうちの 1 つ)。 残った 個の値の平均値 (小数点以下切り捨て) を求めよ。 制約 データセット数 考えたこと ででき…
これ結構好き！ 問題へのリンク 問題概要 それぞれ 枚のコインの入った 枚の袋と、 枚の皿 (初期状態ではすべて空) がある。これらを使ってゲームをする。先手と後手が交互に以下のように手を打つ。 (コインが入った袋が 1 つ以上存在するとき)：コインが入…
原案でした！僕は比較的アドホック寄りの問題を作る傾向があったかもだけど、これは典型な感じ。 問題へのリンク 問題概要 頂点数 、辺数 の連結な平面グラフが与えられます。ここで、各頂点の座標 も入力として与えられます。 どの 3 点も一直線上にはあり…
中盤枠という感じで作られた 問題へのリンク 問題概要 の番号を振られた 個の頂点があります。 最初、これらを繋ぐ辺はありません。 あなたはいくつかの辺を追加してこのグラフを連結にしたいと思いました。 頂点 と を繋ぐ辺を追加するには のコストがかか…
難しかったー！！平方分割かな...とまでは思ったので、もっと粘り強く考えられるようにならないと...！ 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の 4 種類のクエリを 回処理してください。 クエリ 1: が与えられるので、 () を に更新する…
最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…
探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…
DP 復元非本質＞＜ 問題へのリンク 問題概要 人のコンテスタントを 3 人以上を 1 チームとしたいくつかのチームに分割したい。コンテスタント のスキルは である。 チーム分けの良さを、各チームごとの「メンバーのスキルの最大値と最小値の差」の合計値とす…
この手の DFS、一時期全然見なかったけど、最近復活してきた！ 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…
面白かった 問題へのリンク 問題概要 頂点 辺の森が与えられる。各頂点 には、値 が付いている。これにいくつかの辺を追加して、連結にしたい。 頂点 と頂点 とを結ぶのに必要なコストは である すでに辺がある二頂点間は結べない 一度辺を張るのに使用した…
これは楽しい！！！ 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…
セグ木を使って差分更新していく系、解けるけど実装が苦手すぎるので、こういうのをスパッと書けるようになりたい！ 問題へのリンク 問題概要 個の武器と、 個の盾を持って、 体の敵に立ち向かう。あたなは武器の中から 1 個、盾の中から 1 個を選ぶ (初期状…
こういう「どの値が何個ありますか」的な処理方法は典型パターンが 2 つあると思う std::set や std::map などの連想配列を用いて管理する ソートしてソート順に処理していく 問題へのリンク 問題概要 個の整数 が与えられる。この整数列のどの 2 つの要素も…
