2020/11/16 19:03 E問題をyoutubeの解説動画見て通したので、追記しました。
はじめに
AtCoder Beginner Contest 183 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
A,B,C,D,Fの5完でした。
ABCのF問がコンテスト中に解けたの初ですね…。結構解いてる方が多かったので、難易度低め問題と思いますが良かったです。
B問が数学基礎問題だったのですが、考察に一番時間がかかりました。(数学の勉強をやり直したい＞ ＜)
A – ReLU
A - ReLU
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
数式をif文に直す問題です。
そのまま、実装しましょう。
#include<bits/stdc++.h>
using namespace std;
int main(){
int x;
cin>>x;
if(x<0) cout<<"0"<<endl;
else cout<<x<<endl;
}
B – Billiards
B - Billiards
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
難しかったです。
x座標の移動が、abs(sx-gx)移動します。
ここでy座標の移動は、反射する前はsy、反射後はgyです。
反射までに移動する距離をaとしたとき、以下の式で表せられます。
sy:gy=a:abs(sx-gx)-a a*gy=sy*abs(sx-gx)-sy*a a*(gy+sy)=sy*abs(sx-gx) a=sy*abs(sx-gx)/(gy+sy)
ここで計算した値はsxからの移動距離なため、gxとsxの位置関係から、計算した値を足すor引くした値が答えになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
double sx,sy,gx,gy;
cin>>sx>>sy>>gx>>gy;
double d=sy*abs(sx-gx)/(gy+sy);
double ans=sx;
if(sx<gx) ans+=d;
else ans-=d;
printf("%.12f\n",ans);
}
C – Travel
C - Travel
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
N=8しかないので、全探索しても8!=40320通りと余裕があります。
C++ならnext_permutationを使えば、順列が全通り生成できます。これを使って全探索しましょう。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,K;
cin>>N>>K;
int T[N+1][N+1];
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
cin>>T[i][j];
}
}
int ans=0;
int perm[]={1,2,3,4,5,6,7,8};
do{
if(perm[0]==1){
int c=0;
int idx=1;
int n=perm[0];
do{
c+=T[n][perm[idx%N]];
n=perm[idx%N];
idx++;
}while(n!=perm[0]);
//cout<<c<<endl;
if(c==K) ans++;
}
}while(next_permutation(perm,perm+N));
cout<<ans<<endl;
}
D – Water Heater
D - Water Heater
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
ある範囲の合計値を求め。それらがWを超えているかを求める問題です。
範囲の合計値が出てきたら、とりあえず”いもす”で殴ればOKかと思います。
いもすは、それぞれの範囲の
範囲の初めに+値、範囲の終わり+1に-値
をしたものに累積和を取る方法です。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long N,W;
cin>>N>>W;
long long dat[200001]={0};
for(int i=0;i<N;i++){
int S,T;
long long P;
cin>>S>>T>>P;
dat[S]+=P;
dat[T]-=P;
}
for(int i=0;i<200001;i++){
if(i!=0) dat[i]+=dat[i-1];
if(dat[i]>W){
cout<<"No"<<endl;
return 0;
}
}
cout<<"Yes"<<endl;
}
E – Queen on Grid
E - Queen on Grid
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
解説放送を見ました。
DPで解けそうですが、何マスも進めるという操作が厄介です。
結論としては、累積和を更新しながらDPをします。
貰うDPを横移動だけ考えた場合
(i,j)=(i,j-1)+(i,j-2)+….+(i,0)
と言えます。この右側の式が累積和になっており、dpテーブルを更新するついでに更新します。
縦移動、斜め移動も同じように考えればOKです。
累積和のテーブルに関して、横、縦、斜めでそれぞれ違う配列で持って更新していきましょう。
(同じ配列で更新すると、累積の結果が四角形の区間の和とかになってしまいます。今回ほしい累積は一直線の和です。）
#include<bits/stdc++.h>
using namespace std;
int main(){
int H,W;
long long mod=1000000007;
cin>>H>>W;
string S[H];
for(int i=0;i<H;i++){
cin>>S[i];
}
long long dp[H][W];
long long y[H][W];
long long xy[H][W];
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
dp[i][j]=0;
y[i][j]=0;
xy[i][j]=0;
}
}
xy[0][0]=1;
y[0][0]=1;
dp[0][0]=1;
for(int i=0;i<H;i++){
long long x[W];
for(int j=0;j<W;j++) x[j]=0;
if(i==0) x[0]=1;
for(int j=0;j<W;j++){
if(i==0&&j==0) continue;
if(S[i][j]=='#') continue;
if(i!=0) dp[i][j]+=y[i-1][j];
if(j!=0) dp[i][j]+=x[j-1];
if(i!=0&&j!=0) dp[i][j]+=xy[i-1][j-1];
dp[i][j]%=mod;
if(j!=0) x[j]+=x[j-1]+dp[i][j];
else x[j]=dp[i][j];
if(i!=0) y[i][j]+=y[i-1][j]+dp[i][j];
else y[i][j]=dp[i][j];
if(i!=0&&j!=0) xy[i][j]+=xy[i-1][j-1]+dp[i][j];
else xy[i][j]=dp[i][j];
x[j]%=mod;
y[i][j]%=mod;
xy[i][j]%=mod;
//cout<<dp[i][j]<<" ";
}
//cout<<endl;
}
cout<<dp[H-1][W-1]%mod<<endl;
}
F – Confluence
F - Confluence
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
問題文を見た感じ、UnionFindな感じがします。
ただ単純にUnionFindで解くと、”生徒 x と合流している生徒(生徒 x を含む)のうち、クラス y に属している生徒の数”の処理がやっかいです。
今回は、UnionFindの親に子が属するクラスの個数を保持するmultimapを追加し、その値を返すようにしました。
#include<bits/stdc++.h>
using namespace std;
map<int,int> css[200001];
struct dsu {
public:
dsu() : _n(0) {}
dsu(int n) : _n(n), parent_or_size(n, -1) {}
int merge(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
auto it=css[y].begin();
while(it!=css[y].end()){
css[x][it->first]+=it->second;
it++;
}
parent_or_size[y] = x;
return x;
}
bool same(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int>& v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
int main(){
int N,Q;
cin>>N>>Q;
for(int i=1;i<=N;i++){
int C;
cin>>C;
css[i][C]++;
}
dsu d(N+1);
for(int i=0;i<Q;i++){
int qu,x,y;
cin>>qu>>x>>y;
if(qu==1){
d.merge(x,y);
}
else{
int l=d.leader(x);
cout<<css[l][y]<<endl;
}
}
}
UnionFind(dsu)のコードはatcoderのライブラリのものですが、merge時にcss変数(子の属するクラスの個数)にもmerge処理を行うよう追加しています。
おわりに
パフォーマンスが1579でレートが1425(+20)になりました。
一先ず、Highest更新で安心です。
毎日やっているABC潰しですが、もう少し加速して埋めていきE,F問題を安定して解けるようになりたいですね。
コメント