http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4872 問題 点がN個あるので辺が交差しないユークリッド最小全域木を求めよ。 1 解法 クラスカル法かプリム法を使って最小全域木を求めるだけ。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4871 問題 高さの違う高層ビルをN個建てる。ただし、i 解法 DP[n][pos]を考える。DP[n][pos]はn番目までのビルを置いたときにhi

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4870 問題 区間がN個あるジェットコースターがある。ある人がこのジェットコースターに乗るのだが、怖さの閾値Lを越えない範囲でなるべく楽しみたい。ある区間で目を開けているとFi楽し…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4869 問題 長さNの数列がある。そのsubstringの総和の最大値を求めよ。 1 解法 左端から見ていって、総和が負になったら0にもどす。これをしていって最大になった物が答え。

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4868 問題 leading 0が許された数値がある。その数値を回文にするためには最小いくらの数値を足さなければならないか？ 2 解法 左側半分を固定してそれに合わせるように右側半分を足して…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4867 問題 すべての要素が1か0で構成されたN*M行列がある。その中の正方形で全て1で構成される最大の正方形の辺の長さを求めよ。 1 解法 ヒストグラムの長方形の最大面積を使って求めた…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4866 問題 三角形がある。AB,BC,CAからθずらした直線を考える。θを適切に設定した時にその3っつの直線は一ヶ所で交わる。その場所を求めよ。 解法 頑張って手計算するか三分探索で求める…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4865 問題 N*Mの行列がある。各成分は[0,100]の値になっているか空欄になっている。各列の和と各行の和を与えるので元の行列を復元せよ。ただし、値が一意に定まらない箇所は-1と答えよ…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4864 問題 f(x):=xの2進数表記で1の個数という関数を考える。Ni=f(Ni-1)とするとこの数列は1に収束する。このとき、初めて1になったiをKとする。[LO,HI]の区間でK=Xとなるような数値は何…

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4863 問題 Nチームが参加しているコンテストが開催された。各チームに風船をK個配りたいのだが、部屋Aからの距離はDA、Bからの距離はDBとなっている。各部屋には風船がA個、B個ある時、…

PetrとかEgorとかRAVEmanとかと一緒の部屋 300 Hanakoですか… 問題の意味を理解するのに結構時間がかかった 任意の3っつを選んでどんな順番でも同じものになればいいんじゃないの？ 書いた。サンプル通った。サブミット。 500 サイコロを転がす問題 部室のサ…