AOJ埋め14

1日中粘っていた割には思い通りにいってない.ココロオレル.
1日中粘っていたから駄目だったのかもしれないけど.


今回は去年の夏合宿のセットをやった.
解法は一応全部知っているし,今なら9問くらい解けるんじゃね? と思って挑んだけどそうはいなかなった… やはり重いものが多いしそう簡単にはいかないみたいだ.

2165 Strange String Manipulation

基本的にループ回して全部調べるだけなんだけど,計算誤差に気をつけないと痛い目に遭う.
去年は計算誤差の気をつけ方を知らなくてWAを量産した記憶がある.

2166 Erratic Sleep Habits

DPなんだけど,「いつでも無水カフェインを取ることができ,取ると睡眠サイクルをリセットできる」というのが日付の変わる瞬間だけ影響があるのか,それとも取った瞬間に影響が出て昼夜逆転とかもできるのかがよくわからなくて迷った.
実際は前者のほうになるしそれならあまり深く考えることも無いのだけど,後者だと捕らえてしまうと計算量的に難しくなってあれ? となってしまい,時間を食ってしまった.
本番ならチームメイトに投げているところでしょうか….

2167 Find the Point

幾何.n<=2 ならManyだし,n>=3 なら適当な場合分けで有限個の点に絞れるのでそれを見てやればいい… のだけど.
点の絞込みが結構だるい.角二等分線やら,平行な2つの直線の中間に位置する直線やら.
妙にWAが出ていらいらしたので本番のデータセットと照らし合わせながらやったところ,どうやら計算誤差で死んでしまっていたみたい.
EPS=1e-9くらいでやっていたのだけど,それだときつすぎるのか1点に絞り込めるはずのところがNoneになってしまったり….
しょうがないので色々EPSをいじってEPS=1e-8とかにしてやったら通った.
ちょっと,これはどうしようもないというか理不尽というか…
本番で出くわしたらどうすりゃいいんだろう.ちょっと思いつかない.
普段使う計算幾何ライブラリを誤差の少ないものにするとか? はあるだろうけど限界もあるしなぁ.
計算誤差で死んだのは(実は)初めてなのでかなり動揺しました.

2168 Luigi's Tavern

最大流にうまいことモデル化できる妙な問題.去年一応解いたものではあるけど,自分ひとりでは思いつかなかっただろうなぁ….
グラフが結構複雑で刺身にタンポポを載せるような作業感があった.
容量をミス(∞にすべきところを1としていた)っているのに気づかず時間がかかった.

2169 Colored Octahedra

8!列挙して辞書順で最小のものを取る〜 とかする.
計算量はどう見ても8!*24なのに最初なぜか8^8*24とかと勘違いしていた.もうなんか駄目だ….
8!の列挙は何も考えずにdfsを組んだのだけど,後々考えてみればnext_permutation使っても良かったなぁと思わなくもない.

2170 Marked Ancestor

クエリをすべて逆順に見てやれば,Markは2つの木の併合,Queryは木における代表元の出力,ということで,UnionFindを使ってごにょごにょする.
クエリを余分に付け足してやって,(逆から見た)初期状態はすべてのノードがMarkされていると仮定するとやりやすい.
配列の確保が不足していたり,1度Markしたノードを再びMarkする処理が来たときを考慮していなくてWA|REを何度か出す.

2171 Strange Couple

交差点に来るたびにランダムに道を選んでドライブするヘンなカポーの問題.まだ解けてない.
期待値について式を立てると1次連立方程式になるからそれを解くだけ… なんだけど…
まずサンプルから合わない.というかそもそも手でやってもサンプルが合わない. (あれ間違ってない? 答え8.5じゃないの…?
しょうがないので実際のデータセットと照合してやると,大体は合っているのだけど,たまにの値になってしまうということが発覚.
なんでになるのかよくわからないし,コード見ても駄目なところが分からないため放置.
これはできるだろうと思っていただけにショック.

追記:

翌朝見直したらACもらえた.ガウスの消去法のピボット選択のところが間違っていたげ.
サンプルは相変わらず合わないし,多分あのサンプルは間違っています.正しい値はおそらく8.5000です.

2173 Wind Passages

最大流=最小カット=(図形の性質的に)ダイクストラ というイカした問題.
vectorの初期化忘れとかしょーもない理由でTLE何回も出してしまう.嫌になる.