読者です 読者をやめる 読者になる 読者になる

beet's soil

競プロのことなど

AtCoder Beginner Contest 051

今週はABC Onlyだったので出た。

【A - Haiku】

6,14文字目をスペースにするだけ。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  string s;
  cin>>s;
  s[5]=s[13]=' ';
  cout<<s<<endl;
  return 0;
}
【B - Sum of Three Integers】

FA狙ったけどサンプル合わなくて終了。
antaさん45秒ってヤバすぎる。
O(N^3)だと回らないのでO(N^2)に落とす。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll k,s,ans=0;
  cin>>k>>s;
  for(int x=0;x<=k;x++)
    for(int y=0;y<=k;y++)
      if(x+y<=s&&x+y+k>=s) ans++;
  cout<<ans<<endl;
  return 0;
}
【C - Back and Forth】

ぐるぐるっとまわる。
最短経路の条件を見逃してたけど通った。
添え字ミスで1WA(

---->-- ...

^.......v...

.. ->-- ->
..^....v..
<- --<- ..

...^.......v
...|--<----|

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  int sx,sy,tx,ty;
  cin>>sx>>sy>>tx>>ty;
  for(int i=sy;i<ty;i++) cout<<"U";
  for(int i=sx;i<tx;i++) cout<<"R";
  for(int i=sy;i<ty;i++) cout<<"D";
  for(int i=sx;i<=tx;i++) cout<<"L";
  for(int i=sy;i<=ty;i++) cout<<"U";
  for(int i=sx;i<=tx;i++) cout<<"R";
  cout<<"DR";
  for(int i=sy;i<=ty;i++) cout<<"D";
  for(int i=sx;i<=tx;i++) cout<<"L";
  cout<<"U"<<endl;
  return 0;
}
【D - Candidates of No Shortest Paths】

ワーシャルフロイドの経路復元。
一回やったことあるのに忘れててアレ。
また添え字ミスで1WA(

参考にしたサイト
ワーシャル-フロイド法の経路復元 - ゼオスTTのブログ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  int n,m;
  cin>>n>>m;
  map<P,int> mp;
  int e[n][n],g[n][n];
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(i==j) g[i][j]=e[i][j]=0;
      else g[i][j]=e[i][j]=1<<25;
  for(int i=0;i<m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    a--;b--;
    mp[P(a,b)]=mp[P(b,a)]=i;
    g[a][b]=g[b][a]=e[a][b]=e[b][a]=c;
  }
  for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
	e[i][j]=min(e[i][k]+e[k][j],e[i][j]);
  bool used[m];
  memset(used,0,sizeof(used));
  for(int s=0;s<n;s++){
    for(int t=0;t<n;t++){
      bool vi[n];
      memset(vi,0,sizeof(vi));
      queue<int> q;
      q.push(s);
      while(!q.empty()){
	int cur=q.front();q.pop();
	if(vi[cur]) continue;
	vi[cur]=1;
	for(int i=0;i<n;i++){
	  if(i!=cur&&g[cur][i]+e[i][t]==e[cur][t]){
	    q.push(i);
	    used[mp[P(i,cur)]]=1;
	  }
	}
      }
    }
  }
  int ans=m;
  for(int i=0;i<m;i++) ans-=used[i];
  cout<<ans<<endl;
  return 0;
}
【全体】

4完77位 (unrated)
実質混合みたいな感じだったし悪くはないのかな。
全完セットだとWAペナが大きいということがわかった。