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++のほうがさらっと書けそう。

しばらくコンテストないっぽいなー。