虚の書院

問題追加と削除のクエリがあり、それぞれのクエリごとの結果を出力する。制約上クエリの最大数が多いので、1回の計算量が多いとTLEしてしまう。……という、C問題界隈ではよくあるいつものやつ。解説しかし、アプローチが異なるため初心者は躓きやすい。...

問題タイトル通りわらしべ長者。わらしべ有向グラフを渡り歩いて到達可能な頂点を数え上げる。解説グラフ理論を用いた探索。これを表現する実装が分かれば苦労しない。……分かれば、苦労しないはずなんだ……。（ｎ敗）隣接リストを用意する。このリストにあ...

N文字のSがあり、そのインデックスを表す整数の組i,jがあるとして、i,jは同じ文字、かつi,jの距離はL以上R以下、そんなやつをSの中から探索する。Nは5×105、普通に探索すると間に合わない。解説ほぼ問題文の通りに求める素朴な解法では、...

ここで重要なのは3つ。この問題のクエリ処理では配列Aの要素に対する変更がない。Kの制約が5までと少ない。Aから効率良く最小値を取り出すには並び替えの必要がある。Aの配列は制約上109程度まで大きくなるが、実際に評価するのはAを昇順に並び替え...

探索の必要があるものの制約はさほど大きくなく計算してみても最大58=390625程度、であれば全列挙した上で条件に合わないものを弾けばいい。全列挙するには再帰か、QueueやStackをWhileでぶん回す、全部ループを書くなどがあるが、ど...