問題 No.174 カードゲーム（Hard） - yukicoder 解法 #17295 No.174 カードゲーム（Hard） - yukicoderdp[k]:= あるターンturnにおける、j番目に小さいカードより小さいカードがk枚ある確率、をメモする。turnが遷移する時、 dp[0] *= (1 - P[player]); dp[c…

入力文字列と自分の名前のLCSをDPで求める。 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); char[] input = scanner.next().toCharArray(); scanner.close(); int N …

問題 No.173 カードゲーム（Medium） - yukicoder 解法 誤差0.005以内で正解になるという緩さなので、10000100,000回シミュレーションして勝率を出す。@meguru_comp おっしゃるとおりです。100,000回でした。（コードは100000になってます）— 宇宙ツイッタラ…

問題 C: Optimal Recommendations - Indeedなう（オープンコンテスト） | AtCoder 解法 dp[i][j][k]:= 能力i, j, k の人が行ける最高の報酬の会社として、 dp[i][j][k + 1] = Math.max(dp[i][j][k + 1], dp[i][j][k]); dp[i][j + 1][k] = Math.max(dp[i][j +…

解法 i文字目時点での文字cの連続長の期待値をメモしておき、最後に全部足す。 コード public class SquareScores { public double calcexpectation(int[] p, String s) { int N = s.length(); // expScore[i][c]:= i文字目時点でのc連続長の期待値 double e…

問題 C: 仕事計画 - AtCoder Regular Contest 032 | AtCoder 解法 ある時刻time以降の仕事の最大数を考える。 コード import java.io.IOException; import java.util.ArrayList; import java.util.HashMap; public class Main { private static final int MA…

問題 G: 辞書順 - Typical DP Contest | AtCoder 解法 dp[i][c]:= i文字目以降の部分列で文字cから始まるものの個数、とする。i=N-1から順々にdpを埋めていき、埋め終わったらそこから文字列を復元すれば良い。 コード import java.io.BufferedReader; impor…

問題 No.171 スワップ文字列(Med) - yukicoder 解法 重複組み合わせの式で計算するだけだが、掛け算を先にやろうとすると値が大きくなりすぎる。かと言って割り算を先にやることも出来ず、ましてや573で剰余を取ることも出来ないので、掛け算と割り算を同時…

問題 F: 準急 - Typical DP Contest | AtCoder 解法 (駅i+1で連続j+1回目の停車をする組み合わせ) = (駅iで連続j回目の停車をする組み合わせ)なので、愚直にやってもO(NK)で解ける。工夫して、 (駅i+1で停車する組み合わせ) = (駅iで停車する組み合わせ) + (…

問題 E: 数 - Typical DP Contest | AtCoder 解法 下からi桁目まで見た時にj余る整数の数を記録しておく。この時、i桁目がNのi桁目以下になる数も記録しておく。 コード import java.util.Scanner; public class Main { private static final long MOD = 100…

問題 D: LCM Rush - AtCoder Beginner Contest #020 | AtCoder 解法 // 最大公約数 static long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); } // 最小公倍数 static long lcm(long a, long b) { return a * b / gcd(a, b); } 最大公約数と最…

問題 C: 壁抜け - AtCoder Beginner Contest #020 | AtCoder 解法 ゴールについた時の(歩数, 黒マスを通った回数)の組み合わせを記録しておき、それぞれについてxの最大値を求めれば良い。黒マスを通った回数は高々100なので、大した量にはならない。 コード…

問題 D: サイコロ - Typical DP Contest | AtCoder 解法 サイコロを振った回数を1から少しずつ大きくしていく。それぞれの回数について、2の指数、3の指数、5の指数を数え、その状態になる確率を求める。 コード import java.io.IOException; import java.ut…

問題 C: トーナメント - Typical DP Contest | AtCoder 解法 やるだけ。 コード import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] arg) { int K = nextInt(); int N = 1 << K; int[] rating = n…

問題 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(…

問題 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…

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

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

問題 C: 木 - Indeedなう（予選B） | AtCoder 解法 やるだけ。やるだけだけどnew int[100000][100000]はMLEするので、別の方法を考える。 コード import java.io.IOException; import java.util.ArrayList; import java.util.PriorityQueue; public class Ma…

問題 B: 枕決め - CODE FESTIVAL 2014 Middle | AtCoder 解法 高さhを1から少しずつ大きくしていく。 x[i]=hになる人iがいたら、y[i]をPriorityQueueに入れる。 PriorityQueueの中でy hの高さの枕をPriorityQueueの人に順番に配る。 ジョブスケジューリング…

問題 A: 身体バランス - CODE FESTIVAL 2014 Middle | AtCoder 解法 ダイクストラ。 コード import java.io.IOException; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; public class Main { public static void m…

問題 D: パズル - Indeedなう（予選A） | AtCoder 解法 あるマス(i, j)の数字が本来あるべきマスとのマンハッタン距離を計算する。本来あるべきマスまで移動するのに最低でもマンハッタン距離分だけの手数がかかるので、他の数字についてもマンハッタン距離…

問題 No.165 四角で囲え！ - yukicoder 解法 AOJ 2426の方法を使いまわして座標圧縮する。 AOJ 2426: 宝探し（2次元の累積和） - 宇宙ツイッタラーXの憂鬱かつにおける宝物の数とポイントを計算してやれば良いが、x1とx2とy1とy2を全探索するとTLEになるので…

問題 Treasure Hunt | Aizu Online Judge 解法 フィールドは広いが宝物の数は高々5000なので、宝物に準拠した最大5001*5001のフィールドを作る。treasures[i][j]にかつにおける宝物の数を入れておくと、かつにおける宝物の数は、以下の式で表せるようになる…

User ID を入力するとクリア状況が見れる。怒られたらやめます。https://kenkoooo.com/atcoder/

問題 Infinity Maze | Aizu Online JudgeH*Wの迷路が与えられ、ロボットをL回移動させる。ロボットは壁や障害物にぶつかると右に90度回転する。この回転は移動回数にはカウントしない。L回移動させた後、ロボットはどこにいてどこを向いているか。 解法 だが…

問題 Sleeping Time | Aizu Online JudgeでTを目指してK回二分木探索するが、Pの確率で間違った方を選んでしまうとき、探索して見つけた値T'がを満たす確率を求めよ。 解法 二分木探索する（素直） コード import java.math.BigDecimal; import java.util.Ar…

SamurAI Coding 2014-15 とは？ SamurAI Coding 2014ゲームAIのコンテスト。カイジに出てきそうなオリジナルルールのゲーム。 ソース kenkoooo/SamurAICoding2014 kenkoooo/SamurAICoding2014 · GitHub

問題 Slim Span | Aizu Online Judge無向グラフが与えられるので、エッジの最小コストと最大コストの差が最小になるように全域木を作る。作れる場合は最小コストを、無理なら-1を出力する。 解法 エッジを昇順に並べておき、エッジiより大きいコストの中で最…

問題 ボブが1からNまでの自然数を並び替えて数列pを作る（ここではpは1-indexedとしておく）。アリスはf(1)=p[1]、f(m)=p[f(m-1)]となるようにfを考える。ボブがどのように数列pを作ってもf(x)=1となるような最小のxを求めよ。 解法 ボブがどんな数列を作っ…