AtCoder Beginner Contest 051
はい。
https://atcoder.jp/contests/abc051
A - Haiku
C++14
#include<bits/stdc++.h> using namespace std; int main(){ char a[1]; for (int i=0;i<19;i++) { scanf("%c",&a); printf("%c",a[0]==','?' ':a[0]); } printf("\n"); return 0; }
文字列の扱い方よくわからぬ。
B - Sum of Three Integers
C++14
#include<bits/stdc++.h> using namespace std; int main(){ int k,s,ans=0; scanf("%d %d",&k,&s); for (int i=0;i<=k;i++) { for (int j=0;j<=k;j++) { if (s-i-j>=0 && s-i-j<=k) ans++; } } printf("%d\n",ans); return 0; }
ループは3重ではなく2重で。3つ目の数は固定で定まるのでループ回す必要ないです、多分。
C - Back and Forth
C++14
#include<bits/stdc++.h> using namespace std; int ul(int x,int y,int f){ char w[4] = {'R', 'U', 'L', 'D'}; for (int i=0;i<x;i++) printf("%c",w[f%2*2]); for (int i=0;i<y;i++) printf("%c",w[f%2*2+1]); return 0; } int main(){ int sx,sy,tx,ty; scanf("%d %d %d %d",&sx,&sy,&tx,&ty); ul(abs(sx-tx),abs(sy-ty),0); ul(abs(sx-tx),abs(sy-ty),1); printf("D"); ul(abs(sx-tx)+1,abs(sy-ty)+1,0); printf("LU"); ul(abs(sx-tx)+1,abs(sy-ty)+1,1); printf("R\n"); return 0; }
同じ座標を通らずに2往復最短経路だということで2つの座標から作れる長方形の辺と、更にその1つ外側を移動するイメージで移動を決めました。対角線を描くような感じで移動しようとしても斜め先に移動するのに縦横2手かかるので全然縮まらないです。
D - Candidates of No Shortest Paths
C++14
#include<bits/stdc++.h> using namespace std; typedef vector<vector<int> > Matrix; const int INF=100000000; Matrix d; void warshall_floyd(int n) { for (int i=0;i<n;i++) for (int j=0;j<n;j++) for (int k=0;k<n;k++) d[j][k]=min(d[j][k], d[j][i]+d[i][k]); } int main(){ int mod=1000000007; int n,m,x=0,ans=0; scanf("%d %d",&n,&m); int chk[m][3]={0}; d=Matrix(n, vector<int>(n,INF)); for (int i=0;i<n;i++) d[i][i]=0; for (int i=0;i<m;i++) { int from,to,cost; scanf("%d %d %d",&from,&to,&cost); from--; to--; d[from][to]=cost; //0-index or 1-index d[to][from]=cost; //0-index or 1-index chk[i][0]=from; chk[i][1]=to; chk[i][2]=cost; } warshall_floyd(n); for (int i=0;i<m;i++) { if (d[chk[i][0]][chk[i][1]]<chk[i][2]) ans++; } printf("%d\n",ans); return 0; }
ワーシャルフロイドで全頂点間の最小コストを計算する。入力で与えられた辺のコストと比較する。入力のコストのほうが高い場合は使わない辺なのでカウントする。カウントした辺の数が解になる。