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 件のコメント:
コメントを投稿