SRM700 Div1Medium. CrazyFunctions

SRM700 Div1Medium. CrazyFunctions

整数 , が与えられる。以下の条件を満たす関数 を数え上げよ。

• の定義域および値域は 1以上n以下の整数である。
• を満たす。関数 の定義は以下の通り。
  • は の最小値を返す関数。 は任意の非負整数。
  • は 集合 の要素数。
  • は 以上の整数 について、関数 の取りうる値の集合。
    • とは、関数 を に 回適用した値。、および を満たす。

制約

• 
• 

CODE FESTIVAL 2016 予選B E. Lexicographical disorder

日本語につき問題文は略。

code-festival-2016-qualb.contest.atcoder.jp

解法を2つ紹介する。

指定区間の最大値／最小値のインデックスを求めるクエリにたくさん答えたい part2

hama-du-competitive.hatenablog.com

前回の記事の最後で紹介した練習問題の解答編。問題を整理して再掲する。

長さ の数列 が与えられる。クエリに 個答えよ。

全ての問題において、制約は以下の通り。

• 数列の長さ：
• 要素の値：
• クエリの数：

問題1

• i 番目の値を v に変更する。
• l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、インデックスの合計 を出力。

問題2

• i 番目の値を v に変更する。
• l 番目から r 番目の値の中で、 最も左端で*1 v 以下になるインデックス を求める。存在しない場合はその旨を報告。

問題3

• l 番目から r 番目の値を v に変更する。
• l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*2インデックスを求めること。

*1:最も l に近い

*2:最も l に近い

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

Codeforces Goodbye 2015 D. New Year and Ancient Prophecy

桁の数が与えられる。桁の間にいくつか*1線を引いて分割し、新たな数列を得ることを考えよう。

例えば、数 314159265358979 を 3 | 141 | 592 | 6535 | 8979 のように分割すると、数列

が得られる。

数を分割して数列にした時、要素が真に昇順に並んでいる（）ような分割の仕方は何通りあるだろうか？

制約

• 桁数：

*1:0個でもよい

指定区間の最大値／最小値のインデックスを求めるクエリにたくさん答えたい part1

区間内の最大値/最小値のインデックスを求めるRMQの実装を求めています。

— tookunn (@tookunn_1213) October 6, 2016

この問題を以下のように定式化した。効率よく解けるだろうか？

長さ の数列 が与えられる。以下のクエリに 個答えよ。

• クエリ1 : i 番目の値を v に変更する。
• クエリ2 : l 番目から r 番目の値の中で、最小値とそのインデックスを求める。複数ある場合は、最も左端の*1インデックスを求めること。

制約は以下の通り。

• 数列の長さ：
• 要素の値：
• クエリの数：

*1:最も l に近い

AGC #005-D ~K Perm Counting

日本語につき問題文は略。

agc005.contest.atcoder.jp

与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。

• クエリ : 区間 中に出現する数の種類数を求めよ

以下の制約で、効率的に解くことはできるだろうか？

• 数列の長さ：
• 要素の値：
• クエリの数：

以下、解法を3つ紹介する。