A. Cubes Sorting
何もわからなかったので座圧BITで転倒数を求めた
提出コード
void solve(){ ll n; cin >> n; vector<ll> a(n); map<ll, int> mp; REP(i,n){ cin >> a[i]; mp[a[i]] = 1; } int cnt = 1; for(auto [v, k] : mp){ mp[v] = cnt; cnt++; } BIT<ll> bit(n); ll res = 0; REP(i,n){ res += i - bit.sum(mp[a[i]]); bit.add(mp[a[i]], 1); } if(res <= n * (n - 1) / 2 - 1) cout << "YES" << endl; else cout << "NO" << endl; }
B. Rock and Lever
こどふぉで割とよく見るやつ
bitが立っている最上位部分が同じならbitwise andはそのままbitwise xorは打ち消し合うのでbitwise andの操作を行ったものが必ず大きくなる
そのため桁目に立っているbitが最上位のものの個数を管理し、その個数分足していく
提出コード
void solve(){ int n; cin >> n; vector<ll> a(n); REP(i,n) cin >> a[i]; vector<ll> bit(40); ll ans = 0; REP(i,n){ ll b = 0; for(ll j=30;j>=0;j--){ if(a[i] >> j & 1){ b = j; break; } } ans += bit[b]; bit[b]++; } cout << ans << endl; }
C1. Pokémon Army (easy version)
j個目まで見たとき、次に+を取るならi=1, -を取るならi=0
としてDPをしたときの最大値を出力
提出コード
void solve(){ int n, q; cin >> n >> q; vector<int> a(n); REP(i,n) cin >> a[i]; vector<vector<ll>> dp(2, vector<ll>(n+10, -LINF)); dp[1][0] = 0; REP(i,n){ chmax(dp[0][i+1], dp[0][i]); chmax(dp[1][i+1], dp[1][i]); chmax(dp[0][i+1], dp[1][i] + a[i]); chmax(dp[1][i+1], dp[0][i] - a[i]); } ll ans = 0; REP(i,2) REP(j,n+1) chmax(ans, dp[i][j]); cout << ans << endl; }
D. Rescue Nibel!
区間の左側と右側をvectorに入れて、ソートをする
これを昇順に見ていき、区間の左側なら個数を1個足す、右側なら個数を1個引くを繰り返す
区間の左側のときに、個数がK個以上なら今の個数をcntとするとを加算する
ただし、すでに加算したものも重複して加算してしまうので
その前の状態引いてあげればいい
提出コード
void solve(){ int n, k; cin >> n >> k; vector<pair<ll, int>> vp; REP(i,n){ ll l, r; cin >> l >> r; vp.emplace_back(10*l, -1); vp.emplace_back(10*r+1, 1); } sort(vp.begin(), vp.end()); ll cnt = 0; mint ans = 0; for(auto [t, c] : vp){ // dumps(t, c); if(c == -1){ cnt++; if(cnt >= k) ans += bc.com(cnt, k) - bc.com(cnt-1, k); } else cnt--; } cout << ans << endl; }