前回解いたAtCoder035をもう一回解き直した。
まず最初に作ったのはテストを追加した。 例題の問題を突っ込んで、答えがあっているかを確認するだけ。 https://github.com/buty4649/atcoder/tree/master/035/spec
次に、Aを直した。
前回解いた時は 16:9 or 4:3 な入力が保証されているので、決め打ちで解いてしまっていた。
しかし、よくよく考えるとWとHの最大公約数を取ってそれで割ればいいことに気がついた。
これで 16:9 や 4:3 以外でも取れるようになった。
Submission #732515 - AtCoder Beginner Contest 035 | AtCoder
Bも修正。 アルゴリズムと言って良いのかわからないけど、解き方を変えた。 入力をみてXとYの位置を変更していたけど、最終的にマンハッタン距離を出せばいいのでXとYの位置を保持する必要がない。 LとR、UとDの数をそれぞれ数えて互いの数を引いた数がそのまま答えになるということに気がついた。
最大値を求める場合ここに?の数を加えればよい。
逆に最小値を求める場合、?の数を引けばいい…わけではなく、少し工夫が必要だった。
http://abc035.contest.atcoder.jp/submissions/732542
Cも修正。 文字列で盤面を保持していたものをビット列にした。 が、これでもTLEになってしまった。。 もっと高速化しないとダメなようだ。
