Loading...
12/22/2024
途中までかなりあやしかったものの,なんとか5完に漕ぎ着けました...
場合分けとしてありうるのは5通りなので、全部書きます。 提出
a, b, c = map(int, input().split()) if a + b == c or a + c == b or b + c == a or a == b == c: print("Yes") else: print("No")
[[ABC384]]からGitHub Copilotを使っていますが、こういうときに補完をいい感じにしてくれるので見た目の割には書くのに苦労していません。
移動の処理は言われたとおりに頑張るとして、一度通った家を重複して数えないように一度通ったマスをdfs/bfsでやるような要領で管理すればよいです。 提出
di = [0, 1, 0, -1, 1, 1, -1, -1] dj = [1, 0, -1, 0, 1, -1, 1, -1] dc = 'RDLU' h, w, i, j = map(int, input().split()) s = [input() for _ in range(h)] t = input() seen = [[False] * w for _ in range(h)] ans = 0 i -= 1 j -= 1 for c in t: for r in range(4): if dc[r] != c: continue ni, nj = i + di[r], j + dj[r] if ni < 0 or h <= ni or nj < 0 or w <= nj or s[ni][nj] == '#': break if not seen[ni][nj] and s[ni][nj] == "@": ans += 1 seen[ni][nj] = True i, j = ni, nj break print(i + 1, j + 1, ans)
D問題でも思いましたが、終わったときの場所を出力させる問題というのはまた珍しいなぁなどと思いました。どういう意図なんだろう?特に深い理由はないんかな
開始点のビルと、電飾で飾るビルの間隔を決めると選ぶことができるビルの数が求まります。よって、これらを全探索すればよいです。多分調和級数の和なのでぐらいで間に合います。証明はAC(は?) 提出
use proconio::{input, marker::Usize1}; fn main() { input!{ n: usize, h: [Usize1; n], } let mut ans = 1; for i in 0..n { for steps in 1.. { if i + steps >= n { break; } let mut tmp = 1; let mut k = steps; while i + k < n { if h[i + k] == h[i] { tmp += 1; k += steps; } else { break; } } ans.chmax(tmp); } } println!("{}", ans); }
であるような家の列をmap<int, set<int>>
で持ちます。各移動に対して、その移動で通過する家のうち最小・最大のものがlogで求めることができるので、そのような家を取得→重複を防ぐために削除を繰り返せばよいです。
とくに、削除をすることで取得される家の数は最大で個なので、全体ででシミュレートすることができます。
できるんですが、実装がとにかく辛いです。 提出
#define int long long #define rep(i, n) for (int i = 0; i < (int)(n); i++) void solve() { int n, m; int si, sj; cin >> n >> m >> si >> sj; vector<pair<int, int>> home; rep(i, n) { int x, y; cin >> x >> y; home.push_back({x, y}); } vector<pair<char, int>> move; rep(i, m) { char c; int d; cin >> c >> d; move.push_back({c, d}); } map<int, set<int>> home_i; map<int, set<int>> home_j; rep(i, n) { home_i[home[i].first].insert(home[i].second); home_j[home[i].second].insert(home[i].first); } int ans = 0; int now_i = si; int now_j = sj; rep(i, m) { char c = move[i].first; int d = move[i].second; if (c == 'L') { int target = now_i - d; auto itr = home_j[now_j].lower_bound(target); if (itr == home_j[now_j].end()) { now_i = target; continue; } else { while(itr != home_j[now_j].end() && *itr <= now_i) { ans++; home_i[*itr].erase(now_j); itr = home_j[now_j].erase(itr); } now_i = target; } } else if (c == 'R') { int target = now_i + d; auto itr = home_j[now_j].lower_bound(now_i); if (itr == home_j[now_j].end()) { now_i = target; } else { while(itr != home_j[now_j].end() && *itr <= target) { ans++; home_i[*itr].erase(now_j); itr = home_j[now_j].erase(itr); } now_i = target; } } else if (c == 'U') { int target = now_j + d; auto itr = home_i[now_i].lower_bound(now_j); if (itr == home_i[now_i].end()) { now_j = target; } else { while(itr != home_i[now_i].end() && *itr <= target) { ans++; home_j[*itr].erase(now_i); itr = home_i[now_i].erase(itr); } now_j = target; } } else if (c == 'D') { int target = now_j - d; auto itr = home_i[now_i].lower_bound(target); if (itr == home_i[now_i].end()) { now_j = target; } else { while(itr != home_i[now_i].end() && *itr <= now_j) { ans++; home_j[*itr].erase(now_i); itr = home_i[now_i].erase(itr); } now_j = target; } } } cout << now_i << " " << now_j << " " << ans << endl; }
Rustはループをしながら削除、というような操作は所有権の問題で辛い(実際どうなるかはわからないけど、辛い予感がした)のでC++を選択しましたが、C++のイテレータの仕様周りでとにかく躓きました。C++難しいよ〜
以降、は問題文で述べられている「ユ木」を生成する際に選ぶ値を指します。
削除する頂点数の最小化ではなく、残す頂点数の最大化を考えます。 根を一つ決めると、については考える必要がなくのみに着目すればよいです。また、の候補としてありうるのは根と隣接する頂点(以降は公式解説と合わせて"一層目の頂点"と呼びます)が持つ部分木の数です1。 これを大きい方から全探索すると、一層目の頂点のうち部分木の数が大きいほうから番目の部分木の個数をとして採用するとき、残る頂点の数は2とで求めることができるので、全体ででこの問題を解くことができます。 提出
use proconio::{input, marker::Usize1}; fn main() { input! { n: usize, edges: [(Usize1, Usize1); n - 1], } let mut g = vec![vec![]; n]; for (u, v) in edges { g[u].push(v); g[v].push(u); } let mut deg = vec![0; n]; for i in 0..n { deg[i] = g[i].len(); } let mut m_size = 1; for v in 0..n { let mut lc: Vec<usize> = g[v] .iter() .map(|&u| deg[u] - 1) .collect(); lc.sort_unstable_by(|a, b| b.cmp(a)); let d = lc.len(); let mut tmp = 1; for k in 1..=d { let y = lc[k - 1]; let size = 1 + k * (1 + y); if size > tmp { tmp = size; } } if tmp > m_size { m_size = tmp; } } let ans = n - m_size; println!("{}", ans); }
本当にギリギリのところでDとEを通せたことで勝利しましたが、1300↑とそろそろ自分の適正レートから上振れしているなぁと感じるぐらいのレート帯になってきました。しばらくはレートの維持が目標になってきそうです。