ABC163CD
日曜に開催されたものですが、サーバー負荷でアクセスできなかったものです。最新のものはD問題まで解いていこうと思います。
がんばれAtCoder!
まずはC問題。
――――――――――――――――――――――――
問題文
N人の社員からなる会社があり、各社員には1,...,Nの社員番号が割り当てられています。
社員番号1の社員以外の全ての社員には、自分より社員番号が小さい直属の上司がちょうど1人います。
XさんがYさんの直属の上司であるとき、YさんはXさんの直属の部下であるといいます。
社員番号iの社員の直属の上司の社員番号がAiであることが与えられます。各社員について直属の部下が何人いるか求めてください。
制約
• 2≤N≤2×10^5
• 1≤Ai<i
入力
入力は以下の形式で標準入力から与えられる。
N
A2 ... AN
出力
社員番号1,2,,N のそれぞれの社員について、直属の部下が何人いるか、改行区切りで出力せよ。
――――――――――――――――――――――――
考え方
くしくも昨日解いたバケツソートでいけそう。
1. 社員番号=配列の添え字番号となるような配列vecを作成する。
2. Ai=自分の上司の番号となり作成した配列vecの各要素は上司の部下の数と対応するから、vec[Ai]にカウントしていく。
3.それぞれのvec[i]を出力。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vec(n+1);
for(int i=0; i<n-1; i++){
int a;
cin >> a;
vec[a]++;
}
for(int i=1; i<=n; i++){
cout << vec[i] << endl;
}
}
続いてD問題。
――――――――――――――――――――――――
問題文
10^100,10^100+1, ..., 10^100+NのN+1個の数があります。
この中からK個以上の数を選ぶとき、その和としてあり得るものの個数をmod(10^9+7)で求めてください。
制約
• 1≤N≤2×10^5
• 1≤K≤N+1
• 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
和としてあり得るものの個数をmod(10^9+7)で出力せよ。
――――――――――――――――――――――――
考え方
問題を解くうえで、以下の項目を押さえておく。
・選んだ個数が違えば、値が同じになることはない。
→要素が10^100と大きいので、0~Nをいくら足そうが、10^100には届かない。
・K個の数を選ぶとき、10^100部分を除くと、その最小値は0~K-1の総和、最大値はN-K+1~Nの総和となる。
・K個の数を選ぶとき、その組み合わせの数は、最小値~最大値の個数存在する。(細かい証明は置いといてどうもそうなりそう)
そのため、解く手順としては、
1. K個選んだ時の最小値0~K-1、最大値N-K+1の総和をそれぞれ求める。(手計算)
2. 最大値 - 最大値+1でK個選んだ時の組み合わせ数を求める。(手計算)
3. 組み合わせ数をK~N個選んだときの総和を求める。その際、適宜mod(10^9+7)をとる。(手計算でもできるけど計算が煩雑だったので普通にforループで)
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int main() {
long long n,k;
cin >> n >> k;
long long ans = 0;
for(long long i=k; i<=n+1; i++){
ans += (1 + i + n*i -i*i) % mod;
}
cout << ans%mod << endl;
}
ほとんど手計算で解ける問題…。
modをとるときに、データ型をそろえないと違う数値が返ってきてしまうようだ。
これから過去問を解くときはC#で、コンテストに参加するときはC++で行こうと思う。まだC#が慣れないので書くのに時間がかかってしまうのと、数的な処理については、C++のほうがさらっと書けそう。
しばらくコンテストないっぽいなー。