けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

種類数

AtCoder ABC 085 B - Kagami Mochi (6Q, 灰色, 200 点)

古き良き、ABS にも収録した問題! 問題へのリンク 問題概要 個の整数 が与えられる。 これらの整数の中に、相異なる整数は何種類あるかを求めよ。 制約 解法 最も簡単な方法は、集合型 set 型を用いる方法だと思われる。set は 要素の挿入 (集合に要素 を挿…

AtCoder ABC 225 A - Distinct Strings (7Q, 灰色, 100 点)

これ結構難しいと思う! 数学 IA の「場合の数」をやると、よく出て来るやつですね。 問題へのリンク 問題概要 英小文字のみからなる長さ 3 の文字列 が与えられます。 の各文字を並び替えて得られる文字列は、何種類ありますか? 解法 「3 個のものを並び替…

AtCoder ABC 155 A - Poor (灰色, 100 点)

これは結構難しい。いろんな解法がある。 問題へのリンク 問題概要 個の整数 が与えられる。 これらのうち 2 個の値が等しく、残りの 1 個の値がそれらと異なるならば "Yes" を出力せよ。そうでなければ "No" を出力せよ。 解法 ABC-A の前提知識ではないが…

AtCoder ABC 132 A - Fifty-Fifty (灰色, 100 点)

これはだいぶ難しい問題ですね! 問題へのリンク 問題概要 4 文字の文字列 が与えられる。 がちょうど 2 種類の文字からなり、それらの文字がちょうど 2 個ずつあるかどうかを判定せよ。 解法 色んな解法があると思われる。ここでは、 をアルファベット順に…

AtCoder ABC 329 C - Count xxx (灰色, 300 点)

ランレングス圧縮の典型題! なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…

AtCoder ABC 046 A - AtCoDeerくんとペンキ (7Q, 灰色, 100 点)

3 つの整数についてあれこれ問う問題はこの時代多かった 問題へのリンク 問題概要 3 個の整数 がある。これらは 1 以上 100 以下の整数である。 これらの整数の種類数を求めよ。 コード この手の問題は、「配列として受け取ってソートする」テクニックが使え…

AtCoder ABC 215 G - Colorful Candies 2 (黄色, 600 点)

最初 DP で迷走して、期待値の線形性を使って まで来れた。でも、Polynomial Taylor Shift なる解法もあるらしい! 問題へのリンク 問題概要 個のキャンディがあって、各キャンディの色は正の整数 で表されている。 各 に対して、 個のキャンディから 個のキ…

AtCoder ABC 302 Ex - Ball Collector (橙色, 625 点)

undo 付き Union-Find! 問題へのリンク 問題概要 頂点数 の木が与えられる。各頂点には、数値 の書かれたボールと、数値 の書かれたボールがある。 各 に対して、次の問に答えよ。 パス - 上の各頂点から ボールを 1 個ずつ選んだときの ボールに書かれた数…

Yosupo Library Checker - Number of Substrings

Suffix Array を用いる練習問題! ACL practice contest にもある。 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 考えたこと 実は、AtCoder Library Practice Contest に全く同じ問題がある! drk…

AtCoder Library Practice Contest I - Number of Substrings (2D)

Suffix Array と LCP の理解を問う問題。超シンプルで面白い問題! 問題へのリンク 問題概要 長さが の文字列 が与えられる。 の連続する部分文字列の種類数を答えよ。 制約 解法 文字列 の Suffix とは「後ろの何文字かをとってできる文字列」のことである…

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…

AtCoder ABC 249 C - Just K (茶色, 300 点)

ビット全探索もついに茶色 diff ですね! 問題へのリンク 予備知識 ビット全探索の知識があると解きやすいです! drken1215.hatenablog.com 問題概要 英小文字のみからなる 個の文字列 が与えられます。 これらの文字列の中から、いくつかの文字列を選びます…

Codeforces Round #683 (Div. 1) D2. Frequency Problem (R3000)

平方分割で解法を分岐する系の問題で、そのうちの片方の問題は Easy Version として D1 で出題されてた (Easy Version は R2600) 問題へのリンク 問題概要 正の整数 が与えられる。 以上 以下の整数のみからなる 要素の数列 が与えられる。 数列の連続する区…

Codeforces Grakn Forces 2020 E. Avoid Rainbow Cycles (R2400)

むずかしい 問題へのリンク 問題概要 長さ の数列 と、長さ の数列 が与えられる。これらはある操作のコストを決めるためのパラメータである。 さらに、 系列の数列が与えられる。 番目の数列の項数は で与えられる 数列の各項 は 以上 以下の値である 今、…

AtCoder ABC 157 E - Simple String Queries (水色, 500 点)

一瞬、「更新がある」「種類数」ということで、Wavelet Matrix が必要かとびびった 問題へのリンク 問題概要 長さ の文字列 が与えられる。以下の 個のクエリに答えよ タイプ 1: の 文字目を に変更する タイプ 2: の区間 に含まれる文字の種類数を答える …

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

AtCoder ABC 064 C - Colorful Leaderboard (茶色, 300 点)

あるあるあるある。 問題へのリンク 問題概要 人がいてそれぞれの AtCoder レーティングが与えれている。1 以上 4800 以下で、400 ごとに色が変わるという設定。 今、レーティング 3200 以上の人は自由に色を変えることができる。このとき、 人の中に存在す…

AtCoder ARC 074 E - RGB Sequence (橙色, 800 点)

わかってる...!わかってるんだ!!!この問題が超ド典型だってことくらい!!!!!!!! でも典型だからって、そんなパッと解けるわけじゃない。すごく苦手なんだこういうの。。。 問題へのリンク 問題概要 マスを RGB の三色で塗り分ける 通りの方法のう…

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

AOJ 2444 Substring (JAG 夏合宿 2012 day3b-E) (450 点)

ロリハそのものな問題!!! 問題へのリンク 問題概要 長さ の文字列 が与えられ、 の連続する部分列が 個指定される。こうして作られる 個の文字列のうち、相異なるものは何通りあるか答えよ。 考えたこと ロリハで頑張る #include <iostream> #include <vector> #include <string> #i</string></vector></iostream>…

SPOJ DQUERY - D-query

種類数クエリをマスターするぞ! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1: BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…