解法 SRM 636 Div. 1 Easy: ChocolateDividingEasy - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com以前全探索で解いた問題を2次元の累積和で解き直してみた。実行時間が 1979 ms から 468 ms になった。 コード import java.util.Arrays; public class C…

問題 Problem - C - Codeforces 解法 yukicoder No. 176 の解法がまるごと流用できる。yukicoder No. 176: 2種類の切手 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com コード import java.io.IOException; public class Main { public static void main…

問題 D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder 解法 0〜N-1と、N〜2N-1の2N個の街があると仮定する。 ノード数2NのUnion-FInd木を用意する。 xとyの間に敷設する道路の長さが偶数なら、xとy、x+Nとy+Nをuniteする。 奇数ならxとy+N、x+Nとy…

問題 TopCoder Statistics - Problem Statementsnukeさん 解法 見えている部分については、勝てるカードがあればできるだけ小さいカードで勝ち、勝てない時は小さいカードで負けるようにする。見えていない部分はどうしようもないので期待値を出す。 コード …

問題 TopCoder Statistics - Problem Statement 解法 どう見ても累積和の問題なんだけど、愚直な全探索で通った（通った）。 コード public class ChocolateDividingEasy { public int findBest(String[] choco) { int H = choco.length; int W = choco[0].l…

問題 TopCoder Statistics - Problem Statement 解法 点0から始めて、曲がり角が最も大きくなるように貪欲に点を取っていくと上手くいく。 コード public class NoRightTurnDiv2 { double[] direction(int[] X, int[] Y, int from, int to) { // fromからto…

問題 TopCoder Statistics - Problem Statement 解法 動的計画法を使う。アリスが最後に歌った曲とボブが最後に歌った曲に対応する難易度の最小値をメモしておく。 コード public class SingingEasy { public int solve(int[] pitch) { int N = pitch.length…

問題 TopCoder Statistics - Problem Statement 解法 どのように括弧を挿入しても、a[0]は必ず正、a[1]は必ず負になる。 a[2]からa[i]までの合計値をとる。 ただしa[2]からa[j]までの合計値が負になるとき、-a[2]から-a[j]までの合計値は正になるので、a[2]…

解法 4方向いずれかを連打して壁に当たるなら、-1である。どれを連打しても壁に当たらない時は、連打できる最大数を求めておく。この最大数の範囲内であればどのように部分文字列を取られても死ぬことはない。 コード public class RobotOnMoon { public int…

問題 No.177 制作進行の宮森あおいです！ - yukicoder 解法 始点→原画マン→作画監督→終点、という最大フロー問題に帰着する。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; public class Main { public static…

問題 No.176 2種類の切手 - yukicoder 解法 Bの枚数を0から総当りする。Bの枚数をiとした時、切手の合計額がTをギリギリ超えるようなAの枚数jは、以下のように書ける。 j = (T - B * i + A - 1) / AB*iがTを超えていたりB*Aを超えていたりしたらbreakする。 …

問題 TopCoder Statistics - Problem Statement 解法 偶数個間が空いている時、例えば2個空いている時、A__Bのようになっている時はABABしかあり得ないが、A__Aのようになっている時はAABAかABAAかABBAのように3通り考えられる。一般化すると、間が2k個空い…

問題 TopCoder Statistics - Problem Statementtozangezanさん 解法 SRM 649 div1 easy: Decipherability - mayoko’s diary コード import java.util.Arrays; public class Decipherability { public String check(String s, int K) { if (s.length() == K) …

問題 TopCoder Statistics - Problem Statementevimaさん 解法 動的計画法を使う。dp[i][j][p]に「i文字目まででAをj文字使った時にペアpに到達可能かどうか」を記録しておく。 if (!dp[i][j][p]) { dp[i + 1][j + 1][p] = true;// i+1文字目をAにする dp[i …