2020 11/22 13:14 C問題を解説ACしました。
はじめに
AtCoder Regular Contest 108 - AtCoder
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
3週間ぶりのARCでしょうか？
結果はA,Bの2完でした。ただ、B問題はテストケースの穴をついて解いたため、実質Aの1完と良くなかったです…。
A – Sum and Product
A - Sum and Product
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
1≤S,P≤10^12
と制約が大きいので、単純にやると間に合わなさそうです。
対称式 - Wikipedia
ja.wikipedia.org
ここで、対称式という考え方が重要になります。
この問題もNとMを入れ替えても式は変わりません。つまり、対称性のある式です。そのため、
N=aのとき、 a+M=S,M*a=P M=S-a,M=P/a が成り立たないなら、 N=S-aや、P/aも成り立たない
が、いえます。
aを調べるついでにP/aも調べられるため、sqrt(P)まで調べれば全範囲を調べたことになります。計算量もグッと減り間に合うようになります。
#include<bits/stdc++.h>
using namespace std;
int main(){
long long S,P;
cin>>S>>P;
long long ans=1;
for(long long i=1;i<sqrt(P)+2;i++){
if(P%i!=0) continue;
long long s=S-i;
long long k=P/i;
if(s==k){
cout<<"Yes"<<endl;
return 0;
}
}
cout<<"No"<<endl;
}
B – Abbreviate Fox
B - Abbreviate Fox
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
コンテスト解が明らかに嘘解法です。気を付けて見て下さい。
コンテスト解(嘘あり)
foxを線形探索して消した場合、最悪計算量がO(N^2)とTLEします。
foxを消して繋げた際に、foxができる条件として
- fofoxxのようにfofofo…fox…xxxのパターン
- ffoxoxのようにfff…fox…oxoxoxのパターン
の2つが考えられます。
こういった文字列がある場合は一気に消すことで効率化を目指しました…が、どこかで実装がバグっていたそうで13つのテストケースでWAしました。
かなり焦っていて、O(N^2)の愚直解でも通るのでは？と思い提出したら1つのテストケースがTLEでした。
ぬるから
TLEするテストケースが効率化のコードではACになるのでは？
ニコイチさせました。
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
cin>>N;
string s;
cin>>s;
string ts=s;
//fofoxx
//ffoxox
while(1){
//cout<<s<<endl;
int ans=0;
int c=0;
int c2=0;
int del[(int)s.size()];
for(int i=0;i<(int)s.size();i++) del[i]=0;
for(int i=0;i<(int)s.size();i++){
if(i!=(int)s.size()-1&&s[i]=='o'&&s[i+1]=='x'){
c2++;
i++;
if(i==(int)s.size()-1){
i++;
ans+=min(c2,c)*3;
for(int j=i-min(c2,c)*3;j<i;j++){
del[j]=1;
}
i--;
}
}
else{
if(c2>0){
ans+=min(c2,c)*3;
for(int j=i-min(c2,c)*3;j<i;j++){
del[j]=1;
}
c2=0;
c=0;
}
if(s[i]=='f'){
c++;
}
else{
c=0;
c2=0;
}
}
}
for(int j=(int)s.size()-min(c2,c)*3;j<(int)s.size();j++){
del[j]=1;
}
////cout<<ans<<endl;
c=0;
c2=0;\
for(int i=0;i<(int)s.size();i++){
if(s[i]=='x'){
c2++;
i++;
if(i==(int)s.size()-1){
i++;
ans+=min(c2,c)*3;
for(int j=i-min(c2,c)*3;j<i;j++){
del[j]=1;
}
i--;
}
}
else{
if(c2>0){
ans+=min(c2,c)*3;
for(int j=i-min(c2,c)*3;j<i;j++){
del[j]=1;
}
c2=0;
c=0;
}
if(i!=(int)s.size()-1&&s[i]=='f'&&s[i+1]=='o'){
c++;
}
else{
c=0;
c2=0;
}
}
}
for(int j=(int)s.size()-min(c2,c)*3;j<(int)s.size();j++){
del[j]=1;
}
string ns="";
for(int i=0;i<(int)s.size();i++){
//cout<<del[i]<<" ";
if(del[i]==0){
ns+=s[i];
}
}
//cout<<endl;
if(ns==s){
string nns="";
for(int i=0;i<(int)s.size();i++){
if(i+2<(int)s.size()&&s[i]=='f'&&s[i+1]=='o'&&s[i+2]=='x'){
i+=2;
}
else nns+=s[i];
}
//cout<<nns<<endl;
if(nns==s) break;
else s=nns;
}
else s=ns;
}
int a1=s.size();
s=ts;
int c=0;
while(1){
string nns="";
for(int i=0;i<(int)s.size();i++){
if(i+2<(int)s.size()&&s[i]=='f'&&s[i+1]=='o'&&s[i+2]=='x'){
i+=2;
}
else nns+=s[i];
}
//cout<<nns<<endl;
if(nns==s) break;
else s=nns;
c++;
if(c>=1000){
cout<<a1<<endl;
return 0;
}
}
cout<<(int)s.size()<<endl;
}
int a1=s.size();
より上が効率解で下が愚直解です。
愚直解のループが閾値より大きくなれば、効率解を出力しようとしています。
コンテスト中はどんな手を使ってでもAC取る主義の私でもこれは反省ものです…。
エデュ解
Editorial - AtCoder Regular Contest 108
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
頭いい！！！！！
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;
string S;
vector<char> v;
cin>>N>>S;
for(int i=0;i<S.size();i++){
v.push_back(S[i]);
if(v.size()>=3){
if(v[v.size()-3]=='f'&&v[v.size()-2]=='o'&&v[v.size()-1]=='x'){
v.pop_back();
v.pop_back();
v.pop_back();
}
}
}
cout<<v.size()<<endl;
}
stackに放り込んで末尾3つがfoxか確認、foxなら取り除く。といった感じです。
“末尾3つがfoxか確認”がC++のstackではやりにくいので、vectorで代用しました。
C – Keep Graph Connected
C - Keep Graph Connected
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
atcoder.jp
入力例が怪しい問題。
よい書き込み方が存在しないならば No を出力せよ。
という問題なのに、Noの入力例がないです。
実はこの問題、どんなグラフが与えられても” よい書き込み方“が存在します。
具体的には、グラフを木にした場合、辺のラベルに関わらず必ず1通り以上存在するようになります。
- 木の適当な頂点を根にする。
- 根に適当な値を書き込む。
- 書き込んだ頂点の子の頂点に、以下のルールで書き込む
親に書き込んだ値が辺の値と同じ → 辺の値と違う値を書き込む
親に書き込んだ値が辺の値と違う → 辺の値を書き込む
上記3を葉になるまで繰り返すと、それが良い書き込みになります。
葉で帳尻が合わせられるので必ず良い書き込みになる感じです(賢い！)
木の作成はUnionFindで頂点の集合を管理しながら、違うグラフを繋ぐ辺を選んでいけばOKです。
#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>> vp[N+1];
dsu d(N+1);
for(int i=0;i<M;i++){
int u,v,c;
cin>>u>>v>>c;
if(!d.same(u,v)){
d.merge(v,u);
vp[v].push_back(make_pair(u,c));
vp[u].push_back(make_pair(v,c));
}
}
int ans[N+1];
for(int i=1;i<=N;i++) ans[i]=0;
ans[1]=rand()%N+1;
queue<int> q;
for(int i=0;i<vp[1].size();i++){
q.push(vp[1][i].first);
}
while(!q.empty()){
int n=q.front();
q.pop();
int pc=0;
bool f=false;
for(int i=0;i<vp[n].size();i++){
int nx=vp[n][i].first;
int nc=vp[n][i].second;
if(ans[nx]!=0){
pc=nc;
if(ans[nx]==nc) f=true;
break;
}
}
if(f){
if(pc!=N) ans[n]=pc+1;
else ans[n]=pc-1;
}
else{
ans[n]=pc;
}
for(int i=0;i<vp[n].size();i++){
int nx=vp[n][i].first;
if(ans[nx]==0){
q.push(nx);
}
}
}
for(int i=1;i<=N;i++){
cout<<ans[i]<<endl;
}
}
おわりに
ARC、AGCに苦手意識があります…。
ABC埋めを終わらしたらARC埋めに移りたいです。
コメント