提出コード 2つの要素$a_l$と$a_r$をSwapしたとき、$a_r > a_l$であれば、 ある範囲ではPrefixSumが増加し、それ以外では変化しないということになる。 つまり、単純に固定されていない要素を降順に並べ替えればよい。 $0 \sim l-1$の範囲ではPrefixSumの変化なし $l \sim r-1$の範囲ではPrefixSumが$+(a_r-a_l)$増加する $r \sim n-1$の範囲ではPrefixSumの変化なし
提出コード もしも $n \ge 4$ かつ $m \ge 4$ の場合には、どうやっても条件A（縦横の長さがともに偶数の正方形内に含まれる1の数が奇数）を満たすことができない。 例えば、$2 \times 2$の正方形が条件Aを満たすとき、その正方形を4つ連結すると、 その和は偶数になってしまう。つまり、$4 \times 4$の正方形では条件Aを満たすことができない。 それ以外の場合には、何度か操作することで必ず条件Aを満たすことができる。 最小の操作回数はDPを使って解くことができる。 $dp_{i,bit}$を、$i$番目の行まで見たときに、$i$番目のビット列が$bit$であるときの 最小の操作回数とする。 更新式は以下の通り。ただし、$bit$と$nbit$と間で条件Aを満たすことを確認する。 $$ \begin{aligned} dp_{i+1,nbit} \Leftarrow dp_{i, bit} + \sum_{j=0}^{m-1} ((nbit » j) \& 1) \oplus a_{i+1,j} \end{aligned} $$
提出したコード 文字列 $t$ が与えられるので、$t$ の循環左シフト後と循環右シフト後の文字列を等しくしたい。 $t$からいくつか文字を取り除いてこの条件を満たすときに、取り除く最小の文字数は？ $n$ を $t$ の文字列長として、その偶奇で分けて考える。 $n$ が奇数の場合 $t = t_1 t_2 t_3 t_4 t_5$ を例とする。 巡回左シフト $ t_2 t_3 t_4 t_5 t_1$ と巡回右シフト $t_5 t_1 t_2 t_3 t_4$ を等しくしたい。 つまり、すべての文字を等しくする必要がある。 $n$ が偶数の場合 $t = t_1 t_2 t_3 t_4$ を例とする。 巡回左シフト $t_2 t_3 t_4 t_1$ と巡回右シフト $t_4 t_1 t_2 t_3$ を等しくしたい。 つまり、偶数番目はすべて同じ文字であって、かつ奇数番目もすべて同じ文字でないといけない。 解法 いくつかの文字を取り除いた後の文字列の先頭2文字について全探索をする。 先頭2文字が同じ場合、先頭2文字$aa$の後に何文字か$a \dots a$が続けばよい。 違う場合は、先頭2文字$ab$の後に$ababab \dots ab$が続けばよい。
提出したコード 整数$a \ge 2$が与えられるので、$gcd(d_1+d_2,a)=1$を満たすような組$(d_1,d_2)$を求めたい。 ただし、$d_1 \ge 2$かつ$d_2 \ge 2$。 これを$n$個回繰り返す。 まず $a = {p_1}^{k_1} \cdot {p_2}^{k_2} \cdots {p_m}^{k_m}$ のように素因数分解を行う。 もし $m = 1$あるいは$a$が素数の場合には、答えは$(-1,-1)$。 $m \ge 2$の場合には、$(p_1, p_2 \cdot p_3 \cdots p_m)$が答えとなる。 なぜこれが答えでよいのか見ていく。 「$d_1 + d_2$がいかなる素因数$p_i$に対しても割り切れないこと」が言えればよい。 まず、「$d1 + d2$ が $p1$ で割り切れない」ことが正しいのか考えてみる。 $d1 \equiv 0, d2 \not \equiv 0 (mod \ p_1) $ より、$d1 + d2 \not \equiv 0 (mod \ p_1)$ となる。 続いて、「$d1 + d2$ は $p_i (2 \le i \le m)$ で割り切れない」ことが正しいのか考えてみる。 $d1 \not \equiv 0, d2 \equiv 0 (mod \ p_i) $ より、$d1 + d2 \not \equiv 0 (mod \ p_i)$ となる。 ...
ちょっと競技プロをやってみた． Codeforces #308 (Div.2) Codeforcesに初参加． 結局A-Eの5問中，Aしか解けなかった． Aは，実装するだけという感じだったので，そんなに時間がかからず解けた． Bは，ヒストグラムを作れば解けたと思うが，それに気づくのが遅かった． Cは，4番目のpretestで失敗． D,Eは手を付けてない． それと，pretestに失敗した時は，「My contest submissions」から テストケースの詳細が見れるのを知らなかった． ARC040 4問中3問解けた． 問題DはDPかなんかで計算量下げるんだろうなと思ったが， 全探索以外の手法が思いつかず終了． 精進します．