Codeforces Round #630 (Div. 2)

参加しました。3完で3883位(rated内)で、レート1626(-20)になりました。ギリギリ青をキープです。

順位表

A. Exercising Walk

問題へのリンク

軸と軸は対称なので、軸に関して考察します。 左に 回、右に 回移動すると、最後に到達する座標は経路によらず になります。

a = b のとき

交互に動きますが、隣の座標に行くことは避けられません。が区間に入っているか確認します。

サンプルに入っているのでいいとは思いますが、のときは左右に動かないのでコーナーケースです。

a != b のとき

最終的にその座標に行き着きますが、動く範囲をなるべく小さくしたいので、その座標をオーバーするような移動をすることはなく、また最終的に到達する方向と逆向きに移動する必要もありません。よって、最終到達座標が区間に入っているかどうかを確認すればよいです。

以上の考察により、以下のような条件をともに満たすかを確認すればよいことがわかります。

提出へのリンク

bool isin(int s, int l, int r){
    return l <= s && s <= r;
}

bool check(int a, int b, int sx, int x1, int x2){
    if(a == b){
        return a == 0 || isin(sx + 1, x1, x2) || isin(sx - 1, x1, x2);
    }
    return isin(sx + b - a, x1, x2);
}

B. Composite Coloring

問題へのリンク

割とギャグ枠。

以下の合成 が 個与えられるので、それらを互いに素でない個以内の集合に分けてください、という問題。

以下の合成数は、全て以下の素数の倍数です。 なので、の倍数ごとに分ければ終わりです。

以下の合成数が全て以下の素数のみを素因数に持つことは、より大きい、つまり以上の素数のみを素因数に持つ合成数はを超えてしまうことから示せます。

提出へのリンク

C. K-Complete Word

問題へのリンク

これもとても簡単。文字列を個ずつに分けて、それぞれが同じ文字列かつ回文にするのに必要な編集量なので、 同じ文字列が最も多いものに合わせて他を変えればいいです。

提出へのリンク

D. Walk on Matrix

問題へのリンク

天才構築です。DP自体は動きますが、これが最大となるとは限らないことがわかります。つまり、部分問題の結果が次に使えない場合があるのです。bit演算の結果の最大化なのでそれはそうです。

解説通り構築してあげればよいです。面白い問題ですね。

本番も見ながら構築だろうなあと思いながらDPの遷移を考えていたら時間切れになりました。

提出へのリンク

E - Height All the Same

考えてみたら楽しかったので解説を書きました。

解説へのリンク

参考

• 公式解説