2021年9月21日火曜日

Educational Codeforces Round 114 (Rated for Div. 2)

 pretestはDまで。コンテスト終了間際にEの大体の考察はできた。
 システムテストでDがMLEで落ちたけど、setに突っ込むものをtupleからhash(tuple)に変えて通した。(衝突させるテストケースは作れるだろうけど)


E. Coloring

 良い行列の作り方は、

・一行目を決定→n行目はn-1行目の反転
・一列目を決定→n列目はn-1列目の反転

 で全てを網羅できる。また、その方法で作ったものは全て良い行列になる。
 ただし、それだと市松模様が重複するので、その場合を引かないとダメ。

 実装は結構大変なものになってしまった。

・x=3, y=3で1
・x=x, y=5で0

 とかがあると、「一列目を決定→……」の操作では矛盾するので作れないのだけど、そういう、「この操作でやろうとすると矛盾」というのを管理するため、「一列目が1のときと矛盾しないものが何個で、0と矛盾しないもの何個か」を管理する。

 それが矛盾しないときにだけ計算する、という感じでやった。

0 件のコメント:

コメントを投稿