問題 おみやげがN個あり、それぞれvalue[i]の価値がある。2人におみやげの数が同じようになるように分けた時、価値の合計値が同じになるように分けることは可能か判定せよ。 解法 DPで[N/2][sum/2]の状態に到達可能か判定する。 コード public class FoxAndS…

問題 D: 高橋くんとマラソンコース - AtCoder Regular Contest 035 | AtCoder 解法 チェックポイント間の経路数はものすごく大きくなるのでlogで保存しておく。クエリに対してチェックポイント間の経路数の和を返すので、和のセグメント木を作っておく。 コ…

問題 C: アットコーダー王国の交通事情 - AtCoder Regular Contest 035 | AtCoder 解法 まず最初のグラフでワーシャルフロイトして2点間の最短距離を出しておく。新しい道路が建設されるたびに最短距離マップを更新する。この際に、以下のようにするとで更新…

問題 Treasure Hunt | Aizu Online Judge 解法 問題の条件的に愚直にやると最悪ケースで回くらいループを回すことになるから、累積和をとったりとか色々やらなきゃいけないはずなんだけど、なんか通っちゃった。 コード import java.io.IOException; import …

問題 Tiles are Colorful | Aizu Online Judge 解法 叩けるマスを探す→叩いてみる→ポイントになるなら消す→叩けるマスを探す→…の繰り返しでいけた。叩く順番は関係ない。 コード import java.util.PriorityQueue; import java.util.Scanner; public class Ma…

問題 Railroad Conflict | Aizu Online Judge 解法 書くだけ。線分の交差とかはライブラリにしておくと便利っぽい。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Collections; public class Main { public static voi…

問題 No.160 最短経路のうち辞書順最小 - yukicoder 解法 http://yukicoder.me/problems/417/editorialグラフ問題を少しずつ頑張りたい。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.Prior…