解法

DP. 状態を，$T$ の $[0,j)$ まで一致させたとして $j$ をもつ． $S_{i}$ を使えるかどうかは， $T_{[0,j)} + S_{i} = T_{[0,j+|S_{i}|)}$ と同値．

注意

substr は，範囲外にならない様に．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

string t; cin >> t;

ll n; cin >> n;

vector<vector<string>> s(n);

rep(i,n){

ll a; cin >> a;

s[i].resize(a);

cinv(s[i]);

}

// O(n * t.size() * sum_{i \in n and str \in s[i]} |str|)

ll inf = n+1;

vll dp(t.size()+1, inf);

dp[0] = 0;

int main() {
  string t; cin >> t;
  ll n; cin >> n;
  vector<vector<string>> s(n);
  rep(i,n){
    ll a; cin >> a;
    s[i].resize(a);
    cinv(s[i]);
  }

  // O(n * t.size() * sum_{i \in n and str \in s[i]} |str|)
  ll inf = n+1;
  vll dp(t.size()+1, inf);
  dp[0] = 0;
  rep(i,n) {
    drep(ti, t.size()+1) {
      for(auto str: s[i]){
        if(t.substr(ti, str.length()) == str){
          chmin(dp[ti + str.length()], dp[ti] + 1);
        }
      }
    }
  }

  ll ans = dp[t.size()];
  if(ans >= inf) ans = -1;
  cout << ans << endl;


  return 0;
}

drep(ti, t.size()+1) {

for(auto str: s[i]){

if(t.substr(ti, str.length()) == str){

chmin(dp[ti + str.length()], dp[ti] + 1);

}

ll ans = dp[t.size()];

if(ans >= inf) ans = -1;

cout << ans << endl;

return 0;

}

2024-03-18

PAST12K問題

PAST12K

解法

Easy

削除のみの場合．クエリを先読みして，逆に処理すれば，union-find で解ける．

Normal

追加と削除の場合．ただし，追加する辺が 10個以下．
この場合もベースになるのは Easy版で，クエリ先読みと逆順処理をする．もとのクエリで追加する辺(逆順処理では削除する辺)は少ないので，その度に union-find を構成しなおしても間に合う．

実装

Union-find を再構成するために，逆順で処理したときに，追加した辺を記録しておく．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

ll n,m;

cin >> n >> m;

UnionFind<ll> uf;

set<pll> es;

rep(i,m){

ll a,b; cin >> a >> b;

--a, --b;

es.insert({a,b});

}

ll q; cin >> q;

vector<tuple<ll,ll,ll>> qs;

rep(qi,q){

ll t,x,y; cin >> t >> x >> y;

--x,--y;

qs.emplace_back(t,x,y);

if(t == 1){

es.insert({x,y});

}else if(t == 2){

assert(es.find({x,y}) != es.end());

es.erase({x,y});

}

reverse(all(qs));

auto create_uf = [&](void) -> UnionFind<ll> {

UnionFind<ll> ret(n);

for(auto [a,b]: es){

ret.merge(a,b);

}

return ret;

};

uf = create_uf();

vector<string> ans;

for(auto [t,x,y]: qs){

if(t == 1){

es.erase({x,y});

uf = create_uf();

}else if(t == 2){

es.insert({x,y});

uf.merge(x,y);

}else{

ans.push_back(uf.same(x,y) ? "Yes" : "No");

}

reverse(all(ans)); // rem: reverse

for(auto s: ans){

cout << s << endl;

}

return 0;

}

2024-03-16

PAST12H問題

PAST12H

解法

貨幣の枚数を考える．組(金貨，銀貨，銅貨) が辞書順で最大になるのがベスト．銅貨の残り枚数を状態にもって DP すれば O(NX).

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

pll operator + (pll a, pll b){

return make_pair(a.first + b.first, a.second + b.second);

}

int main() {

ll n,x;

cin >> n >> x;

vll a(n), b(n), c(n);

rep(i,n){

cin >> a[i] >> b[i] >> c[i];

}

// r: remainder bronze

vector<pll> dp(x+1, {-1, -1});

dp[x] = {0,(ll)1e9};

rep(i,n) {

rep(br,x+1){

if(br - b[i] >= 0) chmax(dp[br - b[i]], dp[br] + make_pair(c[i], -a[i]));

}

tuple<ll,ll,ll> ans(-1,-1,-1);

rep(br,x+1){ // get bronze

auto [g,s] = dp[br]; // get gold, get silver

chmax(ans, make_tuple(g, s, br));

}

auto [p,q,r] = ans;

cout << p << " " << q << " " << r << endl;

return 0;

}

2024-03-15

PAST12G問題

PAST12G

解法

何を全探索するか考える．素直に $T$ を全探索するのでは $TLE$ ． $T$ は全探索できないが，$T$ の $?$ の位置は，最大で ${}_{10}C_{5} = 252$なので十分間に合う．
まず $S := S_{i}$ を一つ固定して考える． $?$ の位置だけ固定したとき， $S$ から $T$ を作れる条件を考える． $j \in T.size()$ において，

$T_{j} = '?'$ なら，$S_{j}$ は何でもよい．
$T_{j} \neq '?'$ なら，$S_{j} = T_{j}$ が必要．

よって，全ての $j \in |T|$ with $T_{j} = '?'$ となる $j$ に対して $S_{j}$ を $'?'$ で置き換えて， $S = T$ となることが，$S$から $T$ を作れる必要条件．これが十分条件であることは明らか．
次に $i \in N$ を動かして考えてみるが，これは全体で $O({}_{L}C_{L/2} N)$ となる．ただし，$S_{i}$ の一部を $?$ で置き換えた文字列の個数をカウントするときに map を使っているので，オーダーに $max_{i \in N} (|S|) log N$ が掛かる．

実装

$?$ の取り方は bitmask を用いると簡単． $?$ の選び方 $\in 2^{L}$ のうち，popcount が $K$ の物だけ使えばよい．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

ll n,l,k;

cin >> n >> l >> k;

vector<string> s(n); cinv(s);

ll ans = 0;

rep(msk, 1LL << l) if(pcntll(msk) == k){

vector<string> ns = s;

rep(i,n) rep(j,l) if(msk >> j & 1) ns[i][j] = '?';

map<string,ll> cnt;

rep(i,n) cnt[ns[i]]++;

for(auto [_,c]: cnt){

chmax(ans, c);

}

cout << ans << endl;

return 0;

}

2024-03-14

PAST15 J問題

PAST15J

問題の言い換え

ダメージの累計が最小になる様に手裏剣を使う．

思考の流れ

いくつか思いつくことがある．

まず暫定的な答えを出す．これは簡単に求まるというのが大事．手裏剣を 0枚使ったときの求めて，その答えを修正していく．手裏剣 1枚でどれくらい得をするのかを考える．
敵が 1体のときに，$x = 0, 1$ で場合分けして考える．
敵が $N$ 体で，全て $x = 0$ の場合を考える． $x = 1$ の場合は，手裏剣を投げることで $x=0$ に帰着できるから．

それぞれについて詳しく見ていく．
敵が 1体のとする．手裏剣を $u$ 枚使ったとする．

$x = 0$ なら $b-u-1$ 回攻撃を食らう．これは $u=0$, $u > 0$ による場合分けは不要．
$x = 1$ なら，手裏剣を投げるかどうかで場合分け．
- $u = 0$ のときは，$b - u$ 回攻撃をくらう．
- $u > 0$ のとき
  - $b > 1$ のとき，先手をとれるおかげで $b-u-1$ 回攻撃をくらう．
  - $b = 1$ のとき，0回攻撃を食らう．

まとめると， $x = 1$のときは基本的に手裏剣 1枚目だけダメージが $2a$ 得するが， $b = 1$ のときは $a$ 得する． $1$ 枚投げれば，$x = 0$ に帰着できる． $x = 0$のときは，1枚につき $a$ 得する．
また，手裏剣を 0枚使ったときの暫定的な答えはすぐに求まる．

注意

$x = 1$ かつ $b = 1$ のときは，手裏剣を $1$枚投げても $a$ しか得をしない．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

ll n,m;

cin >> n >> m;

using T = tuple<ll,ll,ll,ll>;

priority_queue<T> ts;

ll dmg = 0;

rep(i,n){

ll a,b,x; cin >> a >> b >> x;

ll c = (x+1) * a;

if(b == 1) c = a; // b == 1 && x == 1

ts.push({c, a, b, x});

dmg += (b-(!x))*a; // 手裏剣を使わなかったときのダメージ

}

// 手裏剣を上手に配分してダメージを減らす

while(ts.size() && m > 0){

auto [c, a, b, x] = ts.top(); ts.pop();

if(x == 1){

dmg -= c;

m--;

b--;

if(b > 0) ts.push({a,a,b,0}); // x = 1 は 1枚目の手裏剣だけ特別．2枚目以降は x = 0 に帰着．

}else{

ll use = min(m, b-1);

m -= use;

dmg -= use * a; // 手裏剣を使ってどれだけ得するか

}

cout << dmg << endl;

return 0;

}

2024-03-13

PAST14 L問題

PAST14L

準備

$A$ が $B$ より強いと分かっているとき，かつそのときに限り $A$ から $B$ に矢を張ったグラフ $G$ を考える．

問題

Easy

辞書順を無視して，強い順に並べる．これは $G$ においてトポロジカルソートするのと同じ．

Normal(本問)

辞書順最小の，強い順に並べる．トポロジカルソートで頂点を並べるとき，選ぶ頂点の候補が複数あれば最小の物を選ぶようにすればよい．これは，入次数 0 の頂点を入れる入れ物として， min priority queue を用いれば良い．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

ll n,m;

cin >> n >> m;

vvll to(n);

vll in(n);

rep(i,m){

ll a,b; cin >> a >> b;

--a, --b;

to[a].emplace_back(b);

in[b]++;

}

min_priority_queue<ll> q;

rep(i,n){

if(in[i] == 0) q.push(i);

}

vll ans;

while(q.size()){

ll c = q.top(); q.pop();

ans.push_back(c+1);

for(auto d: to[c]){

in[d]--;

if(in[d] == 0) q.push(d);

}

assert(ans.size() == n);

coutv(ans);

return 0;

}

2024-03-13

PAST15 K問題

$\def \set #1#2{\{ #1 \ \vert \ #2 \}}$

PAST15K

解法

コストの最小を求めるが，下界を求めてそれを実現する例を与える．下界を求める過程は，必要条件を求めるのに近い．

Sub problem: コスト無し

コストを無視して $P_{i}$ と $P_{i+1}$ の swap を考える． $P$ を昇順にするには，小さい $P_{i}$ から左に寄せていくと，少ない回数でソートできる．

Sub problem: コスト有り

コストがある場合も，コスト無しの場合と似た方法で出来る． $P_{[0,i)}$ までソートされているとして，$i = P_{i}$ となるように並べ替えることを考える．このとき，最低でも掛かるコストを求める．集合$X$を， $i$ の左にある $P$ の元のうち，$i$ より大きい元全体とする． $i = P_{i}$ となるまで並べ替えるためには，最低 $$ \sum_{x \in X} (i + x) = |X|\cdot i + \sum X $$ かかる．実際にこのコストでのソートが実現できるのは，コスト無し版の解法から分かる．

実装

この解法には，次が有れば十分．任意の $i \in N$ に対して，

$| \set{j \in i }{ P_{j} > P_{i} } | $,
$\sum \set{P_{j}}{ j \in i \ and \ P_{j} > P_{i} }$.

これらは，共に segtree で実現出来る．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

ll op(ll a, ll b){ return a+b; }

ll e() {return 0;}

int main() {

ll n;

cin >> n;

segtree<ll,op,e> perm(n);

segtree<ll,op,e> cnt(n);

vll pos(n+1);

rep(i,n){

ll x; cin >> x;

perm.set(i,x);

cnt.set(i,1);

pos[x] = i;

}

ll ans = 0;

rep1(i,n){

ll p = pos[i];

ans += perm.prod(0,p);

ans += cnt.prod(0,p) * i;

perm.set(p, 0);

cnt.set(p, 0);

}

cout << ans << endl;

return 0;

}

競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 344D問題

解法

注意

PAST12K問題

解法

Easy

Normal

実装

PAST12H問題

解法

PAST12G問題

解法

実装

PAST15 J問題

問題の言い換え

思考の流れ

注意

PAST14 L問題

準備

問題

Easy

Normal(本問)

PAST15 K問題

解法

Sub problem: コスト無し

Sub problem: コスト有り

実装