Posted at

atcoder ABC109

C,D共に基礎的な問題だった。

https://atcoder.jp/contests/abc109


C問題


方針

全ての都市と都市をDの倍数でいかなければならないため、初期場所Xとそれぞれの都市との距離を配列で記録し、その配列について、最大公約数を求めれば良い。最大公約数はユークリッド互除法で求める。


ユークリッド互除法

実装は以下の通り

static long gcd(long a,long b){

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


D問題


方針

マスが持つコイン数をできるだけ偶数化したいということで、マスについて、左端から見ていき、マスの持つコイン数が奇数だあったら、右もしくは下にコインを送るという操作をすることで、偶数枚持つマス目が最大になる。