競技プログラミング

問題追加と削除のクエリがあり、それぞれのクエリごとの結果を出力する。制約上クエリの最大数が多いので、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でぶん回す、全部ループを書くなどがあるが、ど...

Sを並び替えて有り得る組み合わせの中で、Kの長さの回文を含まない組み合わせの数を答える問題。で、その列挙のためのC++やPythonにあるnext_permutationはどこ？　というのがC#で解くにあたって最も困難な部分。これが使用する...

愚直に有り得る組み合わせを試していったらMLE（メモリ制限超過）した。愚直過ぎた。悔しい。解説制約と問題の性質上、有り得るパターンを分けていけば探索の必要なくACできる。2つより多く分かれることを考えなくてよく、分かれなかったものが存在する...

問題の要約空文字列であるsにQ個のクエリを施し、その各クエリの直後にそれぞれの()が対応する「良い括弧列」であるかを判定する。クエリは800000あるので、「良い括弧列であるか」の判定をO(1)程度でできないと3秒に間に合わない。解説クエリ...