問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1629&lang=ja 解法 底辺の y 座標を決めうったとする．これを \(y_l\) とおく． \(y \geq y_l\) をみたすある点 \((x, y)\) が正三角形の内部にあるための条件は，底辺の左端と右端の x 座…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1623&lang=jp 解法 点を合わせる順番と対応を全部試して探索するだけで解ける． 点を合わせるときは，直接合わせられる場合は直接合わせればよいし，そうでない場合は残りの2点のどちらか…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559 解法 マージテクだけで解ける． 最初に MST を構成しておく．MST に含まれない辺は自明． 以下MSTに含まれる辺についてコストを求める． MST 上を DFS で探索し，各部分木から外に生…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907 解法 \(w_i\) をそれぞれ逆にした文字列集合を \(\{rw_i\}\) とする． 最初にそれぞれをもともとのインデックスが分かるようにソートしておく． 以降は \(w_i, rw_i\) はソート済みで…