ABC083とABC088を解いたので簡単に考えたことなどを残しておきます。
ABC083
問題・ソースコード
C問題
最小値を2倍していって上限を超えたらそこまでで2倍できた回数+1が答えになります。2倍することがもっとも小さく倍数を作る方法なのでこれが最大です。
D問題
両端からうまいことひっくり返していくのかなと考え、短い数列をいじくってみるもわからなかったので観念して解説を見ました。
ポイントはK以上を全部ひっくり返すことができるということで、0と1の境界から両端への長さで長い方の最小値をKとすると0と1の境界を一つ減らすことができます。
例えば0001101011という数列が与えられたとして、0と1の境界でもっとも端に近いのは端のちょうど真ん中の部分。
K=5として左側をひっくり返すと1110001011となって境界がひとつ減らせます！そしてこれ以降はK以上の長さの部分をひっくり返せばどんどん境界を減らしていけます。そして境界を0にすればゴール(全部1でも全部ひっくり返せば0にできます)
0001101011(左から5つをひっくり返す)
1110001011(右から7つをひっくり返す)
1111110100(左から6つをひっくり返す)
0000000100(左から7つをひっくり返す)
1111111100(左から8つをひっくり返す)
0000000000(やった)
また最初にKとして境界から両端への長い方の最小値を取っていたので全ての境界は左か右にK以上の長さがあり、長い方をひっくり返せば良いです。全ての境界のどちらかでひっくり返さないといけないのでKが最大になります。
なるほどなあ。
ABC088
問題・コード
C問題
行間、列間の差が3つとも等しければa,bが存在して矛盾がないのでそこを調べてやればいいです。とても汚いコードになってしまいました。
D問題
迷路の最短経路問題といえば幅優先探索。ということでまず(1,1)から(n,n)までの最短距離を求めてやります。
最短距離が求まらなければたどり着けないということなので-1を返します。最短距離が求められればその一本道さえあればたどり着けるということなので、もともとあった白いマスの数から一本道で使うマス(最短距離+1)を引いてやれば答えがでます。
