問題 C: おやつ - AtCoder Regular Contest 042 | AtCoderarc042.contest.atcoder.jp 解法 最も安い1個については0円と見なすことが出来ると考える。商品を値段の降順でソートして高い方から見ていき、動的計画法で「高い方からn個目までみた時の、予算内で…

問題 C: 双子と○×ゲーム - AtCoder Beginner Contest 025 | AtCoderabc025.contest.atcoder.jp 解法 AtCoder Beginner Contest 025 解説 from AtCoder Inc. www.slideshare.net コード import java.util.Scanner; public class Main { private int[][] b; pr…

問題 D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoderabc018.contest.atcoder.jp 解法 またはなら間に合うが、は間に合わない。そこで男子か女子のどちらか一方だけをビットで回して、もう一方は相手のビットに対する得点を出してソートし、…

問題 C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder コード import java.util.Scanner; public class Main { public void solve() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] a = new int[N]; int[] b = new int[…

問題 C: 茶碗と豆 - AtCoder Regular Contest 038 | AtCoderarc038.contest.atcoder.jp 解法 AtCoder ARC #038 : C - 茶碗と豆 - kmjp's blogkmjp.hatenablog.jp コード import java.util.Arrays; import java.util.Scanner; public class Main { public sta…

問題 D: 射撃王 - AtCoder Beginner Contest 023 | AtCoderabc023.contest.atcoder.jp 解法 二分探索でスコアを探索する。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scann…

問題 C: 収集王 - AtCoder Beginner Contest 023 | AtCoderabc023.contest.atcoder.jp 解法 AtCoder ABC #023 : Python練習編 - kmjp's blogkmjp.hatenablog.jp コード import java.util.Scanner; import java.util.TreeSet; public class Main { private st…

問題 D: マーブル - AtCoder Beginner Contest #004 | AtCoderabc004.contest.atcoder.jp 解法 AtCoder Beginner Contest 004 解説 from chokudai www.slideshare.netスタートと赤・緑・青のノードを結び、赤・緑・青と座標-500~500のノードを結び、これらの…

問題 D: Big Bang - AtCoder Beginner Contest 022 | AtCoderabc022.contest.atcoder.jp 解法 AtCoder Beginner Contest 022 解説 from chokudai www.slideshare.net外側の点を結んで、全ての点が内部か線上にあるような多角形を作る。（凸包というらしい）…

問題 C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder 解法 各a[i]の段のmid以下のa*bの数をカウントし、それがKとなるようにmidを二分探索する。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public static vo…

問題 D: トランプ挿入ソート - AtCoder Beginner Contest #006 | AtCoder 解法 AtCoder Beginner Contest 006 解説 コード import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws Excep…

問題 D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest #005 | AtCoder 解法 たこ焼き器について、二次元の累積和を求めておく。クエリに対して作れる長方形を全列挙し、その長方形を(x,y)だけ平行移動した時に、長方形内部の美味しさの合計を計算す…

問題 D: AtCoder社の冬 - AtCoder Beginner Contest #003 | AtCoder 解法 ステップとしては、 R*C内のX*Yの取りうるパターンを調べる。 X*Y内のD+Lの取りうるパターンを調べる。 D+L内のDとLのパターンを調べる。 の3つをこなす必要がある。R*C内のX*Yの取り…

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 1からnの中から重複を許してk個選ぶという問題に帰着できる。 を求めたいが、割り算をすると計算に時間がかかりすぎる。そこでモジュラ逆数を使う。モジュラ逆数 - Wikipedia コード impo…

問題 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder 解法 ある頂点vに注目した時に、「vに入ってくる最大のパス」と「vから出て行く最大のパス」を計算する。この2つが同じパスにならないように、頂点はそれぞれ1度ずつしか注目しない。め…

問題 C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder 解法 dp[pos][diff0][diff1]:= pos文字目まで見た時に、(0の文字数)-(1の文字数)の最大値がdiff0であり、(1の文字数)-(0の文字数)の最大値がdiff1である組み合わせの数とする。S[pos]='0'…

問題 E: Page Rank - Indeedなう（オープンコンテスト） | AtCoder 解法 最初に全社員のPage Rank を1.0としておき、定義にしたがって1000回ほど計算すると収束する。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Scanne…

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

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

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

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

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