Regionals 2010 :: Asia - Hangzhou - 競技プログラミング+αなブログ

日曜日に時間があったのでやった練習。
http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=866
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=385
BCFHJは解けた。
Dはあと1箇所のミスだった。
Gはぎりぎり解けるレベル。
Aは無理でIはもっと無理（中国のサイトのコードを解読して少し理解した気になった）。
Eは知らない。
中国の地区予選の問題はちゃんとした（英語の）解説さえあれば素晴らしいのに・・・。

A - 4833 - Naughty fairies

問題

Aを以下の操作でBにするときの最小操作回数を求めよ。

1加算
1減算
2倍

制約

解法

多倍長（/2,%2,-,+1,+2,<とか）が必要。
B=AならBの2進数表現を考えてDP。
Bの2進数表現において、上位iビット目(0-origin)をB[i]で表し、上位iビットをB[:i]で表す。
例えば、
B = (10010110)
のとき、
B[:3] = (1001)
となる。
dp[i][j] = AからB[:i]+jを作る最小コスト
とする。jは0か1。
このとき、

B[i] = 0ならば

- dp[i][0] = min(cost(A,B[:i]), dp[i-1][0]+1, dp[i-1][1]+2) …　(i)
- dp[i][1] = min(cost(A,B[:i]+1), dp[i-1][0]+2, dp[i-1][1]+2)

B[i] = 1ならば

- dp[i][0] = min(cost(A,B[:i]), dp[i-1][0]+2, dp[i-1][1]+2)
- dp[i][1] = min(cost(A,B[:i]+1), dp[i-1][0]+2, dp[i-1][1]+1)
ここでcost(x,y)はxからyを加算か減算だけで作るときの最小コストで、cost(x,y) = |x-y|。
例えば(i)について解説すると、AからB[:i]を作るとき、

加算か減算だけ使ったのがcost(A,B[:i])
B[:i-1]を作ってからB[:i]を作ったのがdp[i-1][0]+1 （2倍で作れる）
B[:i-1]+1を作ってからB[:i]を作ったのがdp[i-1][1]+2　（1減算して2倍で作れる）

j=1が必要な理由は、A=(1),B=(11111)とかを考えると分かる気がする。

B - 4834 - Prison Break

二分探索＋DPな問題。
DPはハミルトン閉路+ベルマンフォードみたいな感じで解いた。
大きめに見てlog(15^2)*2^14*14^3=3億くらいのオーダーになった。

C - 4835 - To Be an Dream Architect

n*n*nのブロックから指定された列を取リ除いていき、取り除かれたブロックの数を答える問題。
x軸についてをカウントし、
y軸についてを重複に注意してカウントし、
z軸についてを重複に注意してカウントする。
set使った。

D - 4836 - Gomoku

問題

五目並べの現在の盤面(14*14)が与えられるので、1手目で勝てるか、2手目で必ず負けるか、3手目で勝てるかを判定せよ。
（実際はもう少し細かくてだるい。）

制約

すでに5個並んでいる事はない。

解法

ある(x,y)に置いた時に勝ち状態になっているかどうかを重くない処理で判定する関数を作っておく。
自分は判定をそれぞれ1重(2重)ループ、2重(4重)ループ、3重(6重)ループで行ったが落とし穴もあってかなりだるい。
楽な解法を紹介する。
ある盤面Zにおいて、iさんが石を置いたら勝てる箇所の数をcnt(i,Z)とする。
また、与えられた盤面をA, 自分をm,相手をoとする。
このとき

cnt(m,A)>=1なら1手で勝てる。
cnt(o,A)>=2なら2手で負ける。
Aに加え(x,y)に石を置いた盤面をBとするとき、cnt(m,B)>=2かつcnt(y,B)==0なら3手で勝てる。

この解き方は賢い。

E - 4837 - Gunshots

F - 4838 - Rotational Painting

問題

自己交差のない多角形が与えられる。
この多角形には一様の厚みがあると考える。
これを与えられる多角形の面が見えるように地面に置くとき、安定する起き方は何通りあるか。
ここで安定するとは、物体の重心を地面に射影した点が、地面ついている点が成す区間に真に含まれていることを意味する。

制約

3<=頂点数<=50000

解法

置き方の候補は、多角形の凸包における１辺を地面につくように置く場合のみである。
それを全て試す。
なお重心は頂点の平均ではないので注意。

G - 4839 - Traffic Real Time Query System

問題

ノード数N、エッジ数Mのグラフが与えられる。
また、Q個の(xi,yi)がクエリとして与えられる。
それぞれのクエリに対し、辺xiから辺yiにグラフの辺上を辿って行く時に必ず通らなければならないノードの数を答えよ。

制約

解法

必ず通らなければならないノードとはすなわち関節点である。
すなわち、二重頂点連結成分の間を移動するとき、必ず通らなければいけないノードの数は1増えることになる。
そこで、グラフを二重頂点連結成分分解し、連結成分がノードとなるような森（連結とは限らないので）を構成する。
ここで森のエッジの重みは全て1である。
この森において、xが属するノードとyが属するノードの最短距離を求めればそれが答えになる。
森における最短距離のクエリに答えるにはLCAを使う。
情オリっぽい問題？

H - 4840 - National Day Parade

重要な制約を見落とさなければ簡単。
全部試してソートされたものを割り当てていくだけ。

I - 4841 - Searchlights

問題

n*mのセルがある。
各セルには最大レベルがa[i][j]が設定されている。
ある値xを選んだ時、a[i][j]>=xのセルはレベルをxに設定され、それ以外のセルはレベルが0に設定される。
このとき全てのセルが次のどちらかの条件を満たすような最小のxを求めよ。

レベルが１以上
同じ行、同じ列それぞれで距離x-1以内にレベルがxのセルがある。

そのようなxがない場合は、"NO ANSWER!"を出力せよ。

制約

1<=n<=100
1<=m<=10000

解法

擬似コードで解法を示す。

x = 1
for (i,j) in a[i][j]が小さい順 {
    if (a[i][j] >= x) {
        答えはx
        break
    }
    以降セル(i,j)は”空き”と考える
    if (セル(i,j)の空きを埋め合わせることの出来るセルが無い) {
        失敗
        break
     }
    セル(i,j)が空きとなったことにより出来た空きの区間の長さでxを更新する
}

以下擬似コードの解説をする。
xは今見てる中で最低限必要なレベルである。
今見てない全てのセルのレベルをxに設定出来るなら、レベルxは問題の条件を満たす事ができる。
a[i][j] >= xでないならば、セル(i,j)は最低限必要なレベルに設定することができないので、レベル0を設定する（”空き”にする）しか無い。
レベルを0に設定するということは、i行とj列それぞれあるセルでセル(i,j)を”埋め合わせ”しなければならない。
ここで”ある”セルは、セル(i,j)から最寄りの空きでないセルを考えればいい。
最寄りの空きでないセルが空き区間を埋め合わせるとき、最低でどれほどのレベルが必要かを考え、xを更新する。
空きでないセルがその行／列に無い場合、空きを埋め合わせることができなくなり、NO ANSWERとなる。
では、最寄りの空きでないセルをどうやって効率的に調べるか。
これには、各セルpに対して、p.u,p.d,p.l,p.rというプロパティを考える。
p.uはセルpの上で最寄りの空きでないセルのIDが入る(ない場合は-1)。
他も同様である。
これらのプロパティを用いることで、１つのセルが空きになるときO(1)で空き区間の大きさを求められる上に、プロパティの更新もO(1)で行うことが出来る。
このとき既に空きになっているセルのプロパティを更新する必要はないことに注意する。

J - 4842 - Infinite monkey theorem

普通めのDP。