ABC109参加してない記録
本番は参加できませんでしたが解いてみた感じで書きます
A - ABC333
が奇数になるCが存在するか確かめる問題
偶数に何をかけても偶数なのでが偶数かどうかで判定
B - Shiritori
しりとりが正しいか判定する問題
これは本当にやるだけ。出現済みかどうかはHashSet等で管理すれば楽だと思います。
C
すべての都市を訪れることが可能な最大の移動距離を求める問題
ずつ移動するので移動距離は
の倍数になります。
番目と
番目の都市を移動するときの距離が必ず
の倍数でないといけないので、
逆を言うとすべての都市の
からの距離が
の倍数であればどの順番であってもちょうどたどりつくことができます。
以上のことから、すべての都市の座標のXからの距離の最大公約数を求めると以上の条件に当てはまる最大の移動距離を求めることができることがわかります。
D
指定された操作を行いコインが偶数枚置かれたマスを最大化する問題
マス目上の全てのコインを足したときに偶数枚であれば何らかの操作ですべてのマスのコインのマスを偶数枚にすることができると予想できます。
また、奇数枚であればどこか1か所を除いて偶数枚にすることができると予想できます。
ということはどこか一か所に向かってコインを集めるような操作をすればうまく偶数枚にすることができそうです。
実装として簡単なのは全体を横に移動してから端の縦を下に移動させる方法だと思います。
