ちょい伸び
びのび
— ボンド@競プロ (@bond_cmprog) 2020年5月2日
Bondo416さんのAtCoder Beginner Contest 165での成績:1289位
パフォーマンス:1458相当
レーティング:1378→1386 (+8) :)#AtCoder https://t.co/H6aL259Ofg
A - We Love Golf
を全探索すればいい
提出コード
void solve(){ int K, A, B; cin >> K >> A >> B; for(int i=A;i<=B;i++){ if(i % K == 0){ cout << "OK" << endl; return; } } cout << "NG" << endl; }
B - 1%
愚直にシミュレートする
サンプルに最大ケースあるの優しいね
後はオーバーフローに注意?
提出コード
void solve(){ ll X; cin >> X; ll cur = 100; int ans = 0; while(cur < X){ cur += cur / 100; ans++; } cout << ans << endl; }
C - Many Requirements
読解が難しかった
を満たす場合の数は
重複組合せを考えるとで最大ケースでも十分に間に合う
そのため、dfsなどで全探索をすればいい
コンテスト中はこれを思い出してた
atcoder.jp
void solve(){ int N, M, Q; cin >> N >> M >> Q; vector<int> a(Q), b(Q), c(Q), d(Q); REP(i,Q){ cin >> a[i] >> b[i] >> c[i] >> d[i]; --a[i],--b[i]; } ll ans = 0; auto dfs = [&](auto && dfs, vector<int> v) -> void{ if(v.size() == N){ ll tmp = 0; REP(i,Q){ if(v[b[i]] - v[a[i]] == c[i]){ tmp += d[i]; } } chmax(ans, tmp); } else{ if(v.empty()){ for(int i=1;i<=M;i++){ auto tmp = v; tmp.push_back(i); dfs(dfs, tmp); } } else{ for(int i=v.back();i<=M;i++){ auto tmp = v; tmp.push_back(i); dfs(dfs, tmp); } } } }; vector<int> v; dfs(dfs, v); cout << ans << endl; }
D - Floor Function
これ難しい
手元で実験してみると、周期性があって、B-1のときに最大になっていることがわかる
なので、のときの答えを出力する
提出コード
void solve(){ ll A, B, N; cin >> A >> B >> N; ll mi = min(B-1, N); cout << (A * mi) / B << endl; }
E - Rotation Matching
こういうパズルっぽいの解けるようになる気がしないなあ
端同士の点と、真ん中の2点を取る
端 -> 真ん中 -> 端 -> ...の順に交互に取っていき、端は真ん中に、真ん中は端に寄せていく
2点(i, j)の差分の mod Nが重複しないようにするってことを考えるのが良いのかな
提出コード
void solve(){ int N, M; cin >> N >> M; int a = 1, b = N - 1, c = N / 2, d = N / 2 + 1; REP(i,M){ if(i & 1) cout << a++ << " " << b-- << endl; else cout << c-- << " " << d++ << endl; } }
F - LIS on Tree
言われてみるとそれはそうなんだけど通す人々が多くて強いなーってなった
まず、パスで考えると普通のLISを解けばいい
木上で考えると、ある葉までのパス上の頂点はLISを更新していけばいい
後は、帰りがけのときにDPの更新を戻してあげればいい
これは行きがけのときにDPの値をメモっておいて、帰りがけのときにロールバックをしてあげると、で解くことが出来る
提出コード
void solve(){ int N; cin >> N; vector<int> a(N); REP(i,N) cin >> a[i]; vector<vector<int>> G(N); REP(i,N-1){ int u, v; cin >> u >> v; --u, --v; G[u].emplace_back(v); G[v].emplace_back(u); } vector<int> ans(N, INF); vector<int> dp(N+1, INF); dp[0] = -INF; auto dfs = [&](auto && self, int cur, int par) -> void{ int idx = lower_bound(dp.begin(), dp.end(), a[cur]) - dp.begin(); int tmp = dp[idx]; dp[idx] = a[cur]; ans[cur] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin() - 1; for(auto nv : G[cur]){ if(nv == par) continue; self(self, nv, cur); } dp[idx] = tmp; }; dfs(dfs, 0, -1); for(auto x : ans) cout << x << endl; }
おわりに
青difficulty解けないなあ精進しないと