ABC051 の問題を解いてみました

A問題

, を にして出力すれば解くことができます。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  string s;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    if(s[i] == ',') cout << " "; // , なら   を出力
    else cout << s[i];
  }
  cout << endl;
}

B問題

典型的な TLE を回避する方法を使います。
$x, y$ を決めると、$z = s - (x + y)$ にするしかないことを利用して、計算量を削減します。

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int k, s;
  cin >> k >> s;
  
  int ans = 0;
  for(int x = 0; x <= k; x++){
    for(int y = 0; y <= k; y++){
      int z = s - (x + y); // z を求める
      if(0 <= z && z <= k){ // z が条件を満たしているなら
        ans++;
      } 
    }
  }
  cout << ans << endl;
}

C問題

2つの点は、4方向全てから出入りしないといけないです。
そのため、最短ルートは自ずと決まってきます。
下の画像のようなルートをとる道筋を出力します。

(赤色の長さ = $ty - sy$ で、 青色の長さ = $tx - sx$)

#include <bits/stdc++.h>
using namespace std;
//Created by karaju.

int main(void){
  int sx, sy, tx, ty;
  cin >> sx >> sy >> tx >> ty;
  string s = "";
  
  for(int i = 0; i < ty - sy; i++){
    s += "U";
  }
  for(int i = 0; i < tx - sx; i++){
    s += "R";
  }
  for(int i = 0; i < ty - sy; i++){
    s += "D";
  }
  for(int i = 0; i < tx - sx; i++){
    s += "L";
  }
  
  s += "LU";
  
  for(int i = 0; i < ty - sy; i++){
    s += "U";
  }
  for(int i = 0; i < tx - sx; i++){
    s += "R";
  }
  
  s += "RDRD";
  
  for(int i = 0; i < ty - sy; i++){
    s += "D";
  }
  for(int i = 0; i < tx - sx; i++){
    s += "L";
  }
  
  s += "LU";
  
  cout << s << endl;
}

追加情報

この記事を書いたあとに知ったのですが、
string(n, ch);
と書くと、chをn個連結したものが返されるそうです。

D問題

最短経路が絡んでくる時に使うアルゴリズムといえば、ダイクストラ法やワーシャルフロイド法などがあります。
今回は、ワーシャルフロイド法を使って解いていきます。(どちらでも解ける)

ワーシャルフロイド法の解説記事↓

ワーシャルフロイド法を使えば、すべての頂点からすべての頂点への最短経路を求めることができます。(全点対間最短経路の距離を求められる)

回答のプログラムでは、まず辺の情報を配列で記録します。
そして、その配列のコピーの配列$copy$を作っておきます。
そして、ワーシャルフロイド法を行って、配列$graph_{i,j}$にiからjへの最短経路の距離を代入します。

  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      if(copy[i][j] > graph[i][j]){
        ans++;
      }
    }
  }

このコードを見てください。
上のif文は、iからjへの最短経路が、iとjを結ぶ辺ではなかったときにのみtrueを返します。
そして、その場合、iとjをつなぐ辺はどの最短経路にも含まれません。
結局そこをもっと短く移動する方法があるからです。

よって、このif文でtrueを返した数が、どの最短経路にも含まれない辺の数です。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//Created by karaju.

signed main(){
  int n, m;
  cin >> n >> m;
  vector<vector<int> > graph(n, vector<int>(n));
  vector<vector<int> > copy(n, vector<int>(n));
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(i == j){
        graph[i][j] = 0;
      }
      else graph[i][j] = 1e9;
    }
  }
  
  for(int i = 0; i < m; i++){
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    graph[a][b] = copy[a][b] = graph[b][a] = copy[b][a] = c;
  }
  
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
        graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k]);
        //iを経由したほうが短いかを試す
      }
    }
  }
  
  int ans = 0;
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      if(copy[i][j] > graph[i][j]){
        ans++;
      }
    }
  }
  cout << ans << endl;
}