AOJ 800 solved

3ヶ月ほど前、AOJで800 solvedが目前になったため、

ということをしたら(案の定)グロい問題がたくさん集まりました。

識者のみなさんからは

というありがたいお言葉をいただきました。せっかくなんとかプロコン人生を終わらせずに済んだので、解いた問題達の解説を書き残しておきたいと思います。

795問目: AOJ 1151 くるくる

多角形に棒が1点で内接しているので、その点を中心に回転させ、次に多角形に接した点を新たな中心にしてさらに回転させ……、というのを一定の角度行ったとき、最初に触れていた棒の端点はどこにあるか?という問題。

解法が「回すだけ」で有名な問題。

確かに回すだけなんですが、言うまでもなく回すのが難しい。

どのくらい回転させるのかを、線分の長さを半径とする円の内部にある頂点、あるいは多角形の辺と円との交点、のうち、中心となる端点からもう一方の端点へのベクトルとのなす角が最も小さくなるものから選ぶ、というのが基本的な方針。

複数同じ角度になる頂点がある場合、最も中心から遠いものを選ぶ必要がある。

線分が多角形の辺と共通部分を持つ状態があるというのが結構めんどくさい(例外処理しないと常になす角が0で最小になり、動けなくなるので)。

最終的には計算誤差によりacosに1よりわずかに大きな値を入れてしまいnanが返ってくるバグにずっとやられていた。

 

796問目: AOJ 1523 Cone Cut

円錐と内部の点Pを通る平面が与えられるので、その平面で円錐を切断し、分断された2つの立体の体積を求めよ、という問題。

今回の問題の中で一番良心的な問題だった。amylaseさんが仏に見えました。

制約を見ると、平面は絶対に底面を通ることはないため、切断された上部の立体は必ず斜楕円錐になる。

なので、斜楕円錐の底面の長辺・短辺・高さがわかれば簡単に計算することができ、これらは少し数学を頑張ると比較的簡単にわかる。

最初の立体が割と自由に与えられるのが少しめんどくさいので、最初に頂点が(0,0,h)、Pが(0,y',z')になるように回転させてやると楽になると思います。

 

797問目: Secret Operation

長方形の障害物がある2次元平面上で、2人の人のタイムスタンプ付き軌跡データが与えられる。Aさんは進行方向から左右45°、距離R以内の範囲にBさんがいるとき、その間に障害物がなければ目視できる。AさんがBさんを目視している時間の合計を求めよ、という問題。

実は出力に対する許容誤差がゆるゆるなので、時間をEPSずつ進めていって、実際に見えているかどうか判定するだけでも解ける。

これで一度通したが、ちょっとかっこ悪いのでまともにやる方法で解き直した。見える/見えないが変わり得るイベント点を列挙する方法。

イベント点は、

  1. 2人の間の距離がちょうどRになる
  2. 相手と進行方向とのなす角がちょうど45°になる
  3. 相手と自分を端点とする線分にちょうど障害物が入ってくる = 障害物の頂点が乗る

というのがあり、これらは一緒に考えるとやばいが、独立に考えると頑張って方程式を立てて解くことでわかる。

常に上記の状態を保つ=どのような解も方程式を満たすような場合は、イベント点ではないので気にしなくてよい。

イベント点が列挙できたら、時系列に並べて隣り合った時刻の中間の時間で見える/見えないを判定すればよい。

 

798問目: AOJ 2004 Data Center on Fire

火事になったN階立ての建物の各階から機器を運び出したい。火は一定時間で上下に隣接するフロアに燃え広がり、また別の一定時間で焼け落ち、機器も無くなる。M台のエレベータが同時に通信しながら稼働し、焼失する前に機器を運び出す。全てのエレベータはまだ機器が残っているうち最上階を常に目指し、機器が運び出しor焼失すると、最上階を切り替え目標を変える。いくつの機器を何分で運びだせるか?という問題。

ぶっちゃけ頑張ってただシミュレーションするだけの問題だけど、問題文がひどすぎで、曖昧な部分が多すぎる。

とかいう有様で、データセットを落として来なかったら解けなかったと思う。

問題文がまともなら実装がちょっとめんどいだけ。

今回解いた中で唯一無二のクソ問だったと思う。

 

799問目: 全自動円形掃除機

多角形の部屋の中にルンバがある。移動して掃除できる面積を求めよ、という問題。

これが解法を考えるのに一番時間がかかった(常に考えてたわけじゃないけど2ヶ月くらいかかってる気がする)

解法は、とりあえず近くの壁にぶつけてから壁に沿って動かす。

このとき、壁や角に接した点からなる多角形の面積に、円弧の部分の面積を足せば答えがでる……けどつらい。

基本的に、壁にぶつかるor壁の端につくまで直進させる関数と、1点(=部屋の角)を中心にルンバを回転させる関数を作って、ぶつかる度にどちらを使うべき状況かを判断してシミュレーションする、という感じの方針で書いた。

最終的には計算誤差によりacosに1よりわずかに大きな値を入れてしまいnanが返ってくるバグにずっとやられていた(まるで成長していない)。

 

800問目: Hashigo Sama

はしごグラフという特殊な形をしたグラフを木状に接続してできたグラフが与えられる。2彩色を考えた時、同じ色からなる連結成分の大きさがどれもkを超えないような彩色は何通りあるか、という問題。

最初、木状に接続しているという条件を見落としていて、最悪ほぼグリッドグラフじゃんやばすぎ、となっていた。

木状に接続しているという条件を考えると実は与えられたグラフは外平面グラフになっているため、木幅は高々2となる。

よって、木分解してその上でDPを設計するFPTが考えられる。

木分解&Niceな木分解への変換については、

http://www-imai.is.s.u-tokyo.ac.jp/~imai/lecture/GraphMinor.pdf

を参考にさせてもらった。ありがとうwata神。

グラフ全体の頂点数をN、木幅+1=バッグの最大の大きさをwとおくと、

DPのキーは、(1)木分解上のバッグのID  O(N)通り、(2)バッグに含まれる頂点の塗り方 2^w通り、(3)頂点の接続関係5通り、(4)各頂点が含まれる連結成分の大きさ k^w通りとなる。

DPの情報伝播は1ノードで最悪時 k^wくらいかかるので、全体で O(2^w k^{2w} N)くらいになって、N=2000, k=8, w=3を代入すると約 4×10^9となりやばそうだが、接続する頂点同士は同じ色にならなければならない、などの制約から実際の探索空間はもっと小さくなる。

……と思ったけど実際はだいぶやばかったので、いろいろと枝狩りや定数倍高速化的な何かを頑張った。

 

おわりに

つらかった。