ABC 109 反省
久々にコンテスト中に全完できました. しかし, B問題でWAを連発してしまったため, 大きくペナルティを食らってしまったのは反省事項です.
A問題
問題
解法
を1~3まで試します.
感想
素直に実装しましたが, が奇数だったら"Yes", そうでなければ"No"です.
B問題
解法
次の文字の先頭と今みている文字の尻が一致しているかをみるついでに, map
感想
yukicoder解いてるときにWAが出るとすぐテストケースをのぞいてしまう癖があるので, こういう不測のWAに弱いとこがありました. 反省します.
C問題
問題
解法
すべてのに対して
の差分を取り, これら
すべての最大公約数が答えとなります.
各の間の距離が
の倍数であり, さらに
から距離
でステップしてどれかの
に到達することができれば,
で数列間を移動することができます. その中での最大の
は, 各
に対して
すべての最大公約数となります.
感想
解法はなんとなく思いついたのですが, 説明がなんとなく難しいです.
D問題
解法
発想が必要になる問題です.
まず, の制約から,
の解法が求められます.
これがちょっとしたヒントで, 何度もバックトラックして計算するようなことはなさそうであることがわかります.
操作について考察します.
できるだけ偶数マスを増やしたいときは, 奇数マスのコインをどこかに動かせばよいのですが, ここで動かす方向を下方向に固定してみます.
まず1行目を左から右に見て奇数マスのコインを下に動かし,
次に2行目を...として,最後から2番目の行まで繰り返します.
すると, 最後の1行以外のマスをすべて偶数マスにすることができます.
最後の1行については, 奇数マスのコインを順次右側に動かしていくと, 一番右下のマス以外すべて偶数のマスにすることができます.
コインの総数が奇数だった場合, どうしても奇数のマスは1つできます.
コインの総数が偶数だった場合, すべて偶数のマスにできます. このとき, 右下のマスが奇数で他のマスが偶数ということはありえないので, これが最適解であることがわかります.
あとはpairとvectorなどで移動元と移動先を管理し, 丁寧に実装しましょう.
0-indexedで出力してしまい1-WA.
感想
0-indexedで出力してしまったのはちょっとした悔いですが, 解けてよかったです.
総括
最近難しいABCが続いてましたが, 今回は易しかったように思います. ただ, こういうときにWA量産して順位落としちゃうのはよくないですね.
