AOJ 2965 - F グリッドの番号
解法
小さい順に数字を当てはめていくとき、上段の右端に配置するか、下段の右端に配置するかの二択になることを利用します。
番目までの数字を入れ終えて、上段に配置した個数が個かつ、直近手の上下の配置情報がのときの配置の通り数
とします。
配るDPを考えると、
を配る箇所は、を上段の左から番目に配置した場合と、下段の番目に配置した場合の2か所です。
それぞれのパターンについて、配置したときに矛盾がないかを確認し、問題が無ければ値を配れば良いです。
矛盾がないかを確認するには、をもとに状態を復元します。
上段に配置する場合は、上段の番目の数をチェックしてとの差が以下か、
下段に配置する場合は、上段の番目の数と下段の番目の数をチェックして、との差が以下かチェックすればよいです。
Good Bye 2015 D. New Year and Ancient Prophecy
問題
提出コード
の文字列を一つの年として見た時の、の組み合わせの個数
とします。
の文字列を使用した、と言うことは、次に選ぶがより真に大きい値になる必要があります。
条件は以下の二つで、どちらか片方を満たせばよいです。
これは、桁がそもそも大きいパターンです。かつ、2つの文字列を左から順に見ていった場合に初めて異なる値をについては、についてはとしたときに、
桁が同じ場合です。
1つめのパターンはすぐに計算できます。2つめのパターンが含まれるか含まれないか、を調べればよいです。
これは、についてZ algorithmを適用し、からの接頭辞がどれだけ一致しているかを見ればよいです。
結局遷移は以下のようになります。
となるが含まれる場合
含まれない場合
で計算できます。
累積和を更新しながらDPをすることで、で解けます。
2019-2020 ACM-ICPC Latin American Regional Programming Contest F. Fabricating Sculptures
解法
1段ずつ下からブロックを積んでいくことを考えます。
ある段のある区間にブロックを積んだら、それ以降はその積んだ区間に対してのみ積んでいくかどうかを考えます。
今区間の幅が残りで、ブロックの残り個数が個の際の、そこからの構築通り数
とします。
となります。
少し分解して、
とすると、
とすることで、累積和をループの中で取りながらDPをすることができます。
という式で計算します。
#include <bits/stdc++.h> #define MOD (long long)(1e9 + 7) using namespace std; template <int mod> struct ModInt { int x; ModInt() : x(0) {} ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {} ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; } ModInt &operator-=(const ModInt &p) { if((x += mod - p.x) >= mod) x -= mod; return *this; } ModInt &operator*=(const ModInt &p) { x = (int)(1LL * x * p.x % mod); return *this; } ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; } ModInt operator-() const { return ModInt(-x); } ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; } ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; } ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; } ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; } bool operator==(const ModInt &p) const { return x == p.x; } bool operator!=(const ModInt &p) const { return x != p.x; } ModInt inverse() const { int a = x, b = mod, u = 1, v = 0, t; while(b > 0) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } return ModInt(u); } ModInt pow(int64_t n) const { ModInt ans(1), mul(x); while(n) { if(n & 1) ans *= mul; mul *= mul; n >>= 1; } return ans; } friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; } friend istream &operator>>(istream &is, ModInt &a) { int64_t t; is >> t; a = ModInt<mod>(t); return (is); } static int get_mod() { return mod; } }; long long s, b; vector<vector<ModInt<MOD>>> dp, sum1, sum2; ModInt<MOD> solve(); int main() { cin >> s >> b; b -= s; cout << solve() << endl; return 0; } ModInt<MOD> solve() { dp.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0)); sum1.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0)); sum2.assign(s + 1, vector<ModInt<MOD>>(b + 1, 0)); dp[0][0] = sum1[0][0] = 1; for(int i = 1; i <= s; ++i) { for(int j = 0; j <= b; ++j) { sum1[i][j] += sum1[i - 1][j]; sum2[i][j] += sum2[i - 1][j]; if(j != 0) { dp[i][j] = sum1[i][j] * (i + 1); dp[i][j] -= sum2[i][j]; } else dp[i][j] = 1; if(i + j <= b) { sum1[i][i + j] += dp[i][j]; sum2[i][i + j] += dp[i][j] * i; } } } return dp[s][b]; }
2019-2020 ACM-ICPC Latin American Regional Programming Contest G. Gluing Pictures
解法
これの類題です。
文字目までの文字列を完成させるのに最小となる連続部分列の個数
とします。すると、この配列は広義単調増加になっているはずなので、
は、文字目を右端とするようなの部分文字列の中で最長の長さをとしたとき、となります。
このは前計算で求めておくことで、答えを求めることができます。
この前計算にはSuffix ArrayとLCPを用います。"<探したい文字列>#S"
と連結した後にLCP配列を作成すると、探したい文字列についてのSAのインデックスの前と後ろそれぞれで、最も近い部分に存在するSの一部から始まる箇所を探します。そして、その間にあるLCPの値の最小値が、求めたいになります。
前からと後ろからそれぞれループをし、Sの部分文字列があたったらLCPの値をその値に更新、それ以外の場合は現在の値とLCPの値のminを取る、という操作を繰り返しながらメモをします。
探したい文字列それぞれについてSAを構築するとTLEするので、探したい文字列自体も、"#"
であらかじめ連結します。
#include <bits/stdc++.h> #define inf (long long)(1e18) using namespace std; struct Suffix_Array { string str; int strlen, nowlen; vector<long long> rank, tmp, sa, lcp; Suffix_Array(string news = "") { str = news; strlen = str.size(); nowlen = 0; rank.resize(strlen + 1); tmp.resize(strlen + 1); sa.resize(strlen + 1); construct_sa(); construct_lcp(); } void construct_sa() { auto cmp = [&](int l, int r) { if(rank[l] != rank[r]) return rank[l] < rank[r]; int rx = l + nowlen <= strlen ? rank[l + nowlen] : -1; int ly = r + nowlen <= strlen ? rank[r + nowlen] : -1; return rx < ly; }; for(int i = 0; i <= strlen; ++i) { sa[i] = i; rank[i] = i < strlen ? str[i] : -1; } for(nowlen = 1; nowlen <= strlen; nowlen *= 2) { sort(sa.begin(), sa.end(), cmp); tmp[sa[0]] = 0; for(int i = 1; i <= strlen; ++i) tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0); for(int i = 0; i <= strlen; ++i) rank[i] = tmp[i]; } } void construct_lcp() { lcp.resize(strlen + 1); for(int i = 0; i <= strlen; ++i) rank[sa[i]] = i; int h = 0; lcp[0] = 0; for(int i = 0; i < strlen; ++i) { int j = sa[rank[i] - 1]; if(h > 0) --h; for(; j + h < strlen && i + h < strlen; ++h) if(str[j + h] != str[i + h]) break; lcp[rank[i] - 1] = h; } } }; long long n, sid = -1; string s; vector<string> v; vector<long long> res, vid, memo; Suffix_Array sa; void solve(); long long calc(int id); int main() { cin >> s >> n; v.resize(n); for(int i = 0; i < n; ++i) cin >> v[i]; res.resize(n); solve(); for(int i = 0; i < n; ++i) cout << res[i] << endl; return 0; } void solve() { string t; vid.resize(n); for(int i = 0; i < n; ++i) { vid[i] = t.size(); t += v[i] + '#'; } sid = t.size(); t += s; sa = Suffix_Array(t); long long now = 0, tsize = t.size(); memo.assign(tsize + 1, 0); for(int i = 0; i < tsize; ++i) { if(sa.sa[i] >= sid) now = sa.lcp[i]; else now = min(now, sa.lcp[i]); memo[i + 1] = max(memo[i + 1], now); } now = 0; for(int i = tsize - 1; i >= 0; --i) { if(sa.sa[i + 1] >= sid) now = sa.lcp[i]; else now = min(now, sa.lcp[i]); memo[i] = max(memo[i], now); } for(int i = 0; i < n; ++i) res[i] = calc(i); } long long calc(int id) { long long vsize = v[id].size(); vector<long long> dp(vsize + 1, inf), idmemo(vsize + 1, inf); dp[0] = 0; idmemo[0] = 0; for(int i = 0; i < vsize; ++i) { long long nowid = vid[id] + i; nowid = sa.rank[nowid]; idmemo[i] = i + memo[nowid] - 1; auto it = lower_bound(idmemo.begin(), idmemo.end(), i); if(*it < i || dp[it - idmemo.begin()] == inf) continue; dp[i + 1] = min(dp[i + 1], dp[it - idmemo.begin()] + 1); } if(dp[vsize] == inf) return -1; return dp[vsize]; }
SWERC 2018 K. Dishonest Driver
解法
区間DPをします。
の区間に対する最小コスト
とすると、
になります。
ただし、の文字列を複数回連結するとになる場合のみ、
になります。
この複数回連結、という判定はKMPの周期判定を用いると上手くできます(下のブログ参考)。
ただし、ぴったり複数回連結した場合のみなので、が0にならなければなりません。
#include <bits/stdc++.h> #define inf (long long)1e7 using namespace std; // A[i]: S[0,i-1] longest match(pre and suf) struct KMP { vector<long long> A; long long n; string s; KMP(string _s = "") { s = _s; n = s.size(); A.assign(n + 1, 0); A[0] = -1; for(int i = 0, j = -1; i < n; ++i) { while(j >= 0 && s[i] != s[j]) j = A[j]; ++j; // if(i + 1 < n && s[i + 1] == s[j]) // A[i + 1] = A[j]; // else A[i + 1] = j; } } inline const long long &operator[](int k) const { return (A[k]); } vector<long long> calccycle() { vector<long long> res(n, 0); for(int i = 0; i < n; ++i) res[i] = i + 1 - A[i + 1]; return res; } }; long long n; string s; vector<vector<long long>> dp; long long solve(long long l, long long r); int main() { cin >> n >> s; vector<long long> v = KMP(s).calccycle(); dp.assign(n + 1, vector<long long>(n + 1, inf)); for(int i = 0; i < n; ++i) dp[i][i + 1] = 1; for(int i = 0; i <= n; ++i) dp[i][i] = 0; cout << solve(0, n) << endl; return 0; } long long solve(long long l, long long r) { if(dp[l][r] != inf) return dp[l][r]; long long res = r - l, cycle = KMP(s.substr(l, r - l)) .calccycle()[r - l - 1]; for(int i = l + 1; i < r; ++i) { long long now = solve(l, i); if((r - l) % cycle != 0 || cycle > i - l || (i - l) % cycle != 0) now += solve(i, r); res = min(res, now); } return dp[l][r] = res; }
2019-2020 ACM-ICPC Latin American Regional Programming Contest バチャ 参加記
Dashboard - 2019-2020 ACM-ICPC Latin American Regional Programming Contest - Codeforces
なんか解法書こうと思ったんですけど時間かかりそうなのでそこは暇だったらにします
しろくんとsuta君と出ました。
流れ
開始後
僕がAから、suta君がDから、しろくんがMから読むことになりました。順位表からもMがまず解けそうということで、しろくんがそのままACです。
続いて、Eも解けそうということで、suta君がそのままACしました。
suta君がEの実装をしている間に、僕としろくんはGの考察をしていました。
じつは、Gはほぼ似たような問題を解いたことがあり、そこでsuffix arrayとlcpの使い方を一応学んでいたので、頑張って思い出しました。
そのままGをACしました。
https://t.co/k5zMqIA5ng
— ツバサ (@emtsu_ba) 2020年2月12日
今日のGの簡単ばーじょんです、復習していてよかったぁ
僕がGの実装をしている間に、2人がIの考察を行い、Gの実装と平行してIも実装してもらっていたため、直後にIもACしました。
中盤~終盤
次に解けそうなのがK, Lだろう、ということでsuta君がLの読解をしている間に僕としろくんがKを考察しました。
しろくんが「因数分解できたらいいですよね」みたいな感じのことを言い、
という式を見せてきたときに僕がいい感じに閃き、解法を思いつきました。
同時にバチャを並走してくださっていたチームメンバーのツイートでもちらほら見かけた、「 未満になることが保証されている」を読み間違えて「 未満にしなければいけない」にした結果、時間を食いましたが無事AC。
Lは、suta君が問題の読解を終えて聞いたところ、これのちょっとした応用ですね~、つい最近講義でやりました!って言いつつ自分が実装をしました。
最後は、皆でFをやっていました。
考察は終わった(一応コンテスト後に通しました)のですが、実装が残り5分しかなくて間に合いませんでした。
途中、DPが3乗(残り個数と、1つ隣の高さを状態に持たせる)から落ちない~って言っていて、3人でEDPCの雑談をしていたのですが、その際に急に解法を思いつきました。
結果
6完です。
Fの考察が(多分)終わって実装が間に合わず@shiro537 くんと @suta28407928 くんの3人で出ました pic.twitter.com/bjDVboJLxo
— ツバサ (@emtsu_ba) 2020年2月12日
雑な解法
F
1行ずつ、下からブロックを積み重ねていきます。次にブロックを置く際は、1つ前の操作でブロックを置いた列にしか置かない、とします。
現在使える幅が、残りブロック数がの際の、そこからの置き方
とします。
となります。
このΣの部分を分解します。
として、この累積和も同時並行で求めていくと、上手く計算できます。
G
調べたい文字列を、元の文字列をとすると、
という文字列(ただしはダミー文字)を作成し、これに対してのsuffix arrayおよびlcp配列を構築します。
すると、調べたい文字列の任意の部分を始点とする、との最長一致部分が、前計算で求まります。
あとは、文字目までの最小コスト、としていい感じに更新します(自分は配るDPをしました)
K
与えられる文字列を、の切り替わりで区切ります。そのときの区切りの個数が、多項式の係数の最大です。
求める多項式をとします。のの部分を、の区切れ目の値(例えば、人目が、人目がならば)に設定すると、うまく問題の条件を満たす多項式になります。を計算する際に、が、ならば正、ならば負になるので、いい感じになります。
L
そもそもBGの入れ替えが行われない時、最大正方形のDPは、
を右下とする最大正方形の1辺の長さ
と定義して、となります(そこがならば0です)。
これを、入れ替えたパターンの行に対しても行い、
を右下とする最大正方形の1辺の長さ( ならば行のBGを入れ替え)
とすると、上のDPとほぼ同じ遷移で解くことができます。
二項係数の式変形について
ここであまり得意でないパターンの問題が出てきたのでメモです。DEGwerさんの数え上げPDFなんかにはいろんな種類が載っているので、また出てきたら追加します。数式をごちゃごちゃいじるとできるパターンもそのうち載せたいです。
について計算をしたい、とします。
これは、一回の移動でだけ移動できるとしたときの、座標からへの最短移動経路の経路数です。
について計算します。
これは、座標からへの最短経路の場合の数を、について足し合わせたものです。
上の(適当な)図の、水色が今求めたい部分です。その上の行にある、黄色く塗られた部分のマスについて注目します。
水色のマスに行くには、まず黄色のマスの少なくとも1つを通らなければ、たどり着くことはできません。そして、赤い矢印のうちいずれか1つを必ず通ります。しかも、2本以上その矢印を通ることはありません。矢印を通った後は、水色のマスにたどり着くまでひたすら右に進む必要があります。
つまり、赤い矢印それぞれについて経路が重複することはないため、それぞれの赤い矢印について、そこを通る経路数を計算し、その総和を求めれば、それが水色のマスへの経路数になります。
そして、赤い矢印を通る経路数は、赤い矢印の始点である黄色いマスの経路数そのものです(からの矢印ならば、の経路数である)。よって、結果として矢印の経路数の総和である水色のマスの経路数は、
となりました。
例題(ABC154 F - Many Many Paths)
を求める問題です。
式変形をすると、
となり、ここでを使うと、
になります。これで計算量が落ち、答えを求めることができます。
(のときのため)
(少し展開してを削除)
(を外にだす)
(再びまとめる)
(をΣの外に出し、を0-indexedに直す)
(二項定理)
となります。
例題(ABC 150 E - Change a Little Bit)
提出コード
できるだけコストの小さいものから使用していくのが良いです。ということで、今回は全パターンの総和を求めるため、の順番を変えても差し支えないことから、を昇順でソートします。今後、は0-indexedだとします。
番目のビットを変化させるとします。このとき、問題文にも書いてあるように、残っている個数をとすると、のコストがかかります。
より小さい番号のビットはともにそろっているとします。これらはビット存在し、元々のビットパターンがの4通りなので、この部分は通り存在します。
番目のビットは、の2通り存在します。
さて、より後ろの部分は、ビット存在します。
この中で、ビットがで異なっているとします。ビットは初めからそろっていることになります。
そろっているビットはの2通り、異なるビットもの2通りです。ということで、ビットの組み合わせ自体は通りです。そして、ビットの中から、現在異なっているビットを選ぶのは、通りとなります。
そして、このときにコストはかかります。
については、の選び方があり、それぞれ総和を求めていかなければなりません。
長々と条件を書きましたが、これらを全てまとめて書くと、
2の累乗とを外に出してまとめると、
となります。さらにの部分を分配法則を用いて変形し、
*
とすると、および、二項定理から、
となります。これで計算量が落ち、答えを求めることができます。