2015-03-20から1日間の記事一覧

Typical DP Contest B: ゲーム (動的計画法)

問題 B: ゲーム - Typical DP Contest | AtCoder 解法 お互いに最善を尽くす時、dp[i][j]の前の手はdp[i-1][j]またはdp[i][j-1]になっているはずなので、それで計算する。 コード import java.io.IOException; public class Main { public static void main(…

Typical DP Contest A: コンテスト (動的計画法)

問題 A: コンテスト - Typical DP Contest | AtCoder 解法 dp[i][j]:=i問目まででj点に到達できるかどうか、を保存しておき、dp[N][i]をカウントする。 コード import java.io.IOException; public class Main { public static void main(String[] args) { i…

SRM 653 Div. 1 Easy: CountryGroupHard

問題 TopCoder Statistics - Problem Statement色んな国から来たN人が1列に座っていて、同じ国から来た人は隣り合って固まって座っている。何人かに、同じ国から来た人数を聞いた。その情報だけで、まだ聞いてない人がどう答えるか当てることが出来るか。 解…

yukicoder No. 168: ものさし (Union-Find木)

問題 No.168 ものさし - yukicoder 解法 任意の2点間の距離(最低限必要になるものさしの長さ)を求めておく。それらをソートし、距離の小さい順に取り出していく。取り出した辺の始点と終点を結び、Union-Find木で結合しておく。点1と点N-1が同じ木になるま…