ARC 081 F - Flip and Rectangles
問題概要
0,1が書かれているh*wの盤面がある.
行または列を全て反転する操作が何回でもできるとして,
その中の要素が全て1であるような長方形の最大の面積を求めよ.
解法
ここの方法がわかりやすかったのでこれでやった.
ex.
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
まず横方向にxorをとっていく.
a[i][j]
1 1 1 1
1 1 1 0
1 1 0 0
0 1 0 0
その a[i][j] を縦方向に見ていって, その部分列を要素が{0,0,...,0}か{1,1,...,1}であるように取ることができるなら
横に一つ伸ばして, jとj+1のその部分列で長方形を作ることができる.
例えば,赤色の部分を取ると
a[i][j]
1 1 1 1
1 1 1 0
1 1 0 0
0 1 0 0
この部分が長方形にできることがわかる.
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
よって hist[i][j] = (a[i][j]と等しい数が上に何個続くか) とすると,
hist[i][j]
1 1 1 1
2 2 2 1
3 3 1 1
1 1 2 2
これを横方向にヒストグラムと見なし,ヒストグラムの最大長方形を求めれば良い.
上の青い部分を取れば,
盤面
1 0 1 0 1
0 1 0 1 1
1 0 1 1 1
0 0 1 1 1
の部分で最大長方形が作れることがわかる.
ただし, (長方形) = (高さ) * (幅+1) としてやることに注意する.
メモ
解けなかった.
flipなどでは特に階差xorを考えるのと,
最大長方形のアルゴリズム覚えておきたい..
コード
ARC 092 D - Two Sequences
問題概要
N要素の数列{a_i}, {b_i} が与えられる.
Xor_(1<=i,j<=N) (a_i + b_i) を求めよ.
解法
a_i + b_j のkビット目の1の数の偶奇を考える.
x + y = ( x & y ) << 1 + ( x xor y ) から,
(a_i , b_j のkビット目の立っている数) * N + (k-1ビット以下からの桁上がり) の偶奇を考えれば良い.
前半はそのまま数えればよく, 後半は ((1<<k) - 1) でマスクして(kビット目以上を0にする)ソートし,
各a_iについて, b_j + a_i >= 2k なるjの数をにぶたんで数えれば良い.
計算量はO(30NlogN)
メモ
こういうのは大体各ビットに注目すれば解ける(自戒)
コード
AGC 022 C - Remainder Game
問題概要
N要素の整数列{a_i}を以下の作業を繰り返して{b_i}に一致させる.
- いくつかの要素を選び, a_i をa_i % k に変化させる. その際いくつ選んだかに関わらず コスト2kを払う
必要な最小コストはいくらか.
1 <= a_i, b_i, N <= 50
解法
a_i から a_i % k にコスト2kの有向辺があるグラフを考える.
すると, いくつかの辺を選び,全てのiについて a_i -> b_i のパスが通るようなグラフを構築する最小コストを求める問題に帰着される.
全ての a_i -> b_i について最短路を求め, そこで使っている最大の辺を考える(このコストを2kとする)
1 + 2 + .. + 2k-1 = 2k - 1 < 2k から,他の最短路に用いる辺の全てのコストの総和よりも大きいので,
この辺を使わずに a_i -> b_i のパスを通すことが最適であることは有り得ない.
(自明だが,もしそのようなパスが存在するならばそれが最短路として出されている)
つまりこの辺はグラフの構築に必ず必要であることがわかる.
同様にして上から(辺のコストが高い順に)その辺が必要かどうかを見ていけばいい.
具体的には必要な辺を記録しておいて,その次の手順に進むときにはその辺をコスト0の辺として追加し再び最短路問題を解いていく.
最短路はWarshall-Floydで解けるためO(503), それを辺のコストの数だけ繰り返すためO(504)となる.
メモ
最短コスト求めてor取ればいけるのでは,と思ったがいけなかった(全ての最短路を構築するのは最適とは限らない)
自分の直感にこだわりすぎて解けなかったのでもっと考察力上げねば..
コード
AGC 022 B - GCD Sequence
問題概要
サイズN, 各要素が30000以下の次の条件を満たす数列を求めよ.
- 全ての要素のgcdは1である(全ての要素が互いに素ということではない)
- 全要素の和をSとして,全てのiに対して gcd(a_i, S-a_i) != 1
解法
gcd(a_i, S-a_i) != 1 <-> gcd(a_i, S) != 1
それぞれ二つの異なる素数x,yを因数に含む二つのグループから数列を構成することを考える.
{x,2x,3x,...} + {y,2y,3y,...} (もし等しい要素ができてしまった場合は省く)
x,yは異なる素数だから全てのgcdは1となる.
次に二つ目の条件を考えると, {x,2x,3x,...}の和がyの倍数に,{y,2y,3y,...}の和がxの倍数になれば
S=0 mod xyとなり,全ての要素について条件を満たすことがわかる.
また制約から考えるとx=2,y=3でなければならず,実際に30000以下では |(2の倍数)or(3の倍数)| = 20000である.
よって,
(1) 3,6,9,12,15,... を和が偶数になるように,
(2) 2,4,8,10,14,16,...(偶数)(3の倍数) を和が3の倍数になるように並べれば良い.
(1)で和のmod2について注目すると,+1,0,+1,0,..から,(個数) = 0,3 (mod 4)がわかる.
(2)も同様にmod3で+2,+1,+2,+1,...から, (個数) = 0 (mod2)
よって奇数であれば 5 -> 3+2, 7 -> 3+4, 9 -> 7+2, 11 -> 7+4,..
偶数であれば 6->4+2, 8->4+4, 10->8+2, 12->8+4,...
と個数を振り分けていく.
上限が30000なので,(1)の個数は10000以下であることに注意する.
個数がわかればその個数分だけ出力していけば良い.
このやり方ではN=3,4だとできないのでそこはサンプルケースを埋め込むことにも注意する.
メモ
考察があやふやなまま実装してしまったので,N=19999,20000あたりのケースで死んだ.
また,2グループに分けるところにたどり着くまでの考察も致命的に遅かった.
制約からのエスパーもできるべきぐらいのわかりやすさだったかなと思う.
コード
ARC 073 E - Ball Coloring
問題概要
N組の計2N個の整数x_i,y_iを赤/青に分けていく.
(Rmax - Rmin) * (Bmax - Bmin) を求めよ.
1 <= N <= 2*105, 1 <= x_i,y_i <= 109
解法
全体のmax,minであるma = max_i(max(x_i,y_i)), mi = min_i(min(x_i,y_i) は必ずR/Bに塗られているため,
Rmax = ma or Bmax = ma と, Rmin = mi or Bmin = mi が成り立つ.
よって以下の2通りに場合分けして良い.
1. Rmax = ma , Rmin = mi
2. Rmax = ma , Bmin = mi
これは貪欲とかで解ける.
簡単のために x[i] < y[i] として, xの昇順に並べておく.
1.は minimize( Bmax - Bmin) であり, 最初xを全てBにし, 小さい方からRに塗ってその分のyをBに加えていけば良い.
公式解説とかこことかが詳しい.
2.はminimize(ma - Rmin) * (Bmax - mi) であり,
これはma >= Rmin と Bmax >= mi から maximize(Rmin) & minimize(Bmax) すれば良いので,
大きい方をRに, 小さい方をBに加えていけば良い.
自分が少しハマったのは以下.
- ma,miのペア ma = x[argma] である場合の y[argma] とかの処理がめんどくさい
- maが複数ある場合どれを取れば良いのか
でもこんなものは無視していいと相場が決まっている(ほんとか？)
まず2.について,大きい方をRに,小さい方をBにしていくと自明にmaはRに,miはBになる
x[i] = y[i] = ma みたいな場合も確実にどちらにもmaが含まれるので考えなくて良い.
よって2.はどれがma,miであるかを考えずに処理していっても大丈夫
次に1.について,正直に処理するならmi=x[0]を除くxを全てBに加え, y[0]だけをBに加える必要がある.
しかしこれは, 最初にxを全てBに加え,小さいものを一つずつ交換していく手順で解けば1回目の操作でmi=x[0]はRに加えられるので問題ない.
また,途中で ma = y[argma] を x[argma]と交換してしまい, Rmax = ma でなくなることもあるが, これも無視して Rmax = ma で計算して問題ない.
なぜならこれ以降ではRmin = mi, Bmax = ma であり,2.の場合で計算していることになるから.
これ以降の計算では最適解よりも大きい値が得られ,minを考える上で影響がない.
よってma,miのペアを無視して計算していいことがわかった. するとどのma,miを取れば良いかという問題もなくなり2個目の問題も解決した.
メモ
難しかった. 数列の操作で最適化する問題なかなか慣れない.
コード
ARC 093 E - Bichrome Spanning Tree
問題概要
N頂点M辺の重み付き無向グラフと整数Xが与えられる. この辺を2色に塗っていく.
次の条件を満たす辺の塗り方の数をmod 1e9+7で求めよ.
- 2色どちらの色も含む全域木が存在して,そのような全域木の最小コストがXである.
1 <= N <= 103, 1 <= M <= 2*103, 1 <= X <= 1012
解法
全域木の集合を考えながら問題文を噛み砕いていくと条件は以下のようになる.
(1) 単色でない(2色どちらも含む)コストXの全域木が存在し,
(2) 単色でないコストX-1以下の全域木は存在してはいけない
(2)はつまり,コストX-1以下の任意の全域木に含まれる任意の辺は同じ色であるということになる.
ここである辺を含む最小全域木のコストはその辺を最初に使って,それから他の辺を小さいものから繋げていけば良いから,
a[i] := (全域木のうちで辺iを含むものの最小コスト) は O(M2 * logM)で求められる.
f(x) := (aがx以下の辺が全て同色であるような塗り方) とすると,
num = aがx以下の辺の数として,
num = 0 => f(x) = 2M
num!= 0 => f(x) = 2 * 2M-num = 2M-num+1
(2)を満たす塗り方の数はfを用いて表せ, f(X-1) となる.
そのような塗り方の中で,(1)を満たさない塗り方を考える.
これは a[i] = X であるような辺も X-1以下の色と同じに塗っている場合となる.
そのような塗り方の数は f(X) となるから,答えは f(X-1) - f(X) となる.
メモ
解けなかったので解説放送を見た. 日本語が難しい.
コード
ARC 083 E - Bichrome Tree
問題概要
1が根であるN頂点の根付き木が与えられる.
また数列{x_i} (i=1..N) が与えられる.
木に白/黒と非負整数を割り振り,自身を含めた子に含まれる自身と同じ色の頂点の数の総和がx[i]であるようにしたい.
そのように割り振ることはできるか.
解法
実験をして見ると頂点uについて,自身を含むuの子の白/黒の総和は,1つはx[u]であり,
またもう一方は最小化するのが最適であることがわかる.
そのもう一方の数をa[u]と置き,子の集合をC[u]と置こう.
c ∈ C[u] に色を割り振るとは,x[c],a[c]のどちらかを白の総和として,割り振らなかった方を黒の総和として割り振っていくことになる.
a[u]はどちらの色の総和としても構わないので,白の総和だとしよう.
a[u]を最小化するには黒の総和(=Bとする)を最大化して, 自身を黒のx[u]-Bとすれば良い.
この時, a[u] = sum_(c∈C)(x[c]+a[c]) - B となる.
ところで,x[c]/a[c]のいずれか丁度1つを足していった和というのはDPでできる.
特にbitsetを使えば簡単にできて, dp[i] := (iが和としてできるか) として,
初期化 dp[0] = 1
遷移 dp = (dp << x[c]) | (dp << a[c])
でできる.
これを根からDFSして各頂点に対してやっていけば良い.
計算量は毎回O(NX)のDPをしていてO(N2 * X)に見えるが,
実際,各頂点が子としてDPで使われるのは高々1回なのでO(NX)となる.
仮にO(N2 * X)としてもbitsetで1/64になるので十分間に合う.
メモ
どちらかだけ足すDPをすっきり書くのに時間がかかった.
