COLOCON -Colopl programming contest 2018- C - すぬけそだて――ごはん――
解法
A～Bまでの整数が書かれた各カードを購入するか購入しないで全探索する。
制約等から時間計算量がO(2^35)と思ってしまうが
「...これまでに食べたどのカードに書かれた整数とも互いに素である整数の書かれたカードを食べたとき...」というこの問題の特徴を考えると
2で割り切れる整数は2枚以上購入できない、3で割り切れる整数は2枚以上購入できない、5で...(省略)
という感じで時間計算量O(2^35)も掛からない。
「2で割り切れる整数は2枚以上購入できない」ということで、全探索中に購入出来るカードは高々18枚しかない。
これを3で割り切れる,5で割り切れる,...という風に考えると十分全探索で間に合うと考えられる。
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.*; public class Main { long A,B; long[] prev; private long gcd(long x,long y) { return y == 0 ? x : gcd(y,x % y); } // 整数A~整数Bの各整数に対して 購入する/しない で探索 private int dfs(long n,int it) { if (n == B + 1) { return 1; } // 整数nを購入しない場合 int ret = dfs(n + 1,it); // 購入済みの各整数と整数nが互いに素であるかをチェック boolean ok = true; for(int i = 0;i < it;i++) { if (gcd(n,prev[i]) != 1) { ok = false; } } // 整数nを購入する場合 if (ok) { prev[it] = n; ret += dfs(n + 1,it + 1); } return ret; } private void solve() { A = nextLong(); B = nextLong(); prev = new long[(int)(B - A + 1)]; int it = 0; out.println(dfs(A,it)); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
SRM719 Div2 Hard
考察
根ノードから任意のノードまでのパスのXORの計算を行う。
xor[V] = 根ノードから任意のノードVまでのXOR
そうすると任意のノードVから他の任意のノードUまでのパスのXORの計算結果は
xor[V] ^ xor[U]になる。これはXORの性質を考えると分かる。
A xor B = X
A xor C = Y
X xor Y = B xor C
詳しくはkmjpさんの解説記事で
kmjp.hatenablog.jp
ソースコード
下のコードでやっていることは
ノード0から任意のノードvまでのXORを求めとく。
制約からノード数<=1000なので、パスの始点ノードsと終点ノードtを全探索してxor[s]^xor[t]をSetに挿入。
0<=w[i]<=1023なのでXORの計算結果は高々1024通りしかない。
あとはSetから重複を許して値を二つ選んでXORの最大値を求める。
import java.util.HashSet; import java.util.Set; public class TwoDogsOnATree{ public int maximalXorSum(int[] parent,int[] w){ int N = parent.length + 1; int[] xor = new int[N]; for(int i = 1;i < N;i++){ int v = i; while(v > 0){ xor[i] ^= w[v-1]; v = parent[v-1]; } } Set<Integer> xorSet = new HashSet<>(); for(int i = 0;i < N;i++){ for(int j = 0;j < N;j++){ xorSet.add(xor[i]^xor[j]); } } int ans = 0; for(int a : xorSet){ for(int b : xorSet){ ans = Math.max(ans,a^b); } } return ans; } }
AtCoder Regular Contest 079 D Decrease (Contestant ver.)
考察
・公式解説
Editorial - AtCoder Regular Contest 079 | AtCoder
公式解説見ながらソースコード中に考えたこと書きました。
実験して解法につながる性質とか規則性見つけるの難しい。
こういう問題に出くわしたらどうするのが良いのだろう
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { long K; int N; public void solve() { K = nextLong(); N = 50; long[] a = new long[N]; //解説の通り、[0,1,2,3,4,5,6...,N-1]にする for(int i = 0;i < 50;i++){ a[i] = i; } /* * 1番目,2番目,3番目,4番目,5番目,...N番目,1番目,2番目,3番目,..みたいな感じ * で1～N番目の要素を順番にそれぞれに対して操作を合計K回行う */ long x = K / N;//xはそれぞれの要素に必ず操作する回数 long y = K % N;//先頭からy番目まで追加で操作を行う for(int i = 0;i < N;i++){ a[i] += N * x;//x回N増やす a[i] -= (N-1)* x;//他の要素の数×一つの要素に対して必ず操作する回数 a[i] -= y;//全ての要素の中で追加で操作する回数 if(i < y){ a[i] += N+1;//今見ている要素に対して追加で操作を行うとき } } out.println(N); for(int i = 0;i < N;i++){ if(i != 0)out.print(" "); out.print(a[i]); } out.println(); } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
yukicoder No514 宝探し３
考察
- 座標
と座標
のマンハッタン距離は
である。（
とする）
- そこで、座標
と座標
を考える。（y座標を求めるためにx座標を0に固定する）
- すると、
となり、
と出来る。これで
は求まった。
- あとは
となり、座標
なので)
ソースコード
import sys def query(p): print(p[0],p[1]) sys.stdout.flush() ret = int(input()) if ret == 0: sys.exit(0) return ret a=query((0,0)) b=query(((a,0))) query((a-b//2,b//2))
Codeforces #397 Div1+Div2 D Artsem and Saunders
考察
多分これは,与えられた2つの式
から、式を変形して考察を進めれば良いのかな？
@tookunn_1213 この単射ではないっていうのはh(a) = h(b)の場合,h(a) = h(b) = Aとして、g(h(a)) = a,g(h(b)) = bで,g(A) = a,bはaかbどちらかに一意に定まっていないということか
— tookunn (@tookunn_1213) 2017年2月16日
@tookunn_1213 h(g(x))とh(g(y))は同一の値になることが分かって、g(h(g(x))) = g(h(g(y)))でなきゃいけないからg(x) = g(y)であるということかな（説明が下手）
— tookunn (@tookunn_1213) 2017年2月16日
@tookunn_1213 メモhttps://t.co/phi9xhu1uZ
— tookunn (@tookunn_1213) 2017年2月16日
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.HashMap; import java.util.NoSuchElementException; public class D { int N; int[] g; ArrayList<Integer> h; HashMap<Integer,Integer> map; public void solve() { N = nextInt(); g = new int[N]; h = new ArrayList<Integer>(); map = new HashMap<Integer,Integer>(); for(int i = 0;i < N;i++){ int f = nextInt()-1; /* * fの値ごとにまとめて適当に値を割り当てる * 今回はmap.size()を割り当てる * hには重複なしのfの値を挿入 */ if(!map.containsKey(f)){ map.put(f, map.size()); h.add(f); } //fの値をkeyにして適当に割り当てた値をg[i]に g[i] = map.get(f); } for(int i = 0;i < map.size();i++){ //g(h(x)) = x if(g[h.get(i)] != i){ out.println(-1); return; } } out.println(map.size()); for(int i = 0;i < N;i++){ if(i != 0)out.print(" "); out.print(g[i]+1); } out.println(); for(int i = 0;i < map.size();i++){ if(i != 0)out.print(" "); out.print(h.get(i)+1); } out.println(); } public static void main(String[] args) { out.flush(); new D().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
SRM 708 Div2 Hard
考察
うーん。これ思いつく発想ってどうやるんだろ。
「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」 ことかなぁ
@tookunn_1213
— ばたこ (@btk15049) 2017年2月9日
dp[i][j]:=S[0...i]とR[0...j]の共通部分文字列の個数
の間違いでした
失礼しました
@tookunn_1213 文字列S[i-1] = 文字列R[j-1]の時,dp[i][j] += dp[i-1][j-1]するのは,S[i-1] = R[j-1]からS[i-1]のR[j-1]のペアを回文に含める場合とそうでない場合があるからというのもなんとなく分かった
— tookunn (@tookunn_1213) 2017年2月10日
@tookunn_1213 学校にいるので、帰宅後用メモ pic.twitter.com/aLsmMULoUJ
— tookunn (@tookunn_1213) 2017年2月10日
ソースコード
public class PalindromicSubseq2 { static final int MOD = (int)1e9 + 7; public int solve(String s){ char[] S = s.toCharArray(); char[] R = new StringBuilder(s).reverse().toString().toCharArray(); int N = S.length; long[][] dp = new long[N+1][N+1]; for(int i = 0;i < N+1;i++){ dp[i][0] = 1; dp[0][i] = 1; } for(int i = 1;i < N + 1;i++){ for(int j = 1;j < N + 1;j++){ dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + MOD) % MOD; dp[i][j] %= MOD; if(S[i-1] == R[j-1]){ dp[i][j] += dp[i-1][j-1] % MOD; dp[i][j] %= MOD; } } } long ans = 0; for(int i = 1;i < N + 1;i++){ ans ^= (dp[i-1][N-i] * i % MOD); } return (int)ans; } }
AtCoderBeginnerContest 054 D
考察
- 薬品を買うか買わないかの2通り,その選択をN回行う
通り
になる薬品の買い方を見ていく。そして、その買い方の中で最小の予算を求める
番目の薬品までを見た時,タイプ
の総量が
,タイプ
の総量が
の時の最小の予算
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.NoSuchElementException; public class Main { static final int INF = (int)1e9 + 7; int N,Ma,Mb; int[] A,B,C; public void solve() { N = nextInt(); Ma = nextInt(); Mb = nextInt(); A = new int[N]; B = new int[N]; C = new int[N]; for(int i = 0;i < N;i++){ A[i] = nextInt(); B[i] = nextInt(); C[i] = nextInt(); } int[][][] dp = new int[N+1][444][444]; for(int i = 0;i < N + 1;i++){ for(int j = 0;j < 444;j++){ for(int k = 0;k < 444;k++){ dp[i][j][k] = INF; } } } dp[0][0][0] = 0; for(int i = 0;i < N;i++){ for(int j = 0;j < 444 - A[i];j++){ for(int k = 0;k < 444 - B[i];k++){ int a = j + A[i]; int b = k + B[i]; dp[i+1][j][k] = Math.min(dp[i+1][j][k], dp[i][j][k]); dp[i+1][a][b] = Math.min(dp[i+1][a][b],dp[i][j][k]+C[i]); } } } int ans = INF; int max = Math.max(Ma,Mb); for(int i = 1;i * max < 444;i++){ ans = Math.min(ans,dp[N][i*Ma][i*Mb]); } if(ans == INF){ out.println(-1); }else{ out.println(ans); } } public static void main(String[] args) { out.flush(); new Main().solve(); out.close(); } /* Input */ private static final InputStream in = System.in; private static final PrintWriter out = new PrintWriter(System.out); private final byte[] buffer = new byte[2048]; private int p = 0; private int buflen = 0; private boolean hasNextByte() { if (p < buflen) return true; p = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) return false; return true; } public boolean hasNext() { while (hasNextByte() && !isPrint(buffer[p])) { p++; } return hasNextByte(); } private boolean isPrint(int ch) { if (ch >= '!' && ch <= '~') return true; return false; } private int nextByte() { if (!hasNextByte()) return -1; return buffer[p++]; } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = -1; while (isPrint((b = nextByte()))) { sb.appendCodePoint(b); } return sb.toString(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } }
