秘密の本棚

気になることをなんでも書きます

AtCoder Beginner Contest 109

AtCoder プログラミング

AtCoder Beginner Contest 109 - AtCoder

A - ABC333

問題

A - ABC333

考察

整数a,bが与えられるとき、a\times b\times cが奇数となるような整数cが存在するかを判定する。a\times bが偶数であるときcをどのように選んでもa\times b\times cは偶数になる。一方でa\times bが奇数であるときcを奇数とすればa\times b\times cは奇数になる。

コード

int main(){
  ll a,b;
  cin >> a >> b;
  if(a*b%2==0){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  return 0;
}

B - Shiritori

問題

B - Shiritori

考察

N個の単語が与えられるとき、しりとりのルールを守っているかを判定する。まだ発言していない単語かどうかは、連想配列を利用して各文字列の頻度をカウントすることで判定できる。前の単語の末尾と次の単語の先頭が一致しているかは、配列にすべての単語を記憶しておくことで容易に判定できる。

コード

int main(){
  ll n;
  cin >> n;
  str w[n];
  std::map<str, ll> mp;
  REP(i,n){
    cin >> w[i];
    if(i!=0&&(w[i-1].back()!=w[i].front()||mp[w[i]]>0)){
      cout << "No" << endl;
      return 0;
    }
    mp[w[i]]++;
  }
  cout << "Yes" << endl;
  return 0;
}

C - Skip

問題

C - Skip

考察

数直線上にあるN個の点\{x_i\}を、座標Xから\pm D移動することを繰り返してすべて訪れるとき、最大のDを求める。
まず、Xから出発して最初の点x_jを訪れるためには|x_j-X|がDの倍数である必要がある。さらに順次他の点を訪れていくためには|x_k-x_j|がDの倍数である必要がある。これらをまとめると、結局すべてのx_iについて|x_i-X|がDの倍数であることが必要で、これをみたす最大のDは最大公約数である。最大公約数はユークリッドの互除法を用いて効率的に計算することができる。

コード

ll gcd(ll a, ll b){
  if(b==0) return a;
  return gcd(b,a%b);
}

int main(){
  ll n,X;
  cin >> n >> X;
  ll x[n];
  REP(i,n){
    cin >> x[i];
    x[i]-=X;
    x[i]=abs(x[i]);
  }
  ll ans = x[0];
  REP(i,n-1) ans = gcd(ans,x[i+1]);
  cout << ans << endl;
  return 0;
}

D - Make Them Even

問題

D - Make Them Even

考察

h\times wマスに各々数枚ずつ置かれたコインを、1枚ずつ移動させていってできるだけ多くのマスのコインの枚数を偶数枚にするための操作の仕方を求める。制約として同じマスのコインを複数回選んではいけないので、マスを一筆書きの順番で移動させていけばよい。あるマスの枚数が奇数であれば移動を行い、偶数であれば移動を行わないということを繰り返す。

コード

struct move_coin{int from_y, from_x, to_y, to_x;};

std::vector<move_coin> ans;
int a[500][500];

void move(int from_y, int from_x, int to_y, int to_x){
  if(a[from_y][from_x]%2==0) return;
  move_coin m;
  m.from_y = from_y+1, m.from_x = from_x+1, m.to_y = to_y+1, m.to_x = to_x+1;
  ans.push_back(m);
  a[from_y][from_x]--;
  a[to_y][to_x]++;
}

int main(){
  int h,w;
  cin >> h >> w;
  REP(i,h)REP(j,w){
    cin >> a[i][j];
  }
  REP(i,h){
    if(i%2==0){
      REP(j,w-1) move(i,j,i,j+1);
      if(i!=h-1) move(i,w-1,i+1,w-1);
    }else{
      REP(j,w-1) move(i,w-j-1,i,w-j-2);
      if(i!=h-1) move(i,0,i+1,0);
    }
  }
  cout << ans.size() << endl;
  for(auto m : ans){
    printf("%d %d %d %d\n", m.from_y, m.from_x, m.to_y, m.to_x);
  }
  return 0;
}

雑感

今回も用事で不参加で、後日解きました。Dのルールを最初読み違えていて「？？」となりました。ちょっと実装が冗長になってしまった気がします。