Asia Regional Contest

すずかけ台までは電車で往復2時間近くかかるのでコンテストの問題を印刷して電車の中で考えてた．で今日実装してたけど紙の上で考えるのと実際にやるのはずいぶんと違った．

電車で思った感想

• A やるだけ
• B やるだけ
• C DP
• D 未知のパラメータが6つあって，拘束式が3つあるからとりあえずパラメータを3つ固定すれば200*200*200ぐらいでいくんじゃないかなと思った．
• E グラフさえ作ればあとは簡単．
• F エッジの重みでソートして，尺取り虫っぽく．
• G 探索．
• H 文字列パースとかやりたくないなと
• I よくわかんないけど凸だから最急降下とかで解けるんじゃない．
• J わからない

実際に実装しての感想

• A やるだけ
• B やるだけ
• C DP
• D 最初はXa,Ya,Xbを固定して，残りの座標を求めて高さを求めるという方針でやろうと思ったけど，式がわりとひどいことになったので，Paを決めた時に|P1Pb|が決まり,そのとき格子点上のPbの候補は200程度しかなくて，Pbを決めると|P2Pc|と|P0Pc|が決まり，これからPcが一意に定まるので，あらかじめ距離と点の関係のマップを作っておくとPa,Pb,Pcの候補を列挙できる．3点が与えられればあとは連立方程式をとくと高さがもとまる．なんかサンプル入力が重なりのチェックとかしなくても通るようなな入力なのでちょっとあってるかどうかが自信はない．あとz=0のときの精度が気になる．
• E グラフを作れば簡単なんだけどグラフを作るのがめんどくさい．まだやってない．
• F 最小の枝を固定して，重み順に点をどんどんUnion-Findをつかってマージしていって連結になったらそのときの最大と最小の差をメモっておく．あとは最小の枝をどんどん動かしていけばO(E^2 * A(n))ぐらいで行く(A(n)はアッカーマン関数の逆関数，ようはUnion-Findの計算量)．
• G 実は状態数は壁の位置の制約とかからそんなには大きくならないらしい．考えてた時は状態が256^3で状態から遷移できる状態が5^3ぐらいあるから両側探索しなければならないかと思ったけど別にしなくても通るらしい．*1
• H 思ってたよりはるかに簡単．BNFをよく見るとexpressionだけ再帰的に見ればよくて，評価中にバグがあったら例外をなげるという方針でやればいい．
• I 一応sampleは通るコードは書いたけど，最急降下でどこへ進むかの方向を決めるのかが360度を適当に区切るすると精度か時間のどっちかが間に合わなくなる．
• J 連立方程式をとけばいいらしい．

まあなんか考えたときにはうまくいきそうでも実際にはうまくいかなかったり逆に考えた時には難しいかなと思ったけどやってみるとそうでもなかったりしてなかなか面白いなと思った．

*1:PKUで出るときは絶対に通らないようになってるけど