2021/2/7 5:02 F問題を解説ACしたので追記しました。
はじめに
AtCoder Beginner Contest 191 – AtCoder
A～Eの5完でした。
D問題で爆死した方が多かったようで、324位とかなりの好成績を残せました。
パフォーマンスも2032と黄パフォが出ました。かなり青に近づけましたね！
A – Vanishing Pitch
A – Vanishing Pitch (atcoder.jp)
この問題、速さ距離時間のどれで比較するかで以下の3つの条件式が書けると思います。
速さ：D/T<=V<=D/S 時間：T<=D/V<=S 距離：T*V<=D<=S*V
割り算をするのは、誤差が怖いので距離の式を選択しましょう。
または、速さ時間の式を変形し割り算をなくします。(結果的には距離の式になるかと思います。)
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int V,T,S,D;
cin>>V>>T>>S>>D;
if(V*T<=D&&V*S>=D) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
B – Remove It
Aより簡単かもしれません。問題文通り、A!=XでないAを出力していくだけです。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,X;
cin>>N>>X;
for(int i=0;i<N;i++){
int A;
cin>>A;
if(A!=X) cout<<A<<" ";
}
cout<<endl;
}
このコード、最後に無駄な空白ができるのですがAtcoderでは許容されるようです。
本番では怖くて、フラグにより最後に空白ができないコードを書いてましたが…時間の無駄だったようです:(
C – Digital Graffiti
C – Digital Graffiti (atcoder.jp)
ABC191の問題児その1。
clarがたくさん飛んだ問題を久々に見ました。
多角形の定義が分かりにくいかつ、入力例を見てもその分かりにくさが解消されないのが難点です。
分かりにくい点とは以下のような場合です。
3 3 #.. ##. ### の場合、 斜めを辺としてみなして3角形とするか 斜めを各頂点の集合とみて8角形とするか
私はC問題であることから、前者の場合明らかに難易度が高すぎる(Eくらいありそう)と考え、後者に絞って考えました。
結果として、後者が正解だったので良かったです。改めて問題文を見ると、マス目を塗るとかどうとかって書いてあるので後者であることは自明です。
後者で考えた場合の頂点ですが、以下の2通りが考えられます。
あるマスを"#"と考えて 凸の頂点：あるマスの左上を調べる場合、あるマスの左と上のマスが"."である。 凹の頂点：あるマスの左上を調べる場合、あるマスの左と上のマスが"#"であり、あるマスの左上のマスが"."である。
これを4頂点の各8通り調べて足し合わせました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int H,W;
cin>>H>>W;
string s[H+2];
for(int i=1;i<=H;i++){
cin>>s[i];
s[i]="."+s[i]+".";
}
s[0]="";
s[H+1]="";
for(int i=0;i<W+2;i++){
s[0]+=".";
s[H+1]+=".";
}
int ans=0;
for(int i=1;i<=H;i++){
for(int j=1;j<=W;j++){
if(s[i][j]=='#'){
bool f1=s[i+1][j]=='.'&&s[i][j-1]=='.';
bool f2=s[i+1][j]=='.'&&s[i][j+1]=='.';
bool f3=s[i-1][j]=='.'&&s[i][j-1]=='.';
bool f4=s[i-1][j]=='.'&&s[i][j+1]=='.';
bool f5=s[i+1][j]=='#'&&s[i][j-1]=='#'&&s[i+1][j-1]=='.';
bool f6=s[i+1][j]=='#'&&s[i][j+1]=='#'&&s[i+1][j+1]=='.';
bool f7=s[i-1][j]=='#'&&s[i][j-1]=='#'&&s[i-1][j-1]=='.';
bool f8=s[i-1][j]=='#'&&s[i][j+1]=='#'&&s[i-1][j+1]=='.';
ans+=f1+f2+f3+f4+f5+f6+f7+f8;
}
}
}
cout<<ans<<endl;
}
D – Circle Lattice Points
D – Circle Lattice Points (atcoder.jp)
ABC191の問題児その2。
424人しか解けていない最強のD問題です。
私はE解いてから戻ってきて解きました。
まず考えたことは、|X|,|Y|<=10^5であるため、X方向かY方向になぞれそうと考えました。
次にY方向になぞった場合、格子点であるX座標はある範囲に固まって存在することになります(または、そんな範囲がそもそもない)。
そのため、この範囲を高速で求めれば問題ないと考えました。
ある座標yにある格子点の範囲を考えた場合、 格子点がある=0、格子点がない=1として、 ... 0 0 0 0 1 1 1 1 0 0 0 0 0 ... ← -x方向 x方向 → のように0の連続列の間に1の連続列ができるはず。 また、1の連続列の間には円の頂点座標Xがあるはずなので、そこで二分割することで ... 0 0 0 0 1 1 ... 1 ... 1 1 0 0 0 0 ... と二つの列ができる。この二つの列はソート済みであるため、二分探索で境界を求めることができる。
と、頂点X座標から左と右に分けたときに、題意を満たす格子点とそうでない格子点が綺麗に分かれるので二分探索で範囲の端が分かる→範囲がlog(|X|くらい)で分かる！と考えました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
//https://yttm-work.jp/collision/collision_0003.html
// 円データ
typedef struct
{
long double m_PosX; // X座標
long double m_PosY; // Y座標
long double m_Radius; // 半径
} Circle;
// 点データ
typedef struct
{
long double m_PosX; // X座標
long double m_PosY; // Y座標
} Point;
bool OnCollisionPointAndCircle(Point point, Circle circle)
{
long double a = point.m_PosX - circle.m_PosX;
long double b = point.m_PosY - circle.m_PosY;
long double c = a * a + b * b;
if (c <= circle.m_Radius*circle.m_Radius+0.000000001)
{
return true;
}
return false;
}
int main(){
long double X,Y,R;
cin>>X>>Y>>R;
Circle ci;
ci.m_PosX=X;
ci.m_PosY=Y;
ci.m_Radius=R;
long double Dd=Y-R;
long double Ud=Y+R;
int d=ceil(Dd);
int u=Ud;
//cout<<u<<","<<d<<endl;
long long ans=0;
for(int i=d;i<=u;i++){
int l=-1000000;
Point pot;
pot.m_PosY=i;
pot.m_PosX=(int)X;
int s=0;
if(OnCollisionPointAndCircle(pot,ci)) s=X;
else{
pot.m_PosX=ceil(X);
if(OnCollisionPointAndCircle(pot,ci)) s=ceil(X);
else continue;
}
int r=s;
int il=s;
while(1){
int m=(l+r)/2;
Point po;
po.m_PosY=i;
po.m_PosX=m;
bool f=OnCollisionPointAndCircle(po,ci);
if(f){
il=min(m,il);
if(r==m) break;
r=m;
}
else{
if(l==m) break;
l=m;
}
}
pot.m_PosX=ceil(X);
if(OnCollisionPointAndCircle(pot,ci)) s=ceil(X);
else{
pot.m_PosX=(int)X;
if(OnCollisionPointAndCircle(pot,ci)) s=(int)X;
else continue;
}
l=s;
r=1000000;
int ir=s;
while(1){
int m=(l+r)/2;
Point po;
po.m_PosY=i;
po.m_PosX=m;
bool f=OnCollisionPointAndCircle(po,ci);
//cout<<i<<","<<m<<"("<<l<<","<<r<<")--"<<f<<endl;
if(f){
ir=max(m,ir);
if(l==m) break;
l=m;
}
else{
if(r==m) break;
r=m;
}
}
//cout<<i<<","<<il<<","<<ir<<endl;
ans+=ir-il+1;
}
cout<<ans<<endl;
}
円と点の衝突判定はこちらのサイトからお借りしました。
少し改変していて、
long double c = a * a + b * b;
if (c <= circle.m_Radius*circle.m_Radius+0.000000001)
{
return true;
}
cをsqrtにすると誤差が大きくなるので、半径の方を二倍しています。
あと、半径の方に10^-9を足しこんでいます。所謂EPSとかって呼ばれるやつですが、今回小数4桁までで二乗しているので、9桁以降は誤差と判断し10^-9を足しています。
あと、精度を少しでも高くするためfloat→long doubleにしていますが…10000倍して整数計算したほうが良かったかもしれません。
E – Come Back Quickly
E – Come Back Quickly (atcoder.jp)
ダイクストラで解けそうです。
Nの最大が2000程度なので、各頂点の戻ってくる最短経路を求めても十分間に合いそうです。
戻ってくる経路を計算したいので、スタートはある頂点から1回で行ける頂点(初期コストとして、行くための時間を追加する)、ゴールはある頂点としました。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int main(){
int N,M;
cin>>N>>M;
vector<pair<int,int>> v2[N+1];
for(int i=0;i<M;i++){
int A,B,C;
cin>>A>>B>>C;
v2[A].push_back(make_pair(C,B));
}
vector<pair<int,int>> v[N+1];
for(int i=1;i<=N;i++){
sort(v2[i].begin(),v2[i].end());
int f[N+1];
for(int j=0;j<N+1;j++) f[j]=false;
for(int j=0;j<v2[i].size();j++){
int c=v2[i][j].first;
int t=v2[i][j].second;
if(f[t]==false){
v[i].push_back(make_pair(c,t));
f[t]=true;
}
}
}
for(int i=1;i<=N;i++){
int ans[N+1];
for(int j=0;j<N+1;j++) ans[j]=-1;
priority_queue<pair<int,int>> pq;
for(int j=0;j<v[i].size();j++){
int c=v[i][j].first;
int t=v[i][j].second;
ans[t]=c;
pq.push(make_pair(-c,t));
}
while(!pq.empty()){
int n=pq.top().second;
pq.pop();
for(int j=0;j<v[n].size();j++){
int c=v[n][j].first;
int t=v[n][j].second;
if(ans[t]==-1||ans[t]>ans[n]+c){
ans[t]=ans[n]+c;
pq.push(make_pair(-(ans[n]+c),t));
}
}
}
cout<<ans[i]<<endl;
}
}
E問題なので多重辺は取り除く(最小の時間でない辺は必要ないため、削除する)ことで高速化を図りましたが、それがなくても482msでACしました。(多重辺取り除きを入れても335msなので、あんまり高速化できていない…)
もっというと優先度付きキューじゃないただのキューでも1292msでAC取れました。
この問題の難しさが分からない？？？単純に全頂点のBFSするだけで解けてしまう。正直C,Dより明らかに簡単です。
F – GCD or MIN
ゆっくり考えていきます。
まず、作れる数を絞っていきます。
gcdとminなので
できる操作がgcdとminの2つです。
min(A,B)とした場合、A,Bの小さいほうになります。
gcd(A,B)とした場合、A,Bの小さいほう以下になります。
つまり、どっちの操作にせよ小さいほう以下になります。
つまり、Aminより大きい数にできない(Aminを使うと、Amin以下になるため)です。よって、作れる数はAmin以下となります。
gcdに注目してもう少し絞る
gcd(A,B,C,D…)がAminより小さくなった場合、あとはmin操作を行うことによりgcdの値が残せます。
逆にgcd(A,B,C,D…)がAminより大きくなった場合、min操作を行ってもAminに防がれてgcdの値が残せません。
なので、任意個の値をgcdした時にAminより大きいか小さいかで残せるかどうかが変わります。
ここから、複数の値でgcdを作ってその値がAminより小さい値の種類+1(Aminの分)が答えになります。
よってこの問題は、『Aから任意個選んでgcdする場合、Aminより小さい値は幾つ作れるか？』と言い換えられます。
ある値がgcdで作れるか？
あるAiを使ってgcdを作る場合、考えられる値はAiの約数になります。
この時、Aiの約数が本当に作れるか…が問題です。
例えばA={9,18,27}の場合、3が約数にありますが実際3は作れません。
解決策として、あるAiの約数nを考えた場合、nで割り切れるA同士でgcdを取ってそれがnになるかを見ていけば良いです。
gcdは素因数分解したときに、素因数の共通部分を残すような計算です。そのため、nで割り切れるA同士でgcdを取っていくと、nを含む共通部分が残っていきこの時nだけが残れば、n倍数同士のgcdでnが作れることになります。
逆に、n以外の共通部分が残ってしまうと、どうgcdをとっても作れません。(n倍数以外とgcdを取ると、nが消えてしまう。また、共通部分が残っていくのでgcdを取る個数を少なくしても、共通部分が消えることはない。)
まとめ
上記纏めると以下になります。
- Aの各値の約数(Amin以下)を列挙。
- 列挙した約数をnとして、nの倍数であるAの各値同士でgcdを取る。
gcdを取った結果、nになれば答えの列挙に追加する。 - 答えの列挙のサイズ+1(Aminの分)が答え。
これをコードに落としていきます。
#include<bits/stdc++.h>
//#include<atcoder/all>
using namespace std;
//using namespace atcoder;
int gcd(int a,int b){
if(a<b) return gcd(b,a);
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
int N;
cin>>N;
int A[N];
for(int i=0;i<N;i++){
cin>>A[i];
}
sort(A,A+N);
set<int> ans;
ans.insert(A[0]);
set<int> yaku;
for(int i=0;i<N;i++){
for(int j=1;j<sqrt(A[i])+1;j++){
if(A[i]%j==0){
if(j<A[0]) yaku.insert(j);
if(A[i]/j<A[0]) yaku.insert(A[i]/j);
}
}
}
auto it=yaku.begin();
while(it!=yaku.end()){
int n=*it;
int gc=-1;
for(int j=0;j<N;j++){
//cout<<n<<","<<gc<<","<<A[j]<<endl;
if(A[j]%n==0){
if(gc==-1) gc=A[j];
else gc=gcd(A[j],gc);
}
}
if(gc==n) {
//cout<<"!!!"<<n<<endl;
ans.insert(n);
}
it++;
}
cout<<ans.size()<<endl;
}
最小公倍数について理解しないといけない問題ですね。F問題らしくて個人的には好きです。(気づけば簡単だけど、中々気づかない問題)
おわりに(雑談)
最近QtCreatorの調子が悪い(正確にはセグメンテーション違反等で落ちたときにgdbが落ちた場所を示してくれない)ので、VSCodeを入れて使っています。
VSCodeって、ただのテキストエディタかと思っていたのですが、コンパイル実行もできちゃうんですね…。大学のときはVSでコードを書いてたので懐かしい気分になれます。
QtCreator歴が長いこともあり、慣れない部分も多いですが、ちょっとずつ使いこなしていきたいです。
コメント