\( A = {p_1}^{q1} \times {p_2}^{q2} \times ... \times {p_n}^{qn} \) \( A^B = {p_1}^{q1 * B} \times {p_2}^{q2 * B} \times ... \times {p_n}^{qn * B} \) とする。まず、X にAの素因数分をそれぞれ掛けて、 \( X = p_1 \times p_2 \times ... \times p…

public class SimilarNames2 { int mod = 1000000007; int?[,] memo; int dfs(string[] names, int pos, int L) { if (L == 0) return 1; if (!memo[pos, L].HasValue) { int val = 0; for (int i = 0; i < names.Length; i++) { if (i == pos) continue; if…

\( A = 2^{a1} \times 3^{a2} \times ... \times p_n^{an} \) \( C = 2^{c1} \times 3^{c2} \times ... \times p_n^{cn} \) より \( A^B = 2^{a1*B} \times 3^{a2*B} \times ... \times {p_n}^{an*B} \) \( C^D = 2^{c1*D} \times 3^{c2*D} \times ... \time…

体重 5kg を超えないように、みかんを軽い順に食べていきます。 public class MiniatureDachshund { public int maxMikan(int[] mikan, int weight) { Array.Sort(mikan); int cnt = 0; foreach (int m in mikan) { weight += m; if (weight <= 5000) cnt++;…

回文になる行の集合を全通り試す。回文になる行の箇所が固定されると、(0列とW-1列), (1列とW-2列）... のペアそれぞれについて独立に処理できるため、あとは動的計画法で処理できる。本番だと、i列と(W-1-i)列のペアについて、「i列が回文である / でない」…

goal の使っている各bitについて、その bit を立てられないように、numbers から削除すればよい。ただしこのとき numbers のうち、goal が使っていない bit を含むものは無視する。 public class ORSolitaire { public int getMinimum(int[] numbers, int go…

N,M は 2 以上 8 以下のため、「回文になる列の集合」と「回文になる行の集合」について全探索できる。回文になる行と列がはっきりしていると、{ A[y][x] , A[H-1-y][x] , A[y][W-1-x] , A[H-1-y][W-1-x] } について、同じ値にしないといけないペア情報が確…

シャトルの座席数で全探索。 public class TheShuttles { public int getLeastCost(int[] cnt, int baseCost, int seatCost) { int ans = int.MaxValue; for (int seat = 1; seat <= 100; seat++) { int need = 0; foreach (var c in cnt) { need += (c - 1)…

Div1Easy の ORSolitaire とは違って、|numbers| public class ORSolitaireDiv2 { public int getMinimum(int[] numbers, int goal) { int n = numbers.Length; int ans = int.MaxValue; for (int i = 0; i < (1 << n); i++) { int or = 0, cnt = 0; for (in…