Loading...
1/29/2025
あまり良くない勝ち方でしたが、とはいえ5完で勝ち。最近は連勝できているのでこの調子でレートを増やしたいです。
埋め込むかどうかで少し迷いますが、5個は少し多いなーと思ったのでシミュレーションします。url
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (ll i=0;i<n;++i) void solve() { int a[5]; int n = 5; rep(i, n) cin >> a[i]; rep(i, 4) { swap(a[i], a[i+1]); bool flag = true; rep(j, 5) { if (a[j] != j+1) flag = false; } if(flag) { cout << "Yes "; return; } swap(a[i], a[i+1]); } cout << "No "; }
等比数列ってなんでしたっけ(あの?)となったのでググります。1つめの比をベースとして、それと全て同じになっていることを判定すれば良さそうです。ただし、小数演算は誤差が怖いので
と式変形をして小数を用いずに判定すれば安全にACできます。提出
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for (ll i=0;i<n;++i) void solve() { int n; cin >> n; ll a[n]; rep(i, n) cin >> a[i]; rep(i, n-1) { if (a[1] * a[i] != a[0] * a[i+1]) { cout << "No "; return; } } cout << "Yes "; }
また、言語によりますが、有理数ライブラリを利用するのも手かと思います。有理数ライブラリ解(Rust)
use itertools::Itertools; use num_rational::Ratio; use proconio::input; fn main() { input! { n: usize, a: [u64; n], } println!( "{}", if a.iter() .tuple_windows() .map(|(&a, &b)| Ratio::new(a, b)) .all_equal() { "Yes" } else { "No" } ); }
黒マスの内、最も右/左/下/上にあるもの場所を記録します。その内側にあるものは黒の領域で外側は白の領域となるので、内側の領域に白いマスが存在しないことを判定すればよいです。 提出
void solve() { int h, w; cin >> h >> w; vector<string> bd(h); rep(i, h) cin >> bd[i]; ll l=w, r=-1, u=h, d=-1; rep(i, h) rep(j, w) { if (bd[i][j] == '#') { chmin(l, j); chmin(u, i); chmax(r, j); chmax(d, i); } } if(l==w) { cout << "Yes "; return; } rep(i, h) rep(j, w) { if(bd[i][j] == '.') { if(l <= j && j <= r && u <= i && i <= d) { cout << "No "; return; } } } cout << "Yes "; }
見るからに全探索です。しかも、特に工夫のいらない全探索に見えます。というのも、うまくやることで省略できるという要素がなさそうで、しかも特にメモ化できる要素が無い1ので、再帰で全列挙すればよいです。提出(1142ms)
use std::collections::BTreeSet; use proconio::input; fn dfs(v: &mut Vec<u64>, i: usize, a: &Vec<u64>, ans: &mut BTreeSet<u64>) { if i == a.len() { ans.insert(v.iter().fold(0, |acc, &x| acc ^ x)); return; } for j in 0..v.len() { v[j] += a[i]; dfs(v, i + 1, a, ans); v[j] -= a[i]; } v.push(a[i]); dfs(v, i + 1, a, ans); v.pop(); } fn main() { input! { n: usize, a: [u64; n], } let mut ans = BTreeSet::new(); dfs(&mut Vec::new(), 0, &a, &mut ans); println!("{}", ans.len()); }
計算量解析はせずにまぁ間に合うだろで投げましたが、このような区別できる要素を1つ以上のグループに分ける場合の数のことをベル数というらしいです2。番目のベル数をと書くことにすると、計算量はとなります。、のとき、でありですから、じつはかなりの定数倍勝負だったみたいです。特に、C++ではstd::set
が実はあまり早くないこともありかなりの人が沼にハマったようでした。
Rustでも、BTreeSet
ではなく単にVec
に入れておいて、最後にsortしてdedupすることでより高速に解くことができました。提出(Rust, 369ms)
まず、シンプルなdpが見えました。dp[i][j][k] := カロリーi, ビタミン1がj, ビタミン2がkだけ接種したときのビタミン3としてあり得る最大値
としたい気持ちになりますが、困ったことにメモリが全然足りません。無限のメモリを使いたい。
仕方がないので別の方針を考えます。よく見ると各食べ物はビタミンを1つしか持っていないので、それぞれについて「カロリーiだけ接種したときの接種ビタミンとしてあり得る最大値」とすれば、これはで求めることができます。さらに、この結果を用いて、「カロリーを以下だけ接種したときに、各ビタミンを以上接種することは可能か?」を判定して二分探索をすることによって、でこの問題を解くことができます。
なお、本番の私は何を考えたか毎回動的計画法をやり直すという実装をしました3が、ぎりぎり通ったのでOK。提出(1653ms)
use proconio::{input, marker::Usize1}; fn dp(key: i64, x: usize, v: &Vec<(i64, usize)>) -> usize { let mut dp = vec![-1; x + 1]; dp[0] = 0; for &(a, c) in v { for i in (0..x + 1).rev() { if i + c >= x + 1 { continue; } let val = dp[i] + a; dp[i + c].chmax(val); } } // key以上で最小のindex for (i, &xi) in dp.iter().enumerate() { if xi >= key { return i; } } return x + 1; } fn main() { input! { n: usize, x: usize, v: [(Usize1, i64, usize); n], } let v = v.iter().fold(vec![vec![]; 3], |mut v, &(i, a, c)| { v[i].push((a, c)); v }); let mut ok = 0; let mut ng = 1e18 as i64; while ng - ok > 1 { let mid = (ok + ng) / 2; let s = (0..3) .into_iter() .map(|i| { let res = dp(mid, x, &v[i]); res }) .sum::<usize>(); if s <= x { ok = mid; } else { ng = mid; } } println!("{}", ok); }
手も足も出ず。ある区間を削除する際に、できるだけ長い区間を削除したいです。具体的には、3, 2, 4, 6, 7
が与えられたときは、を選んで数列を6, 7
とし、その後を選ぶのが最適となります。
ここで答えを求めることは難しいので、数え上げる対象を読み替えることにします。すべての操作を行った結果、それぞれについてとして削除を行った回数を数え上げることができれば、この問題を解くことができます。
ここで、操作においてとして削除を行う条件を考えると、それは「対象の区間においてなるが存在しない」です。なぜなら、そのようなが存在するのであればそちらを左端として処理するほうが良いからです。逆に言うと、そのようなが出てくるまでの間はとして削除するのが最適となりますから、であるであってを満たすようなのうち最も大きいもの(存在しなければとする)と、であるであってを満たすようなのうち最も小さいものが高速にわかれば良く、これは二分探索などを用いることで対数時間で求めることができます。 また、同じ区間を重複して数えてしまうケースがあるため、「削除する区間に同じ値が含まれる場合は最も左にある値を使う」というルールをつけ、上とのmaxをとることで重複を排除できます。
以上より、この問題がと十分高速に解くことができます。なお、実装が辛いなーと言いながら工夫をしていたらになっていました。。提出
use proconio::input; fn main() { input! { n: usize, a: [usize; n], } let mut v = vec![vec![]; n + 1]; let mut idxes = vec![None; n + 1]; for (i, &ai) in a.iter().enumerate() { v[ai].push(i); if idxes[ai].is_none() { idxes[ai] = Some(0); } } let mut ans = 0; let mut last_seen = vec![None; n + 1]; for (i, &ai) in a.iter().enumerate() { let mut l = if let Some(idx) = last_seen[ai - 1] { idx as i64 } else { -1 }; l = l.max(if let Some(idx) = last_seen[ai] { idx } else { -1 }); let r = if let Some(idx) = idxes[ai - 1] { v[ai - 1][idx] as i64 } else { n as i64 }; if idxes[ai].unwrap() + 1 == v[ai].len() { idxes[ai] = None; } else { idxes[ai] = Some(idxes[ai].unwrap() + 1); } last_seen[ai] = Some(i as i64); ans += (i as i64 - l) * (r - i as i64); } println!("{}", ans); }