Diagonal Walking v.2 [Educational Codeforces Round 50 (Rated for Div. 2) B]

http://codeforces.com/contest/1036/problem/B

(0,0)から(n,m)への移動を考える。
2種類の移動がある。
1. 隣接するマスへ移動する（上下左右）
2. 対角線上へ移動する（左上、右上、右下、左下）
K回移動して(n,m)へ行く方法は複数あるが、その中で対角線移動の最大値を求めよ。

解法

http://codeforces.com/contest/1036/submission/42628431

根性場合分けをする。
本当に根性なので、あまり参考にならないだろうが、自分がやった改善点だけ述べておく。

• N,Mが反対になっていても答えは変わらないので、N≦Mにして考える
• なるべく最短距離で移るようにしてゴール付近で辻褄をあわせる
• 偶奇を利用して頑張る

　
方針としては、まずはなるべく対角線移動で近づく。
すると、X座標が同じでY座標だけ異なる状況となる。
ここから更になるべく対角線移動で近づく。
マンハッタン距離が2以下となったら、処理を細かく場合分けしていく。

ll N, M, K;
//---------------------------------------------------------------------------------------------------
ll solve() {
    cin >> N >> M >> K;

    if (N > M) swap(N, M);

    if (N == M) {
        if (K < N) return -1;
        ll ans = N - 1;

        K -= N - 1;

        if (K % 2 == 0) ans += K - 2;
        else ans += K;

        return ans;
    }

    ll ans = N;
    ll req = N;

    M -= N;

    if (M % 2 == 0) {
        ans += M - 2;
        req += M - 2;
        M = 2;

        if (K < req + 2) return -1;

        ans++;
        req++;
        
        ll d = K - req;

        if(d % 2 == 1) ans += d;
        else ans += d - 2;

        
        return ans;
    } else {
        ans += M - 1;
        req += M - 1;
        M = 1;
        if (K < req + 1) return -1;

        ll d = K - req;
        ans += d - 1;

        return ans;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) {
        auto ans = solve();
        printf("%lld\n", ans);
    }
}