CS Academy #42 - Xor Submatrix
問題
問題概要
長さの配列
と長さ
の配列
が与えられる。これらから、
の行列
を作る。
で行列の各項を与える。
この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。
アイデア
部分行列の左上隅のindexを、右下隅のindexを
と表すことにしよう。ここで、部分行列内の全てのXORを取るということがどういうことになるのかを考えてみると、各
は
回だけ全てのXORの計算に現れてくることになる。つまり、この
の偶奇によって、各
が総和に現れるか否かが決まる事がわかる。
この考察より、以下の3パターンに分けて考えよう：
- 縦も横も偶数幅
- 縦か横のどちらか一方が偶数幅でもう片方は奇数幅
- 縦も横も偶数幅
1の場合については、全ての項が偶数回現れることになるので0になる。2の場合については、奇数幅を構成する側は偶数回現れることになるので打ち消し合い、偶数幅を構成する側のみのXORを取ることになる。3の場合は両方の幅を構成するもののXORを取れば良いことになる。
そうすると、部分行列のと
を決めれば
と
についてXORでの累積和を持つことによってこの部分行列内のXOR和を
で得ることができる。
よって、部分行列内を全て計算する必要はなく、各配列でそれぞれこのような累積和を取る話に問題は変わってくる。そこで、この問題を言い換えると、
から奇数幅で得られるXOR和の値を集めた集合
と、
から奇数幅で得られるXOR和の値を集めた集合
から1つずつ値を選んでXORを取って最大値を構成するという問題になる。これはTrieを使うことで求められる。具体的には、Vの要素を全てバイナリとして表したものをTrie上にのせ、
内の各要素に対して大きいビットの方から貪欲にそのビットを1に出来るならその方向に進むということをすればよい。
実装(C++)
続きを読むCS Academy #44 - Array Elimination
問題
問題概要
要素数の配列
が与えられる。いま、配列のindexを1つ指しているポインタ
があり(はじめは
)、そのポインタに対して以下の3つの操作ができる：
を1増やす
この3番目で行う削除の順番を、non-decreasing orderで行うために必要な操作の回数の最小値を求めよ。
アイデア
まず、配列の中に同じ要素がなければ、削除の順番は一意に決定するので操作は貪欲にしていけば良いことになる。この操作の一つ一つを本当にシミュレーションするとなると回数は
回かかるので当然間に合わない(ただ、次に行くべき位置が決まってるので、移動は省けそうに見える)。
もし、も中に同じ要素がある場合は、要素の値でグループ分けをして削除の処理をしていくことになる。この時、グループ間の削除の順番は入れ替えることが出来ないが、グループ内であれば削除の順番を入れ替えても良いことになる。
今、未満の値の削除が終了し、
の値のグループを削除していくという状況を考えよう。さて、上の3つの操作を見比べてみると、
が値
の位置を指しているときにするべきことは3番目の操作しかありえないということが分かる(1番目の操作や2番目の操作もその中に含んでいるし、その後の状況が良い)。ということを考えれば、このグループ内で最後に削除されることになるのは配列の左端の
または右端の
のどちらかということになる。
よって、次のようなDPが考えられる：
dp[x][0/1] = 値x以下は全て削除完了し、値xのグループに関しては最後に削除したのが左端(0)/右端(1)のときの(削除を伴わない移動)操作回数の最小値
xの部分については座圧することで、種類になる。小さい方から
番目の値であると考えることにすると、このdpを計算するのに必要なのはdp[i-1][0/1]ということになる。
dp[i][0]を計算したいと思った場合には、dp[i-1][0]とdp[i-1][1]のそれぞれからの遷移を考えるわけだが、どちらについてもやるべき最適な動作は共通で、値xの右端まで(値を削除しながら)ポインタを進めていき、折り返して左端まで行くという操作になる。その間で必要になる操作の回数はその区間にあるより大きい値の個数に一致することになる。これは、dpを進めていくと同時にBITを更新することでその個数を数えることができ、全体としては
で実現出来る。
