区間に関するクエリ
面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…
実家なんだと思うけど...意外とはまりやすい問題な気がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…
こういうのを得意になるぞー！！！ でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…
Mo のアルゴリズムの練習第三弾！！！！！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…
Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…
種類数クエリをマスターするぞ！ 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1： BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…
えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…
