Educational Codeforces Round 51 参加記録
結果は4完で450位。
4問振り返ります。
A. Vasya And Password
問題概要
以下のクエリを 回処理せよ。
- 与えられる文字列
を最小文字数だけ書き換えて、数字、英小文字、英大文字の全てが含まれるようにせよ。
制約
- 全てのクエリについて、
解法
各文字種を含む・含まないの8通り（「全部含まない」はあり得ないので実際には7通り）で場合分けします。虚無。
ACコード
B. Relatively Prime Pairs
問題概要
正整数 が与えられる。
であり、
は奇数である。
個の整数
を互いに素な2数のペアに分割せよ。（またはそれが不可能であることを判定せよ。）
制約
は奇数
解法
隣り合う2つの正整数は必ず互いに素である、という性質があります。正整数 が2以上の約数
を持っている時、
を
で割った余りは必ず1になるので、2以上の共通約数を持たないことが証明できます。
そのため答えは常にYESで、隣り合う数を順番に出力していけばよいです。
ACコード
C. Vasya and Multisets
問題概要
個の整数
が与えられる。これを、以下の性質を満たすように2つのグループに分ける分け方を1つ示すか、そのような分け方が存在しないことを判定せよ。
- 各グループは0個以上の要素を持ち、それぞれのグループの「グループに1つしか含まれていない整数の種類数」が等しい。
解法
最初に与えられる整数を、その個数に応じて分類します。
- 1個しかない整数：どちらのグループに入れても、必ず「1つしか含まれていない整数」となる。
- 2個ある整数：1+1で分けると、それぞれのグループで「1つしか含まれていない整数」となる。2+0で分けるとどちらも該当しない。
- 3個以上（
個）ある整数：
で分けると、1個のほうだけが「1つしか含まれていない整数」となる。それ以外の分け方では、どちらも該当しない。
それぞれの整数が各グループの「1つしか含まれていない整数の種類数」にどのように影響するかを考えると以下のようになります。
- 1個：1+0
- 2個：0+0 または 1+1
- 3個以上：0+0 または 1+0
これらの合計を2グループ間で揃えるにあたって、1個しかない整数はなるべく均等にしたいです。2個ある整数はどのように分けても差を作らないので関係ありません。3個以上ある整数は1種類追加するかどうかを選べるので、これを調整に使えます。
- 1個しかない整数を均等に分ける。
- 1個しかない整数の個数が奇数だった場合、偏りがあるので、3個以上ある整数をどれか1種類加える。（これができない場合はNO）
- これらの整数がそれぞれのグループで「1つしか含まれていない整数」となるように要素を分ける。
これで解けます。
ACコード
D. Bicolorings
問題概要
2行 列のグリッドを白か黒に塗り分ける。
同じ色のマスが縦か横に繋がっているとき、そのマス同士を連結であるとみなす。連結成分がちょうど 個であるような塗り方を数え上げ、998244353で割った余りを出力せよ。
制約
解法
DPをします。「左から 列目まで見て、その時点での連結成分が
個で、」までは良いですが、追加で何の情報を持たせると遷移がうまくいくでしょうか。
新しい列はどんどん右側に増えていきます。そして、右側に列を足した時に連結成分の数がどうなるかは、それに直接隣接する列の色によって決まります。一番右側の列の情報を持たせてあげればよさそうです。2マスの白/黒で4パターン持っても良いですが、対称性から「色が同じ」「色が違う」の2パターンだけでも十分です。
つまり、「左から 列目まで見て、その時点での連結成分が
個で、一番右の列の色が違う/同じである塗り方の総数」を持ってDPします。くっつくパターンは以下のように書き下せるので、それぞれの遷移を地道に書いていけばよいです。
ACコード
Submission #43137036 - Codeforces
さいごに
この4問はほどほどの難易度でしたが…この次のEかFを本番中に解けないと、という感じですね。
