AOJ埋め6

AOJ

東京の某イベントに行こうか悩んだのですが，己の中の情熱が足りなかったため実家に帰省しました．

1248 The Balance

おとといくらいに手をつけた問題．
1次不定方程式 ax+by=d の解がそのまま天秤の載せ方に対応するので，これを解いて一般解列挙して条件(|x|+|y|が最小，これが同じならa|x|+b|y|が最小)を満たすものを求めればよいのかなー
…と思って拡張ユークリッドの互除法を引っ張ってくる．
一般解はどの程度列挙すればいいのか分からないけど，パラメータを-10000から10000まで動かせばいいんじゃね? 数万回ループするけどいいよね． 送る．


TLE. え，まじで…．


これでTLEとかどんだけテストケースあるのよ… 仕方ないのでもうちょっと考える．|x|+|y|が最小となる解があるのは，x=0 or y=0に近いところに限られるはず．(実際にグラフを描くと分かる)
これで調べるパラメータの範囲がかなり限られる．送る．WA．
えー，なんで，こんな簡単そうな問題なのに．コーナーケースとかないだろこんなの…


しかたないのでググって解法が書かれているページの通りに実装して送る．WA．
嫌になって放置する．


しばらく経って見返してみると，今までsubmitしていた問題番号が全部間違っていました．ウボァ．問題番号を訂正して送ると普通にAC．
試してないけど拡張互除法でも普通に通るんじゃないかな… たぶん．

1249 Make a Sequence

普通の実装ゲー．
ちょっとミスってWAを出してしまう．

1250 Leaky Cryptography

よくわからんけど下のビットから決めていけばいいんじゃね?
と思って適当に書いたらACもらえた．実はあんまりよくわかってない．

1252 Confusing Login Names

swapが結構ややこしいので編集距離DPの拡張とかは難しそう．サンプルにもあるけど，たとえば

xy -> yx (swap) -> yax (insert) -> yabx (insert)

みたいなのの扱いが難しいのではなかろうか．
問題文を読むと編集距離の閾値がd<=2と非常に小さいので，文字列s から編集距離2になる文字列をdfsで全生成させて，ほかの文字と比較するようにした．
全生成する際，insertやreplaceではa-zでいちいち別のパターンを作るのではなく，ワイルドカードっぽい扱いの文字列(たとえば*とか)で置き換えてやると生成される文字列の個数を減らせる．

1253 Dice Puzzle

探索．
最初R11〜R33までを6^9通り程度調べればいいのかなーと思ったのだけど，それだとコーナーケースがあるのでうまくいかない．
たとえば

0 0 0
0 0 0
0 0 0
0 0 0
0 0 0
0 0 0

みたいな場合，Tij，Fijにいつまでも自由度が残り続けるため，実際には不可能な盤面も生成されてしまう．


というわけで，T11〜T33，F11〜F33を，
T11→F11→T12→F12→T13→F13→T21→F21→…
といった感じの順番で全通り試すdfsを書いた．R11〜R33は確定できるようになったときに確定する．
これなら不可能な盤面は生成されないし，制約が結構強く働くので高速に探索できる．

1254 Color the Map

「え，まさか4色定理? ICPCも豪快だな〜」とか思ったのだけど与えられる地図に飛び地があったりして，
グラフが平面的ではないので4色定理は使えない．
これはビットを使うタイプのdpで，頂点集合Sに対して dp[S] := Sだけのグラフを考えた際に塗り分けに必要な最小色数として求めていく．
もしSの頂点がすべて独立であるなら1色で済むし，そうでないなら，Sを2つの部分集合S=T+Uに分けて，min{dp(T)+dp(U)} がそれになる．

1255 Inherit the Spheres

3次元球がいっぱい集まった変なオブジェをz軸で分断していく問題．
分断のポイントの候補は球のz±rとなる点と，2球の交点に限られる．
前者は明らかで，後者は2球のx,yの相対距離，zの相対距離を考えると平面上の円の交点に帰結できる．
分断のポイントの候補が分かったら，あとはそのポイントに沿って実際に分断して円のつながりをグラフにし，dfsで連結成分の個数を求めることができる．
結構実装が重くなってしまったのだけど，もっと簡単にやる方法が存在しそうな気がしなくもない．