Regionals 2011 :: Asia - Dhaka
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=518
Binary Matrix
問題
要素が1,0のみのN×M行列が与えられる。
隣接する要素同士をスワップするという操作のみ認められる。
ただし、1行目とN行目のスワップや、１列目とM列目のスワップも認められる
全ての行の1の数が等しく、全ての列の1の数が等しくなるようにしたい。
どちらも可能か、行のみ可能か、列のみ可能か、どちらも不可能か、
また、そのとき最小で何回のスワップが必要かを求めよ。
制約
2 ≤ M, N ≤ 1000
解法
行と列は別々に考える。
i行の1の数をaiとすると、aiから1ずつ隣接するajのどちらかに値を移動することが出来るときaiの値を等しくするという問題になる。
これは最小費用流で解くことが出来る。
中央値解法
http://one-problem-a-day.blogspot.jp/2011/08/uva-11300-spreading-wealth.html
sumをaiの合計とする。
sumがnで割り切れなければ、aiを同じ値にすることはできない。
割り切れる時を考える。
per = sum / n とする。
x(p,p+1)を、pからp+1に移す値とする(mod n)。
x(i-1,i) - x(i,i+1) = per - a[i]
が成り立つ。
A[i] = per - a[i]とすると
x(0,1) = A[1] + x(1,2)
x(1,2) = A[2] + x(2,3)
.............
x(n-2, n-1) = A[n-1] + x(n-1, 0)
x(n-1, 0) = A[0] + x(0, 1)
右辺を変数x(n-1,0)だけで表現すると、
x(n-1, 0) = 0 + x(n-1, 0)
x(n-2, n-1) = A[n-1] + x(n-1, 0)
x(n-3, n-2) = A[n-2] + x(n-2, n-1) = A[n-2] + A[n-1] + x(n-1, 0)
..............
x(1,2) = A[2] + A[3] + ... + A[n-1] + x(n-1, 0)
x(0,1) = A[1] + A[2] + A[3] + ... + A[n-1] + x(n-1, 0)
B[i] = 0 + A[1] + ... + A[i]
とする。
| x(0,1) | + | x(1,2) | + .... + | x(n-1,0) | が最小になるようにするには、 |
x(n-1,0)をB[0]...B[n-1]の中央値のマイナスにすればよい。
すなわち中央値をmedとすると、
| x(0,1) | + | x(1,2) | + ... + | x(n-1,0) | の最小値は |
| B[0]-med | + | B[1]-med | + ... + | B[n-1]-med | となる。 |
これは、min{|y1-x| + |y2-x| + ... + |yn-x|}を考えたとき、
それぞれの項のグラフを考えると分かる。
Candles
問題
0から9の数字プレートが1枚ずつある。
この数字プレートを使ってn個の数字を表したい。
数字プレートの他に+と書かれた特殊なプレートを使うことで、和として表すこともできる。
例えば12は、2+10, 3+9, 4+8, 5+7, 7+5, 8+4, 9+3, 10+2, 12 として表すことが出来る。
ここで例えば10は、プレート1とプレート0を並べて作ることが出来る。
n個の数字を表せるような数字プレートの部分集合で、要素数をできるだけ小さいものを求めよ。
制約
1<=n<=10
1<=表したい値<=100
解法
まず全ての部分集合に対して、表すことの出来る数字を全て列挙する。
表したい値が100までしか無いことに注目すると、表し方としては、
- 1枚のプレート
- 2枚のプレートを並べる
- 2枚のプレートの和
- 2枚のプレートを並べたものと1枚のプレートの和
- 2枚のプレートを並べたもの×2の和
の5パターンしか無い。
あとは、n個の数字を全て表せるような部分集合のうち要素数が最小のものを選べば良い。
前処理にsetを使ってO(2^n*n^4*log(n))
各テストケースに対してO(2^n*n)
Cards
問題
ジョーカー2枚入りのトランプをシャッフルしてデッキを作り、上から順にスートごとに分けて置いていく。
このときC枚のクラブ、D枚のダイヤ、H枚のハート、S枚のスペードが出るまでに置くカードの枚数の期待値を求めよ。
ただしジョーカーを引いたときは、そのジョーカーをある1つのスートに属するとみなして置く事ができる。
ここでジョーカーが属するスートは求めたい期待値が最小になるように決めるとする。
制約
0<=C,D,H,S<=15
Game of Connect
保留
Guards
問題
N×Nのフィールドがあり、2N個の丸を各行各列にちょうど２つの丸があるように配置する。
同じ行、同じ列の丸を線で結んだときサイクルがK個あるようにしたい。
このような丸の配置の仕方は難通りあるか求めよ。
制約
2 ≤ N ≤ 105, 1 ≤ K ≤ min(N, 50)
解法
dp1[n][k] = n×nのフィールドで、サイクルがkであるような配置の仕方
dp2[n][k] = (n-1)×nのフィールドで、既に2つの列には丸が（フィールドの外側で）配置されているとき、サイクルがkであるような配置の仕方
Packing for Holiday
やるだけ
Pair of Touching Circles
問題
W×Hのグリッドがある。
このグリッドに円を２つ書く。
円は以下の条件を満たす。
- ２つの円は接する
- ２つの円の共通部分はない
- 円の中心は整数座標
- 円の半径は整数
このとき、円の書き方の総数を求めよ。
制約
0 < H, W ≤ 1000
解法
整数cに対して、
mp[c] = √(a^2+b^2)を満たす(a,b)のリスト
を求めておく。
２つの円の半径に関して二重ループを回して、
円を軸に平行に置いたとき、ずらして置いたときそれぞれについて、場合の数を計算する。
１つの円を含む最小正方形にもう一方の円が完全に内包されることもあることに注意。
Treasure Hunt
問題
長方形領域に４人が落ちる。
長方形領域は（多分１点で支えられていて）最初バランスが取れているが、
４人が落ちたことによってバランスが崩れてしまうので、４人はバランスが取れるように移動する。
４人の移動量の総和が最小になるように移動したとき、４人の最終的な位置を出力せよ。
ただし４人の体重は同じ。
制約
解法
長方形領域の重心をG、４人の重心をOとすると、４人の重心をOからGに移動させれば良いことが分かる。
そこで、４人をベクトルOGだけ動かせば良い。
もしある人が長方形領域から外れてしまう場合は、その人は端まで移動させておいて、他の人でその分を賄うという感じでできる。
Truchet Tiling
https://icpcarchive.ecs.baylor.edu/external/58/5817.html
問題
図のようなmotifが２種類あり、R×Cのセルが埋められている。
各クエリで座標が与えられるので、その座標を含む領域の面積を求めよ。
制約
0 < R, C ≤ 100
1 ≤ Q ≤ 100
解法
１つのセルを、LEFT,CENTER,RIGHTという３つの領域にわけて考える。
Union-Findを用いて各セル各領域の接続関係を求め、同時に面積も足し合わせることで計算する。
各クエリに対しては、その座標がどの領域に含まれるのかを判定してUnion-Findで求めておいた面積を出力すれば良い。
O(RCα+Qα)
O(RCQ)も許されると思うのでBFSでも良いはず。
As Long as I Learn, I Live
問題文に書いてある貪欲グラフ探索を実装するだけ
