Loading...
2/22/2025
頭が回っておらず誤読などもありで、ABCDFの遅めの5完に終わりました。苦しい。
面倒くさいですが愚直に4通り場合分けします。bit演算をすると場合分けが減って微妙に楽だったかも。提出
void solve() { string s, t; cin >> s >> t; string sick = "sick"; string fine = "fine"; if (s == sick && t == sick) cout << "1 "; else if (s == sick && t == fine) cout << "2 "; else if (s == fine && t == sick) cout << "3 "; else cout << "4 "; }
とを決めればの位置が決まるので、その3要素が条件を満たすかどうかを判定すればよいです。提出
#define rep(i,n) for (ll i=0;i<n;++i) #define rep2(i,a,n) for (ll i=a;i<n;++i) void solve() { string s; cin >> s; int n = s.size(); int ans = 0; rep(i, n) { rep2(j, i+1, n) { int d = j - i; int k = j + d; if(k >= n) continue; if (s[i] == 'A' && s[j] == 'B' && s[k] == 'C') { ans++; } } } cout << ans << ' '; }
実はの長さはたかだか100なので、愚直に3重ループを書いても良かったのですがこれが一番初めに思いついたのでそのまま実装しました。 ,,が全て同じ、と誤読しており、AのAC後6分とかなりの時間を使いました。もったいない...
これは(グラフの知っている必要がありますが)言われた通りのことをどう実現しますか?という問題です。
自己ループは、であるようなものを数えればよいので簡単です。問題は多重辺ですが、ある頂点から伸びている辺の集合を保持しておけば良く、RustであればBTreeSet
(あるいはHashSet
)で持っておけば十分高速に数えることができます。提出
use std::collections::BTreeSet; use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, m: usize, e: [(Usize1, Usize1); m], } let mut ans = 0; let mut g = vec![BTreeSet::new(); n]; for &(u, v) in e.iter() { if u == v || g[u].contains(&v) { ans += 1; } g[u].insert(v); g[v].insert(u); } println!("{}", ans); }
これも誤読をしていて、「木を構築する」だと思ってぜんぜん違う問題を解いていました。あの?
差分計算を頑張るやつです。
あるを中心に集めることを考えると、それより左側にある1
に対する操作回数と、右にある操作回数をで求めることができます。具体的には、以下の擬似コードのように求めることができます1。
j <- i
zero_count <- 0
operate_count <- 0
while j < |S|:
if s[j] == 0:
zero_count <- zero_count + 1
else:
operate_count <- operate_count + 1
ここで、に1加算したときの(つまりi <- i+1
で更新したときの)操作回数は、更新後のが0であれば左側にある1の個数だけ増えて右側にある1の個数だけ減ります。更新後のが1で合った場合には操作回数は変化しません。
これらを用いてから始めて差分計算をしていくことで、初期値が、差分計算をでできるため、この問題が十分高速に解けます。提出
use proconio::{input, marker::Chars}; fn main() { input!{ n: usize, s: Chars, } let mut l = 0u64; let mut r = 0; let mut cur = 0; { let mut z_cnt = 0; for i in 0..n { if s[i] == '0' { z_cnt += 1; } else { cur += z_cnt; r += 1; } } } let mut ans = INF; for i in 0..n { if s[i] == '0' { cur += l; cur -= r; } else if s[i] == '1' { r -= 1; ans.chmin(cur); l += 1; } } println!("{}", ans); }
そもそもLIS(最小増加部分列)をどうやって求めたかということを思い出すと、これはdp[i] := 長さiの最長増加部分であって、i番目の値としてあり得る最小値
とする動的計画法で、数列の長さに対して時間で求められるのでした。この動的計画法の配列は必ず狭義単調増加になります。
ここで問題をよく見ると、i番目のクエリは「番目の更新を行った後のdp配列のうち、を満たす最大ののインデックスを求めよ」というように言い換えることができます。よって、クエリ先読み+二分探索によって、この問題が時間で解くことができます。提出
実装ではそこまで頭が回っていないので「長さの最長増加部分列のうち番目の値としてあり得る最小値」を配列で持っていますが、これは不要です。
use itertools::Itertools; use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, q: usize, a: [u64; n], queries: [(Usize1, u64); q], } let mut ans = vec![0; q]; let mut qi = 0; let indicates = (0..q).sorted_unstable_by_key(|i| queries[*i].0).collect_vec(); let mut dp = vec![INF; n]; let mut mv = vec![INF; n]; for i in 0..n { let idx = dp.lower_bound(a[i]); dp[idx] = a[i]; mv[idx] = mv[idx].min(a[i]); while qi < q && queries[indicates[qi]].0 == i { let j = mv.lower_bound(queries[indicates[qi]].1); ans[indicates[qi]] = if j < n && mv[j] == queries[indicates[qi]].1 { j + 1 } else { j }; qi += 1; } } println!("{}", ans.iter().join(" ")); }
難しすぎ!
条件を満たすの約数の個数としてあり得る最大値は240個2ですから、これが全列挙できれば最大ケースでも回程度の計算で最大公約数を求めることができます。よって、に含まれる約数を高速に列挙することができればこの問題が解けそうです。
よって、元の問題が解けました。ただし、本当に全部の値を保持すると空間が足りなくなる可能性があるので、に含まれる値だけを持っておくとよいでしょう。提出
use itertools::Itertools; use proconio::input; static M: usize = 1e6 as usize + 2; fn mp(has: &[bool]) -> Vec<Vec<usize>> { let mut res = vec![vec![]; M]; let mut i = 2; while i < M { let mut j = i; while j < M { if has[j] { res[j].push(i); } j += i; } i += 1; } res } fn main() { input! { n: usize, k: usize, a: [usize; n], } let has = a.iter().fold(vec![false; M], |mut v, &ai| { v[ai] = true; v} ); let v = mp(&has); let mut cnt = vec![0; M]; for &ai in a.iter() { for &vi in v[ai].iter() { cnt[vi] += 1; } } let mut ans = vec![1; n]; 'i: for (i, &ai) in a.iter().enumerate() { for &vi in v[ai].iter().rev() { if cnt[vi] >= k { ans[i] = vi; continue 'i; } } } println!("{}", ans.iter().join(" ")); }
これは「どうせ差分計算をできるだろ」と思ってぐっと睨むとわかると思います ↩
高度合成数の一覧 - アルゴ式 本番中はそれぞれに対して約数列挙を行う方針を考えていましたが、これでは最悪ケースで間に合いません。 ここで、数列に含まれる数の約数を直接求めるのではなく、一気に列挙する方法を考えます。これは「ある値に対して、(条件の範囲内で)を約数に持つもの」を列挙する、という方針です。この方針でまでのものを列挙することを考えましょう。 のとき、1を約数に持つものはの個です。次に、のときは、の約個です。 この調子で列挙していくと、計算回数はとなり、これは調和級数の和なのでと高速に列挙することが可能です。 ↩