問題 解法 n文字からなる文字列の変換の典型として, 'a' -> 0, 'b' -> 1, 'c' -> 2 に変換して総和のmod3に注目する この場合でも総和のmod3は保存されることがわかる. この非自明な必要条件が本質. 更に実験すればわかるが,1回以上の操作によって a[i] == a…

問題 解法 全力で必要条件を列挙していく. Nのk進数表記が下の桁から n_0, n_1, n_2, .. であったとすると, N = n_0 + n_1 r1 + + n_2 r2 + .. a_k = n_0 + n_1 + n_2 + .. N - a_k = n_1 (r - 1) + n_2 (r2 - 1) + n_3 (r3 - 1) で, rx - 1 は r-1 で割り切…

問題 解法 1,..,N の順列を p1,..,pN として, 最大化したい関数は |A_p1 - A_p2| + .. + |A_pN-1 - A_pN| になる. 目的関数の絶対値を外したい気持ちになるので,そのためには数列の順序付けが必要になる. それを念頭に起きつつ最適解の必要条件を列挙してみ…

問題 解法 sample2をじっと見ると,必要条件として X_i, Y_i の和のパリティが全て一致する というのがあることがわかる パリティに注目するのはよくやるのでこれは気づかないとどうにもならない. 実際に,そのときdとして1を20個/21個用意すれば300点は取れる…

問題 解法 まず十分条件を列挙していく. 0-indexedとして, s[0] = 1 s[N-1] = 1 s[i] = s[N-1-i] D問題でもそうだったが,自明な必要条件が必要十分条件になっているというパターン. s = "100..01.." として,k番目に初めて1が現れるとする. このとき,1つの辺…

問題 問題概要 a[i] (1<=i<=N) の長さのロープN本がある.これらは順に繋がっている. 長さがLより小さくならないように一つずつ結び目を解くことができるか,できる時解き方を出力せよ. 2 <= N <= 105, 1 <= a_i,L <= 109 解法 解くことができる <-> a[i] + a[…

問題 問題概要 ビット列Sが与えられる。K以上の範囲を選んでその区間のSを反転させることができる時、最大のKを求めよ。 1<= |S| <= 105 解法 k文字目のみを変えようとした時、[0,k-1]->[0,k]を反転させることで変えることができる。 同様に[k+1,N]->[k,N]で…