AtCoder Grand Contest 022
A.Diverse Word(300)
問題
https://beta.atcoder.jp/contests/agc022/tasks/agc022_a
すべての文字が異なる文字列Sが与えられる。辞書式順序でSよりも大きく、すべての文字が異なる辞書順最小の文字列Tを求めよ。
方針
|S|<26の場合は、Sに使用していない文字のうち、辞書順最小の文字列をSの末尾に追加する。|S|=26の場合はnext_permutationで辞書順の次の文字列を求め、余分な文字を削除する。
public void solve(int testNumber, InputReader in, PrintWriter out) { char[] s = in.nextString().toCharArray(); int len = s.length; boolean[] used = new boolean[26]; for (int i = 0; i < len; i++) { used[s[i]-'a'] = true; } if (len < 26) { for (int i = 0; i < 26; i++) { if (!used[i]) { out.print(s); out.println((char)(i+'a')); return; } } } else { char[] t = s.clone(); Permutation p = new Permutation(); p.next(t); StringBuffer sb = new StringBuffer(); boolean same = true; for (int i = 0; i < len; i++) { if (s[i] == t[i]) { sb.append(t[i]); } else { sb.append(t[i]); same = false; break; } } out.println(same ? -1 : sb.toString()); } } static class Permutation { public boolean next(char[] a) { int n = a.length; int i = n - 1; while (i > 0 && a[i - 1] >= a[i]) i--; if (i <= 0) return false; int j = n - 1; while (a[j] <= a[i - 1]) j--; swap(a, i - 1, j); int k = n - 1; while (i < k) swap(a, i++, k--); return true; } private static void swap(char[] a, int i, int j) { char tmp = a[i]; a[i] = a[j]; a[j] = tmp; } }
雑記
本番中に通せなかった悔しい問題。|S|=26の場合に次の辞書式最小を求めるのが(当時は)難しかった。next_permutationがinputの次の辞書式の順列をreturnするということに気がつくと容易ですね。
ポイント
- next_permutationは辞書式で次の順列をreturnする
B.GCD Sequence(600)
問題
https://beta.atcoder.jp/contests/agc022/tasks/agc022_b
a_n = {a_1, a_2, ... ,a_n} で与えられる。以下の条件を満たすa_nを求めよ。
- a_iのすべての要素の最大公約数が1
- a_iとa_i以外のすべての最大公約数が1でない
- すべてのa_i <= 30000
方針
まだよく理解していない。。。
雑記
C.Remainder Game(700)
問題
https://beta.atcoder.jp/contests/agc022/tasks/agc022_c
a_n = {a_1, a_2, ..., a_n} と b_n = {b_1, b_2, ..., b_n} が与えられる。以下の操作をすることで、a_i を b_i にする時のコストを最小化せよ。(存在しない場合は-1)。
- 操作:コスト2kで a_i を a_i % k またはそのままにする
方針
- 操作として、同じkを2回以上使用はしない
- 1 <= b_i <= 50 なので 1 <= k <= 50
コストが2k。
最小化するときのコストを仮定
- すべて必要と仮定して、k=50から順番に1111...111
- kビット目を除いたとして、他のk-1以下のビットを使用してa_iをb_iにすることができるかどうか。できるのであればkビット目は不要。(これを部分問題とする)
部分問題の解き方
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); int[] a = in.nextIntArray(n); int[] b = in.nextIntArray(n); // すべての要素が最初から同じ場合 boolean same = true; for (int i = 0; i < n; i++) { if (a[i] != b[i]) { same = false; break; } } if (same) { out.println(0); return; } // すべてのb[i]が最初から0の場合 for (int i = 0; i < n; i++) { if (b[i] != 0) { same = false; } } if (same) { out.println(2); return; } // kの集合(1 .. 50) Set<Integer> set = new HashSet<>(); for (int i = 1; i <= 50; i++) { set.add(i); } long ans = 0; for (int k = 50; k >= 1; k--) { // グラフの初期化 long[][] g = new long[51][51]; for (int l = 0; l < 51; l++) { for (int m = 0; m < 51; m++) { if (l == m) { g[l][m] = 0; } else { g[l][m] = INF; } } } // kを不要と仮定 boolean need = false; set.remove((Integer)k); // グラフに有向辺を構築 for (int i : set) { for (int j = 0; j < 51; j++) { g[j][j%i] = 1; } } // ワーシャルフロイド法 for (int K = 0; K < 51; K++) { for (int I = 0; I < 51; I++) { for (int J = 0; J < 51; J++) { g[I][J] = Math.min(g[I][J], g[I][K]+g[K][J]); } } } // a[i] -> b[i] への経路がなくなった場合 for (int i = 0; i < n; i++) { if (g[a[i]][b[i]] == INF) { need = true; break; } } if (need) { ans += (long)1 << k; set.add(k); } } out.println(set.size() == 50 ? -1 : ans); }
雑記
方針も何も初見では全然わからなかったので解説ACした。以下学び。
- 求められている答えを仮定する
- nk ときたらビット列を想像する
- 操作の順番が重要 ⇔ グラフ構造を考える