TOP > ネタ・話題 > 与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱

与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱

長さ の数列 が与えられる。以下のクエリにたくさん答えよう。 クエリ : 区間 中に出現する数の種類数を求めよ 以下の制約で、効率的に解くことはできるだろうか? 数列の長さ: 要素の値: クエリの数: 以下、解法を3つ紹介する。...

ツイッターのコメント(17)

解法色々。何ならオンラインでもいけるらしい。典型問題っぽかったらまずはググろう……。
与えられた数列の区間中の種類数を求めるクエリにたくさん答えたい - 問題解決の宝石箱
これのことか?
なるほど…検索してみれば良かった
読んでみるか
自分用メモ
abcお疲れさまでした

F, これ実装すればいいんでしょ?って言いながら40分くらい椅子を温めてた
ありがとうございます。ありがとうございます。ありがとうございます。
なるほど
@watarimaycry2 これです
競技検索か?
ABC174 初全完
A: うん
B: 二乗して考えると安全
C: 5 の倍数ありえないのに気づくの五万年かかった レピュニットだって
どこから左を R に右を W にするか全探索
E: 落ち着いてみると整数の範囲でできる二分探索であることが分かる
Mo を貼ると壊れたので を写経
ABC174おつです、世界一褒め難い全完
C→なぜこれがDより解かれてないのか……
D→なぜこれがCより解かれているのか……
E→結果値で二分探索、過去問が活きてこれは瞬殺、小数点とかは割と無視できる設定
F→すみませんでした……
ABC174お疲れ様でした
C: 2*K桁まで回してみてだめなら-1をした
入れ替えだけ考えればいい
E: 2分探索
見た目がド典型なのでググると答えが書いてあります
Fはググったらこれに出会ったけど、解けなかった
うううう
見つけるのが遅すぎた
Fはこのサイトを見ました、ごめんなさい。
ABC174お疲れ様でした
89分+5ペナで初全完!!
C N−1桁まで見れば確定 
D どうせ2個目の操作要らないんだろ?
E にぶたん こういう系最近結構解いたからすぐ思いつけた
F 典型ぽかったから「c++ 区間 種類を求める」で調べたら出てきた(最悪)

BITを学べたのでOK!!
2番目の操作は必要ない。赤い石の個数を数え、最初からその数の場所までに含まれる白い石の個数が答え (6:17)
E: 蟻本p.129ほぼそのまま。最小の長さを決め打って二分探索 (8:08)
(13:48)
以上
 

いま話題のニュース

PR