UAPC 2011 - y_mazun’s blog

でました。

6ACで12位だとおもってたら13位だった。Bの修正の影響だろうか。まあどちらにしろなかなかの成績。
最後の20分で2問通せたのが大きかった。

全体的な感想としては、アルゴリズムの問題より、実装系の問題が多くてちょっと好みとは外れた感じだった。

A: It's our delight!!

やるだけ

B: Watchin' TVA

どうやら出題側でミスがあったらしい。
Greedyに番組を見ていけば良い。やるだけ。

C: Yanagi's Comic

ちょっとサンプルが理解できないので飛ばした。

D: The House of Huge Family

グラフを２つ以上に分割するための最小コストを求める問題。
ちょっと勘違いしたせいでWAの嵐。
そもそもコストが負の枝は削除。
枝の個数が、頂点の個数以下なので、削除する枝は多くとも２本なので全探索。

F : Cutting a Chocolate

面積と、アーモンドの位置(どこに属するか)を求めるところまではライブラリゲー。
あとは尺取虫しながらアーモンド最小個数を更新していけばいい。

アーモンドの位置を全探索していたら間に合わなかったので、二分探索した。二分探索に慣れていなかったので時間がかかってしまった。要練習。

(追記：図形が台形ないしは三角形にしかならないので面積は簡単に求まりそう。アーモンドの位置も直線の上か下かが分かればいいので、ライブラリ無くてもそこまで難しくはなさそう)

H : Squid Multiplication

数列の最初の２つは a0 * a1、a0 * a2、数列のｎ＋１番目の要素は a1 * a2 なので
sqrt( (a0 * a1) * (a0 * a2) / (a1 * a2) ) で a0が求まる。
double で求めて、誤差を(一応)補正するだけ。
あとは最初の n 個の要素を a0 で割れば全答えがでる。
最後にソートするの忘れてたせいですごく時間かかった・・・。

想定解法がこれと同じなのかは気になるところ。
最初の n + 1 個の要素以外捨ててるので・・・。

K : Rearranging Seats

ハルナちゃんキタ！これで勝つる！
実は今回一番簡単な問題。
縦か横が偶数なら上手く隣同士で交換すればできる。
両方奇数だと、多分ムリ。みんなACしてるしこれで通るだろうと思い、submit。通る。終わり。

他

よう分からん or 時間がなかった。