裏紙

ほぼ競プロ、たまに日記

GCJ 2017 R1A B - Ratatouille

問題

Dashboard - Round 1A 2017 - Google Code Jam

問題概要

究極のラタテュイユのレシピが完成した。レシピにはどの原料をどれほど使うべきか、が記されている。ラタテュイユにはn種類の原料が必要であり、1人前を作るのにi番目の原料がR_iグラム必要である。

その原料をセットとして揃えて売るために、原料パッケージをいくつか注文することにした。原料パッケージには、ある特定の原料が一定量だけ入っている。各原料ごとにp個のパッケージがあり、i番目の原料のj個目のパッケージにはQ_{ij}グラムの原料が入っている。

これらのパッケージを使って、ラタテュイユキットをなるべく多く作りたい。ラタテュイユキットは、ラタテュイユに必要な各原料のパッケージ1つずつを組み合わせて構成される。

原料の比が厳密なもののみを作ろうとするとあんまりセットが作れないので、実際にそのセットで作ることができるとラベルに書いてある量に対して、原料は90%~110%の間に収まっていれば良いということにした。

例:ラタテュイユ1人前に500gのトマトと300gの玉ねぎが必要な場合

原料パッケージとして、900gのトマトと660gの玉ねぎを持っているとする。
これらのパッケージを使って、2人前のキットを作ることが出来る。
2人前には1000gのトマトと600gの玉ねぎが必要だが、
  トマトの量は1000gの90%~110%
  玉ねぎの量は600gの90%~110%
に収まっていれば良いので、可能である。

また、x人前のキットを作ると考えるときに、xは必ず整数でなければならない。更に、何人前のキットを作ろうと、それは1個のキットと見なす。この時に、作れるキットの個数を最大化せよ。

  •  1 \le n \le 50
  •  1 \le p \le 50
  •  n * p \le 1000
  •  1 \le r_i \le 10^6
  •  1 \le q_{ij} \le 10^6

イデア

パッケージのグラム数は本質的に重要な情報ではなく、重要なことは各パッケージは何人前に割り当てることが出来るのかということである。

例えば、1人前には10gのトマトが必要な時に、201gのトマトのパッケージは19~22人前のキットに入れることが出来る。このように、各パッケージを区間として考えることにしよう。

では、この区間を計算することを考える。パッケージの量をQ、その原料の1人前の量をRとすると、m人前のキットに入れることが出来る時、 0.9 * R * m \le Q \le 1.1 * R * mを満たし、mについて変形すれば \frac{10 * Q}{11 * R} \le m \le \frac{10 * Q}{9 * R}と計算でき、O(1)で計算できる。

さて、この区間を各原料ごとに昇順でソートしておき、各原料について何番目を見ているかを保存しながら、小さい方から貪欲にi人前のセットが作れるかをイテレーションしていくと良い。

任意の区間に対してだとこれが上手く行かない場合があるような感じがするが、今回のような区間の作り方だと上手くいく。なぜなら、今回の区間の作り方に従うと以下のことが成り立つ:

同じ原料の2つの区間l_1l_2を考える。l_1l_2に含まれる時、2つの区間は少なくとも1つの区間の端点を共有している(Property 0)。

→ 各区間が実際にS_iグラムから得られたものだったとすると、S_1 \le S_2のとき、l_1の下限はl_2より大きいことはない(つまりl_2と下限が一致)。逆に、S_1 \gt S_2のとき、l_1の上限はl_2より小さいことはない(つまりl_2と上限が一致)。よって少なくとも一方は端点が一致することが分かる。

上の貪欲が正しいことを証明する前に、他にも良い性質があるのでそれを確認しておこう。

  • Property 1: ある区間を捨てる(どのキットにも入れない)ことにする時と言うのはもうその区間のあらゆるx人前のキットが作れないことを意味する。

  • Property 2: ある区間を採用する(あるキットに入れる)ことにする時に、区間の共通部分のうち最小値がMだとすると、M未満のx人前のキットはもう作れない。

確かに、上の貪欲に従っていくなら、2つとも当たり前のことだという感じがする。それでは証明に入る。

上の貪欲によって、M_1 , M_2, \ldots , M_k人前のキットが作成されていったとする。ここで、N_1 , N_2, \ldots , N_k, N_{k+1}人前のキットの作り方のうち最小のものがあるとする。

Case A

iN_i \lt M_iを満たす最小の値とする。Property 2によって、このようなことが発生するのはN_i人前のキットがもう作れない場合に発生する。これは、考えた貪欲がそのような区間を捨てているか、以前に使用してしまった可能性が考えられるが、前者はProperty 1によって有り得ない。また、貪欲の選び方とProperty 0によって後者も起こり得ない。ある区間rが選ばれる時、その原料パッケージに対してまだ残っている区間rよりも上限は小さいことはない。よってその時点で選ぶのはrがベターであることが分かる。

Case B

Aのようなiが無いとする。つまり、N_{k+1}のキットが作成できなかったことになるが、Property 0,1によりこれは有り得ないことが同様に言える。

以上より上の貪欲は最適なことが分かる。

実装(C++)

続きを読む

CS Academy #42 - Xor Submatrix

問題

CS Academy

問題概要

長さnの配列vと長さmの配列uが与えられる。これらから、n * mの行列Aを作る。A_{ij} = v_i \ XOR \ u_jで行列の各項を与える。 この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。

  •  1 \le n,m \le 1000
  •  0 \le v_i , u_i \lt 2^{29}

イデア

部分行列の左上隅のindexを(ly,lx)、右下隅のindexを(ry,rx)と表すことにしよう。ここで、部分行列内の全てのXORを取るということがどういうことになるのかを考えてみると、各v_i (ly \le i \le ry)rx-lx+1回だけ全てのXORの計算に現れてくることになる。つまり、このrx-lx+1の偶奇によって、各v_i (ly \le i \le ry)が総和に現れるか否かが決まる事がわかる。

この考察より、以下の3パターンに分けて考えよう:

  1. 縦も横も偶数幅
  2. 縦か横のどちらか一方が偶数幅でもう片方は奇数幅
  3. 縦も横も偶数幅

1の場合については、全ての項が偶数回現れることになるので0になる。2の場合については、奇数幅を構成する側は偶数回現れることになるので打ち消し合い、偶数幅を構成する側のみのXORを取ることになる。3の場合は両方の幅を構成するもののXORを取れば良いことになる。

そうすると、部分行列の(ly,lx)(ry,rx)を決めればvuについてXORでの累積和を持つことによってこの部分行列内のXOR和をO(1)で得ることができる。

よって、部分行列内を全て計算する必要はなく、各配列v,uでそれぞれこのような累積和を取る話に問題は変わってくる。そこで、この問題を言い換えると、

vから奇数幅で得られるXOR和の値を集めた集合Vと、uから奇数幅で得られるXOR和の値を集めた集合Uから1つずつ値を選んでXORを取って最大値を構成するという問題になる。これはTrieを使うことで求められる。具体的には、Vの要素を全てバイナリとして表したものをTrie上にのせ、U内の各要素に対して大きいビットの方から貪欲にそのビットを1に出来るならその方向に進むということをすればよい。

実装(C++)

続きを読む

CS Academy #44 - Array Elimination

問題

CS Academy

問題概要

素数nの配列aが与えられる。いま、配列のindexを1つ指しているポインタpがあり(はじめはp=0)、そのポインタに対して以下の3つの操作ができる:

  • pを1増やす
  • pを1減らす
  • pが指している位置の要素を削除し、pは1つ前の要素か1つ後の要素を指すようにどちらかを選ぶ

この3番目で行う削除の順番を、non-decreasing orderで行うために必要な操作の回数の最小値を求めよ。

  •  1 \le n \le 10^5
  •  1 \le a_i \le 10^9

イデア

まず、配列aの中に同じ要素がなければ、削除の順番は一意に決定するので操作は貪欲にしていけば良いことになる。この操作の一つ一つを本当にシミュレーションするとなると回数はO(n^2)回かかるので当然間に合わない(ただ、次に行くべき位置が決まってるので、移動は省けそうに見える)。

もし、aも中に同じ要素がある場合は、要素の値でグループ分けをして削除の処理をしていくことになる。この時、グループ間の削除の順番は入れ替えることが出来ないが、グループ内であれば削除の順番を入れ替えても良いことになる。

今、x未満の値の削除が終了し、xの値のグループを削除していくという状況を考えよう。さて、上の3つの操作を見比べてみると、pが値xの位置を指しているときにするべきことは3番目の操作しかありえないということが分かる(1番目の操作や2番目の操作もその中に含んでいるし、その後の状況が良い)。ということを考えれば、このグループ内で最後に削除されることになるのは配列の左端のxまたは右端のxのどちらかということになる。

よって、次のようなDPが考えられる:

dp[x][0/1] = 値x以下は全て削除完了し、値xのグループに関しては最後に削除したのが左端(0)/右端(1)のときの(削除を伴わない移動)操作回数の最小値

xの部分については座圧することで、n種類になる。小さい方からi番目の値であると考えることにすると、このdpを計算するのに必要なのはdp[i-1][0/1]ということになる。

dp[i][0]を計算したいと思った場合には、dp[i-1][0]とdp[i-1][1]のそれぞれからの遷移を考えるわけだが、どちらについてもやるべき最適な動作は共通で、値xの右端まで(値を削除しながら)ポインタを進めていき、折り返して左端まで行くという操作になる。その間で必要になる操作の回数はその区間にあるxより大きい値の個数に一致することになる。これは、dpを進めていくと同時にBITを更新することでその個数を数えることができ、全体としてはO(n log n)で実現出来る。

実装(C++)

続きを読む