問題概略 長さNの数列Aと整数Kが与えられる。 以下の操作をQ回行う 連続するK個を選び最小値を取り除く。上の操作で得られた最大値と最小値の差を最小にしたい。制約 1 1 解法 問題をそのまま捉えるとよくわからなくなる。 これは一番いい最大値と最小値を選…

C - String Coloring 問題概略 長さ2Nの文字列が与えられる。各文字を青と赤に塗り分けた時、左から青を読んだときと右から赤を読んだ時の文字列が同じ組み合わせはいくつあるか 制約 1≤N≤181≤N≤18 SS の長さは 2N2N である SS は英小文字のみからなる 解法 …

C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder 問題概略 N個の整数A1~ANが与えられる。i<jとなるAi,Ajを選んだ時、２つの積がKの倍数となる組み合わせを求めよ 制約 1≦N≦200,000 1≦Ai≦109(1≦i≦N) 1≦K≦109 Ai, K はいずれも整数 解法 N^2では間に合わない。組み合わせ問題でよくあるまとめ上げを使う。 ２つの積がKの倍数になる -> Kの約数でないものは考えなくていいため、Aたちの中からKの約数だけを取り出し、それぞれ何個あるかを持っておく。 あと</jとなるai,ajを選んだ時、２つの積がkの倍数となる組み合わせを求めよ>…

D - 連結 / ConnectivityD - 連結 / ConnectivityD - 連結 / Connectivity ２種類の連結が与えられ、それぞれの街で二重に連結されている街の個数を数える問題 2 解法2種類の親が同じなら、aとbは二重に連結していることがわかる。aとbのとり方は無限にある…