K番目を求める
いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番…
二分探索法の教育的典型問題ですね！！ 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…
めっちゃフラクタルな問題だ！ ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 JOI のロゴは、下図のようになっている (問題文より)。 レベル のロゴは 1 × 1 のグリッドで "J" のみからなる レベル のロゴは、 の…
最初は、問題を見た瞬間に「にぶたんだ...」となったので、青 diff に驚いたのだった。でもいざ実装を始めると、頭壊れる問題ですね。。。^^; 問題へのリンク 問題概要 個の整数 が与えられる。これらから 2 つを選んで積をとって得られる 個の整数のうち、…
この手の DFS、一時期全然見なかったけど、最近復活してきた！ 問題へのリンク 問題概要 1 以上の整数であって、隣り合う桁の値の絶対値が 1 以下であるような数をルンルン数とよぶ。 番目に小さいルンルン数を求めよ。 制約 考えたこと さて、「 番目に小さ…
BinaryTrie を確認した！！！ 問題へのリンク 問題概要 数の集合 S に対する以下のクエリ ( 個) を処理してください。 S に数 X を追加する S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する 制約 考えたこと BIT や priority_queue、…
とてもこどふぉっぽい問題だと思った！！！こういうのを得意になるぞー！！！ 問題へのリンク 問題概要 の順列が与えられる。各 に対して、以下の問いに答えよ。 順列の隣り合う 2 要素を swap して、順列のどこかの場所で がこの順に連続で並んでいる状態に…
「k 番目を求める」に関する典型的な処理を要求される問題。 問題へのリンク 問題概要 空集合 に対して、以下の 回の操作を行う: に整数 を 個挿入する 回の操作後の S において 番目に小さな値を求めよ。 制約 考えたこと この問題の注意点として、 を具体…
昨日の ABC で、「左右両端からの累積和」を使うと良い問題が出たので、その発展的類題の紹介に。 drken1215.hatenablog.com 問題へのリンク 問題概要 を正の整数とする。 個の要素からなる数列 にとおいて、 個の要素を取り除き、残った 個の要素のうち (前…
priority_queue で動的に 個出力する問題作りたいな〜と思ってぼんやりストックしてた問題と一緒だった！！！！！！ 問題へのリンク 問題概要 個の要素からなる数列 個の要素からなる数列 個の要素からなる数列 が与えられる。 からそれぞれ 1 個ずつとりだ…
こういうのを爆速で書けるようになりたい。問題としては マンハッタン距離に関する問題では x 軸方向と y 軸方向とで独立に考えればよいことになるケースが多い (マンハッタンに限らず、各要素ごとに独立にならないかを考察することは重要) の最小値を与える…
「 番目の値を求めよ」「メディアンを求めよ」といった問題では、二分探索法が有効なことが多々ありますね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 この数列の連続する区間として考えられるものは 個あります。そのそれぞれの区間について…
十分多い回数重ねるとなにかが収束する系はよく見るん 問題へのリンク 問題概要 (ABC 106 C) 1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う: 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666…
AOJ-ICPC で無作為に問題を選んで実装する練習するなん。いや、つらいのんな^^; あと、桁 DP でやってしまったけど、もっとずっとはるかに楽な方法があったん。。。 問題へのリンク 問題概要 1 から順に FizzBuzz をやって得られる文字列を FizzBuzz 文字列…
完全に冷静さを欠いたし、ハマったん。。。 ARC 099 D - Snuke Numbers 問題概要 (ARC 099 D / ABC 101 D) 正の整数 N に対してその 10 進法での桁の和を f(N) で表す。今、正の整数 N がすぬけ数であるとは、任意の N より大きい正の整数 M に対して f(N) /…
本番出てなかったけどこれは... ARC 097 C K-th Substring 問題概要 文字列 s が与えられる。s の連続する部分文字列のうち、辞書順で K 番目の文字列を求めよ。 制約 1 <= |s| <= 5000 1 <= K <= 5 解法 K が小さいのが怪しい。 冷静に考えると、辞書順 K …
CS Academy 079 DIV2 E Smallest Subsets 問題概要 N 個の整数 S[0], S[1], ..., S[N-1] が与えられる。これらの部分和 (2N 通り) を小さい順に K 個出力せよ。 1 <= N <= 105 1 <= K <= min(2N, 105) -109 <= S[i] <= 109 解法 S[i] として負の値もあるのが…
yukicoder 649 ここでちょっとQK！ K は固定で与えられる。数の集合 S に対する以下の Q 個のクエリを処理してください。i 番目のクエリは以下のいずれかです。 タイプ 1： S に数 v[i] を追加する。 タイプ 2： S に含まれる数のうち K 番目に小さい数を答…
