AtCoder
java8

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問題

方針

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