問題リンク
問題A. 木を掘って火を起こす
S * V >= n さえ満たせばよい
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2010,mod = 1e9 + 7;
int n,s,v;
void solve() {
cin >> n >> s >> v;
if(s * v >= n)
cout << 1 << endl;
else cout << 0 << endl;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int h_h = 1;
cin >> h_h;
while(h_h--)solve();
return 0;
}
コードを見る問題B. 奇妙な配列
等号の数は ai mod m = 0 の個数を数えることで求められる。 less than の数は求めにくいので、 greater than の数を計算する。すべての ai を m で剰余を取る操作は結果に影響しない。なぜなら 0 ≤ bi+1 − bi < m であるからである。
bi mod m > bi+1 mod m ⇐⇒ ⌊bi/m⌋ < ⌊bi+1/m⌋
全体的に考えると、 greater than の数は ⌊ bn / m ⌋ になる。
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2e3 + 10;
//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<int, int > mp;
int n,m,t,k;
priority_queue <int,vector<int>,greater<int> > Q;
void solve()
{
cin >> k;
vector<int> a(k);
for(int i = 0;i < k;i++)
cin >> a[i];
int x;
cin >> n >> m >> x;
for(int i = 0;i < k;i++)
a[i] %= m;
int sum = x % m;
int num = 0;
for(int i = 0;i < k;i++)
num += a[i];
sum += n / k * num;
for(int i = 0;i < n % k;i++)
sum += a[i];
cout << n - sum / m << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int Ke_scholar = 1;
//cin >> Ke_scholar;
while(Ke_scholar--)
solve();
return 0;
}
/*
*/
コードを見る問題I. 木構造
各ノードに答えを直接保持する。操作1において、パスの両端以外のノードは答えが変わらないことが分かる。したがって、操作1では両端のノードにその値をxorするだけでよい。操作2ではそのまま出力すれば良い。
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6+10, mod = 1e9 + 7;
//typedef long long ll;
typedef pair<int,int> PII;
int n,m,t,k;
map<int,int> mp;
priority_queue<int> QQ;
deque<int> Q;
void solve() {
cin >> n >> m;
vector<PII> a[n + 1];
vector<int> sum(n + 1,0);
for(int i = 1;i < n;i++){
int x,y,z;
cin >> x >> y >> z;
a[x].push_back({y,z});
a[y].push_back({x,z});
}
for(int i = 1;i <= n;i++){
for(auto j : a[i])
sum[i] ^= j.second;
}
while(m--){
int op;
cin >> op;
if(op == 1){
int x,y,z;
cin >> x >> y >> z;
sum[x] ^= z;
sum[y] ^= z;
}
else{
int x;
cin >> x;
cout << sum[x] << endl;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
//cin >> Ke_scholar;
while(Ke_scholar--)
solve();
return 0;
}
/*
*/
コードを見る問題J. 関数
正の整数 n (1 ≤ n ≤ 10^5) と n 個の二次関数が与えられる。i番目の関数は y = (x − i)^2 + bi (1 ≤ bi ≤ n) の形をしている。
正の整数 m (1 ≤ m ≤ 10^5) が与えられ、操作回数を示す。
操作には二種類ある。一つ目は、係数が1の二次関数を追加するもので、y = (x − a)^2 + b (1 ≤ a, b ≤ n) の形式となる。二つ目は、すべての二次関数について x = a (1 ≤ a ≤ n) における最小値を求める操作である。
具体的には、各操作はまず操作のタイプを示す。0は一つ目の操作、1は二つ目の操作を意味する。一つ目の操作では a と b という二つの正の整数を与える。二つ目の操作では a という正の整数を与える。
x = a における最小値を求める際、最小値になる可能性がある関数は左右の平方根の範囲内に限られる。したがって、左右の平方根の範囲内ですべての関数を走査し、最適解を見つけるだけである。
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
#define LB long double
using namespace std;
const int N = 1000000000, mod = 1e9 +7;
//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<char, int > mp;
//priority_queue <LB,vector<LB>,less<LB> > Q;
int n,m,t,k;
/*
*/
string s;
void solve()
{
cin >> n;
vector<int> b(n + 1);
for(int i = 1;i <= n;i++)
cin >> b[i];
int sn = sqrt(n);
int q;
cin >> q;
while(q--){
int op;
cin >> op;
if(op){
int x;
cin >> x;
int res = LONG_LONG_MAX;
for(int i = x - sn; i <= sn + x + 1;i ++){
if(i >= 0 && i < n && b[i])
res = min(res, (i - x) * ( i - x) + b[i]);
}
cout << res << endl;
}
else{
int x,y;
cin >> x >> y;
if(b[x])
b[x] = min(y, b[x]);
else
b[x] = y;
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int Ke_scholar = 1;
// cin >> Ke_scholar ;
while(Ke_scholar--)
solve();
return 0;
}
コードを見る問題K. 分割
実際には n 個の数の差を事前に処理し、ソートして累積和を求める。操作0ではこの差は一切変更されない。操作1では整数 k を与え、n - k - 1 の累積和を求める。
#include<bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0;i < n;i ++)
cin >> a[i];
int q;
vector<int> ve;
for(int i = 1;i < n;i ++){
int x = abs(a[i] - a[i - 1]);
ve.push_back(x);
}
sort(ve.begin(),ve.end());
map<int,int> mp;
for(int i = 0;i < ve.size();i++){
if(i == 0)
mp[i] = ve[i];
else
mp[i] = ve[i] + mp[i - 1];
}
cin >> q;
while(q--){
int op;
cin >> op;
if(!op){
int x;
cin >> x;
a[x - 1] = a[x] + a[x - 2] - a[x - 1];
}
else{
int k;
cin >> k;
cout << mp[n - k - 1] << endl;
}
}
return 0;
}
/*
*/
コードを見る問題L. 張飛の針を通す - 細くても厚い
n - 1 を出力するだけ
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e9 + 10, mod = 1e9 +7;
//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<char, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
string s;
vector<PII> a,ans;
void solve()
{
cin >> n;
cout << n - 1 << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int Ke_scholar = 1;
//cin >> Ke_scholar ;
while(Ke_scholar--)
solve();
return 0;
}
コードを見る