ABC075 (AtCoder Beginer Contest 075)

　久しぶりの更新です。正直このブログの存在を忘れてましたm(_ _)m

　おとといABCがあったので、それの解答を載せたいと思います。C問題のコンパイル通らなくて辛かったです。終了数分前にやっとコンパイル通したらWAだったという。。。そんな感じのABCでした。そもそも手元でコンパイルぐらい通してから提出しろよという(←n回目の懺悔(n≥3))

A - One out of Three

　まずはA問題ですね。問題名は「One out of Three (3人の中の一人)」。３つの整数 A、B、C がもらえるので、仲間はずれ君を探し出してやればACをもらえます。入力例1が 5 7 5 なのはご愛嬌ですね。

#include <iostream>
using namespace std; 
int main(void){ 
  int A, B, C; 
  cin >> A >> B >> C; 
  if(A==B) cout << C; 
  else if(B==C) cout << A; 
  else cout << B; 
  return 0; 
}

　気づきましたでしょうか。そうです。シンタックスハイライターが使えるようになりました(嘘。はてな記法です。できてなかったらごめんなさい。

　肝心のコードですが、今回はスタートダッシュしたかったので入れ子{}というものをできるだけ使わない書き方にしました。提出コードはchar型の変数宣言をコメントアウトしてたりしててもっと汚いです。。。

　if文やfor文の{}は、操作が1行で済むなら使わなくても大丈夫です。インデント的にどうなの？　と思うことはありますが。。。下のコードのように書いても問題なく動きますが、さすがに見づらい(可読性が低い)ので自重しましょう。可読性は大事です。

if(A==B) 
cout << C; 
else if(B==C) 
  cout << A; 
else cout << B;

B - Minesweeper

　つぎはB問題です。問題名は「Minesweeper」明らかにms社のパソコンに積んであるあのゲームですね。はじめに H * W の文字列がもらえて、' # ' が爆弾(地雷)マス、' . ' が空きマスです。空きマスを周囲8マスにある爆弾の数に置き換え、爆弾マスはそのまま ' # ' で出力できればACもらえます。

#include <iostream>
using namespace std;

int main(void){
    int H, W;
    cin >> H >> W;

    char m[H+2][W+2];
    for(int i = 0; i < H+2; i++){
        for(int j = 0; j < W+2; j++){
            if(!i || !j) m[i][j] = '.'; //!i は i==0 と同義
            else if(i==H+1 || j==W+1) m[i][j] = '.';
            else cin >> m[i][j];
        }
    }
            
    for(int i = 1; i < H+2; i++){
        for(int j = 0; j < W+2; j++){
            if(m[i][j] == '.'){
                int bom = 0;
                if(m[i-1][j-1] == '#') bom++;
                if(m[i-1][ j ] == '#') bom++;
                if(m[i-1][j+1] == '#') bom++;
                if(m[ i ][j-1] == '#') bom++;
                if(m[ i ][j+1] == '#') bom++;
                if(m[i+1][j-1] == '#') bom++;
                if(m[i+1][ j ] == '#') bom++;
                if(m[i+1][j+1] == '#') bom++;
                cout << bom;
            }else{
                cout << "#";
            }
            if(j == W-1) cout << endl;
        }
    }
    return 0;
}

　今いるマスの左上、左、左下、上、下、右上、右、右下のマスを、そのマスあるかな～(端っこじゃないよね？)といちいち確認しながら爆弾あるかな～と数えていってます。最近セグメントエラー(coreを出力しました)という文字列をよく見るので、変なとこ(配列のサイズの外側)の値を参照したりしないように、配列mの大きさを上下左右に1つづつ広くとってます。以上。

C - Bridge

　つづいてはC問題です。問題名は「Bridge」、グラフから辺を取り除いたときに、グラフ全体が非連結になるような辺を「橋」というそうです。最初に、いつもの自然数N、Mがもらえるので、N個の頂点を結ぶM本の辺がもらえるので、上手いことやって橋の本数を求めてください、という問題ですね。

#include <iostream>
using namespace std;

bool g[51][51];
bool gg[51][51];

bool cone(int n){
  bool rtn=true;
  bool ck[n+1] = {false, true};
  for(int k=0; k<n; k++)
    for(int i=1; i<=n; i++)
      for(int j=i+1; j<=n; j++)
        if(gg[i][j] && (ck[i] || ck[j]))
          ck[i]=true, ck[j]=true;

  for(int i=1; i<=n; i++)
    if(ck[i]==false) rtn = false;

  return rtn;
}

bool coneRemoveAB(int n, int a, int b){
  for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
      gg[i][j] = g[i][j];

  gg[a][b]=false;
  gg[b][a]=false;

  return cone(n);
}


int main(void){
  int n, m;
  cin >> n>> m;

  int a[m], b[m];
  for(int i=0; i<m; i++){
    cin >> a[i] >> b[i];
    g[a[i]][b[i]] = true;
    g[b[i]][a[i]] = true;
  }

  int bridge = 0;
  for(int i=0; i<m; i++)
    if(!coneRemoveAB(n, a[i], b[i])) bridge++;

  cout << bridge << endl;
  return 0;
}

　bool型の配列g[i][j]は、iからjへの辺があるかどうかを記録します。関数coneRemoveABで、グラフgから辺abを取り除いた配列ggを作って、関数coneで、グラフ全体が連結かどうかを判定します。これをm回(辺の数)だけ繰り返してあげると、取り除いたときにグラフ全体が非連結になる辺(橋)の数が分かるというわけです。
　冒頭にも書いた通りコンテスト中にC問題は通せなかったのですが、その原因は関数coneの3重ループです。2重ではいけません。gg[1][2]==false, gg[1][3]==true, gg[2][3]==true のときなど、嘘関数になってしまい、、、
　つまり、2重ループではいけないのです(コンテスト終了直前に気付いた)。それで3重ループにするわけですが、じゃ何回繰り返すの？　ってことなんですが、1番多いときで、gg[2][3], gg[3][4], gg[4][5], ... ... , gg[n-1][n], gg[n][1] だけがtrueみたいな感じのときで、n回なんですね。というわけで1番外側のループはn回繰り返せばいいわけです(←だいたいワーシャルフロイド法)。みなさんは全探索ぐらい余裕で書けるようになりましょう()

　D問題も一応コンテスト中に実装しようとしたんですが、vectorの使い方が分からないままvector使おうとして死んだので、、、

　というわけでまた次回にゃ～～～～～～～～～～～～～～～～～～～(てーげー)