競プロ参加日記007 AtCoder Beginner Contest 176(ABC176) 参加
ぬるからです。
https://atcoder.jp/contests/abc176
ABC176に参加しました・
・全体的に
D問題(怒)
9ペナ出してしまった。
ただ、A～Eの5完できたので満足です。
・A Takoyaki
Atcoderでよく見かける感じのA問題です。
余りをカウントすることを忘れないようにします。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
int N,X,T;
cin>>N>>X>>T;
cout<<((N/X)+(N%X!=0))*T<<endl;
}・B Multiple of 9
Nの制約が大きいのでlong longだと受け取れないです。
『整数 Nが 9の倍数であることと、Nを十進法で表したときの各桁の数のが 9の倍数であることは同値です。』
と書かれているので、これに従いましょう。Stringで受け取って各文字を数値に変換して足し合わせて、それが9で割れるかを見ればいいです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
string s;
cin>>s;
int sum=0;
for(int i=0;i<s.size();i++){
sum+=s[i]-'0';
}
if(sum%9==0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}多倍長を使えば、Nの最大も受け取れるので、inputが9で割れるかどうかというA問題相当の問題になります。
・C Step
前から条件を満たすためにはどれくらい高さを盛るかをみて行けばいいです。無駄に高くしても後ろが無駄に高くなって答えが大きくなるだけなので、ぎりぎりを狙うのがBESTです。(後ろから見ると、前の人が高くなる可能性があるため、ぎりぎりの高さが分からないです。前から見ましょう。)
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
signed main(){
int N;
cin>>N;
int mn=0;
int ans=0;
for(int i=0;i<N;i++){
int A;
cin>>A;
if(mn>A){
ans+=mn-A;
}
else{
mn=A;
}
}
cout<<ans<<endl;
}・D Wizard in Maze
単純にBFSを書くとTLEします。
ワープに関してですが24方向にばらけるため、歩きと同時に進めると再探索の個所が増えそうな感じがします。(ワープした場所が実は歩いて行ける場合、歩きの方がコストが低いので、低くなったコストで再度探索をしてしまう。)
なので、歩きを優先に探索すれば計算量はぐっと抑えられそうです。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define MAX 1000
signed main(){
int H,W;
cin>>H>>W;
int Ch,Cw,Dh,Dw;
cin>>Ch>>Cw>>Dh>>Dw;
int cnt[MAX+5][MAX+5]={{0}};
string S[MAX+5]={{0}};
for(int i=0;i<H;i++){
cin>>S[i+1];
S[i+1]="#"+S[i+1];
for(int j=1;j<=W;j++){
cnt[i+1][j]=LLONG_MAX;
}
}
set<int> s2;
queue<int> qx,qy,qx2,qy2,c2;
qx.push(Cw);
qy.push(Ch);
cnt[Ch][Cw]=0;
while(!qx.empty()){
set<int> s;
int nx=qx.front();
int ny=qy.front();
qx.pop();
qy.pop();
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
for(int i=0;i<4;i++){
int tx=dx[i]+nx;
int ty=dy[i]+ny;
if(tx>=1&&tx<=W&&ty>=1&&ty<=H&&cnt[ty][tx]>cnt[ny][nx]&&
S[ty][tx]=='.'){
cnt[ty][tx]=cnt[ny][nx];
int o=tx*10000+ty;
if(s.find(o)==s.end()){
qx.push(tx);
qy.push(ty);
s.insert(o);
}
}
}
int dx2[]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int dy2[]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
for(int i=0;i<24;i++){
int tx=dx2[i]+nx;
int ty=dy2[i]+ny;
if(tx>=1&&tx<=W&&ty>=1&&ty<=H&&cnt[ty][tx]>cnt[ny][nx]+1&&
S[ty][tx]=='.'){
cnt[ty][tx]=cnt[ny][nx]+1;
int o=tx*10000+ty;
if(s2.find(o)==s2.end()){
qx2.push(tx);
qy2.push(ty);
s2.insert(o);
}
}
}
if(qx.empty()){
while(!qx2.empty()) {
qx.push(qx2.front());
qx2.pop();
}
while(!qy2.empty()) {
qy.push(qy2.front());
qy2.pop();
}
s2.clear();
}
}
/*for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
cout<<cnt[i][j]<<",";
}
cout<<endl;
}*/
if(cnt[Dh][Dw]==LLONG_MAX) cout<<"-1"<<endl;
else cout<<cnt[Dh][Dw]<<endl;
}歩き終わるまで、ワープで到達した個所は探索しないようにしています。
公式解説を見て気づいたのですが、実装は少し違いますが01-BFSと呼ばれるアルゴリズムみたいです。
公式ではdequeを使うことによって、ワープで到達した個所の探索を後ろにずらしていました。
・E Bomber
嘘解法っぽい？
hだけ見て、一番多く壊せる場所をx座標にする → wを見て、一番壊せる場所をy座標にする(先に決めたx座標は除く)
これをh→wとw→hの2パターンやって、大きいほうを解としました。
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/
using namespace std;
#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007
#define MAX 400000
signed main(){
int H,W,M;
cin>>H>>W>>M;
int h[MAX],w[MAX];
for(int i=0;i<M;i++){
cin>>h[i]>>w[i];
}
int ans1=0;
int cn[MAX+1]={0};
for(int i=0;i<M;i++){
cn[h[i]]++;
}
int mi=-1,mn=-1;
for(int j=1;j<=H;j++){
if(mn<cn[j]){
mn=cn[j];
mi=j;
}
}
for(int i=1;i<=MAX;i++) cn[i]=0;
ans1=mn;
int mi2=mi;
mi=-1,mn=-1;
for(int i=0;i<M;i++){
if(mi2!=h[i]) cn[w[i]]++;
}
mi=-1,mn=-1;
for(int j=1;j<=W;j++){
if(mn<cn[j]){
mn=cn[j];
mi=j;
}
}
ans1+=mn;
for(int i=1;i<=MAX;i++) cn[i]=0;
int ans2=0;
for(int i=0;i<M;i++){
cn[w[i]]++;
}
mi=-1,mn=-1;
for(int j=1;j<=W;j++){
if(mn<cn[j]){
mn=cn[j];
mi=j;
}
}
for(int i=1;i<=MAX;i++) cn[i]=0;
ans2=mn;
mi2=mi;
mi=-1,mn=-1;
for(int i=0;i<M;i++){
if(mi2!=w[i]) cn[h[i]]++;
}
mi=-1,mn=-1;
for(int j=1;j<=H;j++){
if(mn<cn[j]){
mn=cn[j];
mi=j;
}
}
ans2+=mn;
cout<<max(ans1,ans2)<<endl;
}反例が思い浮かばなかったので出しましたが、通ってよかったです。
テストケース100近くを通ったので嘘ではないと思うのですが、頭の中で何故通るかがいまいち理解できていません。(良い子はマネしちゃだめだよ)
・F Brave CHAIN
Dに時間をかけたせいで考察の時間がなかった。
雑考察で出した解法は大半がWAで撃沈。
どうも赤色問題だったらしいですね...。見た目簡単そうなのに...。
・最後に
https://qiita.com/e869120/items/f1c6f98364d1443148b3
https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7%B4%9A%E8%80%85%E3%81%8C%E8%A7%A3%E3%81%8F%E3%81%B9%E3%81%8D%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-100-%E5%95%8F
最近は、qiitaのレッドコーダーが教えるシリーズの問題を解いたりと、少し競プロの練習を始めました。
一先ずは、青になるまでは頑張りたい...。
この記事が気に入ったらサポートをしてみませんか？