JOI 2009 春合宿 day4 distribution(冊子の配布)
- 問題
- 解き方
木構造で何かしらの最大を求める問題は木dpっぽさを感じたので、この方針で突っ込んだ。
自分の子が持つべき情報は、何冊もらった時にどれだけのやる気を得ることができるかのテーブル。
この情報があれば、普通のdpの遷移と同じようにやれる。
つまり、
dp[v][i] := vを根とする部分木に i 冊配った時のやる気の総和の最大値
と定義する。
dp[v].size() = m として全頂点でdpをすると、遷移的にO(NM^2)になって間に合わないので、二乗の木dpというテクニックを使って高速化。
これは
木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
の解説を参考にするとよい。
- 自分の提出
Submission #21851215 - 2009年 日本情報オリンピック春合宿OJ
ABC182 Valid Payments
- 問題
- 解法
「同じ硬貨を使わない」というのを「同じ桁が同時に非零にならない」と読み替える。つまりY - X = Z (Y : 支払い、Z : お釣り) だと考えた時に、a0 < a1 < ... < a(n-1) かつ a(i+1) % ai = 0が成り立ってるので、各硬貨の使用枚数の上限が決まっていて、これをその桁で取れる最大の値と考える。
引き算は考えにくいので、Y = X + Z で考える。
条件「同じ桁が同時に非零にならない」を満たすような Y, Zの定め方を求めればいいが、これは桁dpで解ける形。
自分の実装では Zi = 0 の場合と Zi != 0 の場合に分けて考えたが、Yi = 0 と Zi = 0 の場合に分けてる人も多そう。(ZiはZのi桁目)
どちらにせよ、下の桁からの繰り上がりと合わせて考えることで、この桁からの繰り上がりが発生するかどうかが決まるので、注意深く場合分けすれば良い。
例えば、Zi != 0 の場合に Xi = 0 で下から繰り上げがないなら、どう頑張ってもZi = Yi になるので遷移できないので気をつける必要がある。
- 提出
JOI 2009 春合宿 day1-1 sequence3
- 問題
- 解き方
偶奇のみに注目すればよく、mod 2 で考える。
与えられた漸化式によって出来る bit 列は、初めの長さ m のビット列さえ決まれば一意に定まるので、m bit分のパターンに注目すれば良さそう。
0と1しか取らないので、各位置をスタート地点とみなして 2^m 通りくらい試せばループする(m bit分を1セットとして区切ってやろうとすると空間計算量がm倍になるので注意)。
- 提出
ABC140 F Many Slimes
- 問題概要
始めの1つの値を決めた後、毎秒いま持ってる全ての値に対して、それより真に小さい値を手持ちに加える。最終的に与えられた配列A内の2^N個の数と一致させることができるか。
- 解法
現在持ってる値の配列をcurと呼ぶことにする。
配列A内で最大である要素を、一番最初の値にしなければいけないのは明らか。
さらに、cur[i]から生み出す値は、 Aの中でまだcurから生み出されていない値であってかつ、cur[i]より小さい値のうち最大のものが最適。これは、数が大きければ大きいほど、後で生み出せる数の範囲が大きくなるため。
したがって、貪欲による解法でOK。
ちなみに、curからは大きい順に取っていく必要はない。
実装は、既に生み出したものを削除するためにmultisetを用いた。
また、Aの値を全て負の値にすることで、multisetのメンバ関数のupper_boundが使いやすくなる。
Codeforces Round #530 Div2 E. Nice Table
- 問題概要
A, G, C, TからなるN*Mのテーブルに対して、最小回数の操作を施して、どの2*2のマス内に各文字が一回ずつ登場するようなテーブルに直せ。
- 解法とその証明
文字をa,b,c,dで代表させることにする。この時、
abab
cdcd
abab
cdcd
のような状態から任意の行のみについてズラすか、任意の列のみについてズラすことで、2*2のマス内に各文字が一回ずつ登場する。逆に、このようにズラした後のテーブルのみを考えればいいことも証明できる。
※任意の行についてズラすとは、上の4*4のマスを例えば以下のような模様にすることである。
abab
dcdc
baba
cdcd
<proof>
任意の行と任意の列についてズラして、どの2*2のマスにもa,b,c,dが一回ずつしか現れないと仮定する。
ここで、ある行にa,b,c,dのうち3文字以上が含まれている場合を考えれば、この行の長さ3の文字列のどこかに必ず3文字が含まれている部分が存在する。
これを例えばc1c2c3だとすれば、c2の上下にある文字は、c1c2c3に含まれない文字であることが確定する(そうでなければ、2*2のマス内に含まれない文字が存在する)。
そして、c2の上下が決まると、2*2マス内に1回ずつ現れるという仮定から、この上下の行はそれぞれ一意に定まり、これらの行も3文字を含んでいてかつ文字列として等しいことが分かる(下のテーブルを参照)。
dcdad
babcb (c1c2c3 は abc に対応する)
dcdad
従って、新たに定まった行に対しても3文字を含んでいることから、その上下の文字列も等しいことになり、結局偶数行目と奇数行目の文字列が等しいことが導かれる。
つまり、各列については違う文字を2つしか含まない。
行と列についての議論を変えても同じことが言える。また、同じ行または列に4文字以上が含まれる場合でも、長さ3の文字列を取り出せば同様のことが言える。
従って、条件を満たすテーブルは、各行または各列に2種類の文字しか含まないことが分かる(1種類の文字しか含まない時は自明にOUT)。
これは結局、一番最初に書いたテーブルについて、任意の行あるいは列についてのみズラす操作をすることで達成できる。
自分の提出コードはありませんが、snukeさんのコードが分りやすいと思ったので載せておきます。(列についての操作を、テーブルを反転させることで行についての操作に帰着させています。)
