World Codesprint 10: Permutation Happiness
https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness
解法
DP。1~n の順列に n+1 を挿入するイメージで更新していく。山の頂上(極大点)の個数を状態として持つと良い。dp[i: 順列のサイズ][j: 頂上の個数]
とする。
(1) 頂上の隣に挿入した場合は、頂上の個数は変わらない。2j 通り。
(2) それ以外の場所に挿入すると、頂上の個数が一つ増える。i+1-2j 通り。
#include <iostream> #include <cstdio> #include <vector> const int mod = 1e9 + 7; struct modint { int n; modint(int n = 0) : n(n) {} }; modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); } modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); } modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); } modint &operator+=(modint &a, modint b) { return a = a + b; } modint &operator-=(modint &a, modint b) { return a = a - b; } modint &operator*=(modint &a, modint b) { return a = a * b; } int main() { int q; std::cin >> q; const int N = 3000; std::vector<std::vector<modint>> dp(N + 1, std::vector<modint>(N + 1)); dp[1][1] = 1; for (int i = 1; i < N; i++) { for (int j = 0; j <= i; j++) { dp[i + 1][j] += dp[i][j] * (2 * j); dp[i + 1][j + 1] += dp[i][j] * (i + 1 - 2 * j); } } while (q--) { int n, k; std::cin >> n >> k; modint ans = 0; for (int i = 0; i <= N; i++) { if (n - i >= k) { ans += dp[n][i]; } } std::cout << ans.n << std::endl; } }
GCJ 2017 Qual
A 問題
+- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。
B 問題
10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁の数字を 1 減らしたらそれに続く数字はすべて 9 にすればいいことを踏まえれば解くことができる。
C 問題
区間の長さだけ保持しておけばよくて、大きい区間から順に分割していくのを繰り返せば良い。 分割過程では値が重複しやすいため、同じ長さの区間をまとめて処理すれば速くなりそうである。
分割の様子を図にすると以下の通り。
木の高さは O(log n) である。また、各レベルにおける値の種類数はたかだか 2 である(これは最大値と最小値の差がたかだか 1 であることから分かる)。ゆえにまとめて処理すれば O(log n) 回で収まる。
D 問題
条件を整理すると
- どの列/行も、x を 2 つ以上含まない
- どの列/行も、x と o の両方を同時に含まない
- どの列/行も、o を 2 つ以上含まない
- どの対角線も、+ を 2 つ以上含まない
- どの対角線も、+ と o の両方を同時に含まない
- どの対角線も、o を 2 つ以上含まない
となる。あるマスに o が書かれているというのは、あるマスに + と x の両方が書かれていると言い換えられる。この言い換えにより条件はよりシンプルになる。
- どの列/行も、x を 2 つ以上含まない
- どの対角線も、+ を 2 つ以上含まない
+/x を o に変える操作は許されているので、+/x は完全に独立して考えることができる。よって、それぞれ独立に最大化すればよい。これは貪欲にできる。
AtCoder Grand Contest 012 C: Tautonym Puzzle
http://agc012.contest.atcoder.jp/tasks/agc012_c
解法
空の列も良い文字列だとみなす。
順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。
- A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。
- A←A+[foo], B←[foo]+B とすると A+B のパターン数は X+1 になる。
これを利用することで 4log(N) 個の要素で構築できる。
AtCoder Grand Contest 012 B: Splatter Painting
http://agc012.contest.atcoder.jp/tasks/agc012_b
解法
di が小さいのが鍵に見える。
dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。
補足
ある頂点から距離 d の範囲を塗りつぶすという命令は、距離 d-1 の塗りつぶし命令に分解できる。
頂点 v から距離 d の塗りつぶし命令が複数あるならば、最も新しい命令以外は無視しても良い。無視することにより計算量は O(d(n+m)) になる。
AtCoder Grand Contest 012 A: AtCoder Group Contest
http://agc012.contest.atcoder.jp/tasks/agc012_a
解法
入力を昇順にソートして考える。
適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。
_o__o__o__o_ 000111222333
oになっているのが中央値。
これは改善ができる。
_o__o___o_o_ 000111232233
改善の雰囲気から最適構造が見える。
____o_o_o_o_ 012300112233