blogskol

思わず声に出して読みたくなるブログ

ABC164-I hate Matrix Construction

F - I hate Matrix Construction

整理

まずbit毎に解いていいのは明らか
以下bit毎に考えるためu[i],v[j]は0,1で考える
また、同様に出力盤面ans[i][j]も0,1で考える
あと方針としては条件を満たす行列が出力出来るような入力のみを考えることにする
最後に出来た行列が条件を満たすかチェックすれば満たさない入力の時はちゃんと-1を吐くように出来るので
s[i]=0の時
u[i]=1ならans[i][*]=1であり、
u[i]=0ならans[i][j]=0となるjが一つ以上存在する
同様のことを他の条件についても整理すると
(A):s[i]!=u[i]の時ans[i][*]=u[i]
(B):s[i]==u[i]の時ans[i][j]=s[i]を満たすjが一つ以上
(C):t[j]!=v[j]の時ans[*][j]=v[j]
(D):t[j]==v[j]の時ans[i][j]=t[j]を満たすiが一つ以上
となる
あとはこの条件を満たすようにひたすら埋めて行けばいい
ただし実装は本当に大変なので今回はマクロや関数をしっかり使っていく

考察と実装

まず(A)と(C)に関して満たすように埋める

REP(i)if(s[i]^U)REP(j)F(s[i]^1);
REP(j)if(t[j]^V)REP(i)F(t[j]^1);

ただしここで REP(i)はiを[0,n)で回すマクロ
U,Vはそれぞれ実際のu[i],v[j]の現在考えてるbitを表すマクロ
F(a)は（bit毎に考える都合上）一時的な盤面tmp[i][j] にaを書き込むマクロ
詳細な実装は解説の都合上もうちょっと下で

次にBとDに関して、利害が一致しているところを埋める
例えば、s[i]==u[i],t[j]==v[j],s[i]==t[j]が成立しているようなtmp[i][j]をs[i]で埋めることに問題がないのは明らか

REP(i)REP(j)if(s[i]==U&&U==t[j]&&t[j]==V)F(s[i]);

ここまでで一度整理すると、現在盤面で埋まっていないtmp[i][j]は
i行に少なくとも0が一つ以上欲しい&&j列に少なくとも1が一つ以上欲しい
もしくは
i行に少なくとも1が一つ以上欲しい&&j列に少なくとも0が一つ以上欲しい
のどちらか

なので、
i行に少なくとも0が一つ以上欲しく、実際すでに0が一つ以上埋まっている
のようなiについてはまだ埋まっていないマスを全て1で埋めていいのは明らか
これはjや1に関しても同様
また、そのようなマスを埋めることで新たにこの条件を満たす行、列が連鎖的に出来ていく可能性があることも十分に考えられる
そこで、このような考え方で埋められるマスが一つもなくなるまで埋めるという関数ALを作り実行する

void AL(){
  int koushin=1;
  while(koushin--){
    REP(i)
      if(s[i]==U){
        bool f=0;
        REP(j)f|=tmp[i][j]==s[i];
        if(f)REP(j){koushin|=tmp[i][j]<0;F(s[i]^1);}
      }
    REP(j)
      if(t[j]==V){
        bool f=0;
        REP(i)f|=tmp[i][j]==t[j];
        if(f)REP(i){koushin|=tmp[i][j]<0;F(t[j]^1);}
      }
  }
}

koushinは一回のループで更新箇所が一つでも存在しているかを表す変数で、これが0の状態でwhileループを迎えるとこの関数は終了する
fは実際すでに0が一つ以上埋まっている のような条件が満たされているかを表す変数で、これが1の時その行（or列）の埋まっていないマスを条件に出てこないほうの数で埋めることが許される

これでまだ埋まっていないマスに関しては、まぁどうにか適当にマスを選んで埋めてはAL()を呼び出すを繰り返すしかないんだけど、実はこの時次のルールにしたがって埋めていい

ルール

S[i]:i行目で埋まってるマスの数 T[j]:j列目で埋まってるマスの数としてこれら2n個の数字のうち値がn未満であるものを並べる
この集合の中で値が一番大きいものを一つ取り出してその行（or列）の まだ埋まってないマスを一つ好きに選んで埋めていい
ただしここで埋める数はもちろんその行が必要としている数である
（例えば少なくとも一つ以上0が欲しいと言う条件の行だった場合は0）

このルールに従って マスを一つ埋める➡️ALを呼び出す➡︎マスを一つ埋める➡️ALを呼び出す...
と言うのを全てのマスが埋まるまでやればよい

このルールが正しいことの証明はACです（はい!?）
多分合ってるとは思うんだけど詰めるのが面倒なんだよね、もしかしたら間違ってるのかも
埋まってないマスが1つしかない行なんかは真っ先に埋めないといけないのは自明で、そう言うマスがない場合には埋まってないマスがある行や列だけを抜き出すと埋まってないマスが長方形とかに多分なってて、それは唐草模様で埋めればいいから最初の一つは好きに埋めていいとかそんな感じじゃないかな

取り敢えずコードを書くと

struct P{int va,idx,ve,ne,al;};
bool operator <(const P&a,const P&b){return a.va<b.va;};
priority_queue<P>que;

IN=1;
REP(i)if(S[i]<n)que.push({S[i],i,'S',s[i],1});
REP(j)if(T[j]<n)que.push({T[j],j,'T',t[j],1});
while(que.size()){
  P p=que.top();que.pop();
  if(p.ve=='S'){
    int i=p.idx;
    if(p.va<S[i])continue;
    REP(j)
      if(!~tmp[i][j]){
        F(p.ne);
        p.ne^=p.al;p.al=0;
      }
    AL();
  }
  else{
    int j=p.idx;
    if(p.va<T[j])continue;
    REP(i)
      if(!~tmp[i][j]){
        F(p.ne);
        p.ne^=p.al;p.al=0;
      }
    AL();
  }
}

INに関しては後述
Pは埋まっていない行、列の情報を全部持たせる構造体で、これをpriority_queueに持たせることで埋まってるマスが多い順にやるというのが基本方針
va,idx,ve,neはそれぞれ埋まってるマスの数、そのマスの番号、それが行か列か、埋めたい数（alは必ず1を入れるもので意味は後述）
雑にqueに突っ込んでいくのでqueに入れてから取り出されるまでに他の方向から既にマスがいくつか埋められてることも起こりうる
if(p.va<S[i])continue;はそういったことが起きてた行に関してはスキップするためのもの 

REP(j)
      if(!~tmp[i][j]){
        F(p.ne);
        p.ne^=p.al;p.al=0;
      }

が埋めてる箇所で、 tmp[i][j]を最初に-1で初期化しておくことで、!~tmp[i][j]がtrueならばそのマスが埋まってないことを示す
この時そのマスを欲しい数字p.neで埋めるが、その行の残りのマスはp.ne^1で埋めていいことも明らかであるから、p.ne^=p.al;をして残りのマスをp.ne^1で埋めてしまう
p.ne^=1;は一回だけ実行されて欲しいのでp.al=0;で意味をなくしてしまう

マスを埋めるたびにqueには最新のマスの情報を持っていて欲しい
そこで、数を埋めるマクロであるFの実装にその機能を組み込ませる
ただし最初の方の行全部を0で埋める操作などでまでqueに情報を入れていってはTLE,MLEするので、入れる時を表すbool値INを用意しておく

#define F(va) {\
  if(!~tmp[i][j]){\
    ans[i][j]+=((ul)1<<bit)*(tmp[i][j]=va);\
    if(++S[i]<n&&IN)que.push({S[i],i,'S',s[i],1});\
    if(++T[j]<n&&IN)que.push({T[j],j,'T',t[j],1});\
  }\
}

なんか見辛いね
~tmp[i][j]の時は既に埋まっているので何もしない
そうでなければtmp[i][j]に代入するついでにans[i][j]にもその値を正しいbitで加算する（ ulはunsigned long long）
S[i],T[j]はtmp[i][j]が新しく埋まるたびに1を足し、INがtrueで値がn未満の時だけqueにpushする

これでbit毎にやることは終わったので、以上の過程を64bit分やったあと、正しいかをチェックして出力すればいい

REP(i){
  ul A=ans[i][0];
  REP(j)
    if(s[i])A|=ans[i][j];
    else A&=ans[i][j];
  if(A!=u[i])ng();
}
REP(j){
  ul A=ans[0][j];
  REP(i)
    if(t[j])A|=ans[i][j];
    else A&=ans[i][j];
  if(A!=v[j])ng();
}
REP(i){
  REP(j)cout<<ans[i][j]<<" ";cout<<endl;
}

あとul A=ans[i][0];のところは注意が必要で、ちょっと考えるとわかるけどこれをul A=0;としちゃうと間違いなので気をつけようね（A=0;にしたらどれだけ論理積をとってもA=0のまま）
ng()は-1を出力したのちプログラムを終了させる関数

最後に全部組み合わせる（多少紹介したものとは順番が違ったりする）

#include <bits/stdc++.h>
using namespace std;
using ul=unsigned long long;
int s[500],t[500],tmp[500][500],S[500],T[500],n,bit=-1,IN;
ul ans[500][500],u[500],v[500];

void ng(){
  cout<<-1;
  exit(0);
}

struct P{int va,idx,ve,ne,al;};
bool operator <(const P&a,const P&b){return a.va<b.va;};
priority_queue<P>que;

#define REP(i) for(int i=0;i<n;i++)
#define U ((u[i]>>bit)&1)
#define V ((v[j]>>bit)&1)

#define F(va) {\
  if(!~tmp[i][j]){\
    ans[i][j]+=((ul)1<<bit)*(tmp[i][j]=va);\
    if(++S[i]<n&&IN)que.push({S[i],i,'S',s[i],1});\
    if(++T[j]<n&&IN)que.push({T[j],j,'T',t[j],1});\
  }\
}

void AL(){
  int koushin=1;
  while(koushin--){
    REP(i)
      if(s[i]==U){
        bool f=0;
        REP(j)f|=tmp[i][j]==s[i];
        if(f)REP(j){koushin|=tmp[i][j]<0;F(s[i]^1);}
      }
    REP(j)
      if(t[j]==V){
        bool f=0;
        REP(i)f|=tmp[i][j]==t[j];
        if(f)REP(i){koushin|=tmp[i][j]<0;F(t[j]^1);}
      }
  }
}

int main(){
  cin>>n;
  REP(i)cin>>s[i];
  REP(i)cin>>t[i];
  REP(i)cin>>u[i];
  REP(i)cin>>v[i];

  while(++bit<64){
    memset(tmp,-1,sizeof(tmp));
    memset(S,0,sizeof(S));
    memset(T,0,sizeof(T));
    IN=0;

    REP(i)if(s[i]^U)REP(j)F(s[i]^1);
    REP(j)if(t[j]^V)REP(i)F(t[j]^1);
    REP(i)REP(j)if(s[i]==U&&U==t[j]&&t[j]==V)F(s[i]);

    AL();
    IN=1;
    REP(i)if(S[i]<n)que.push({S[i],i,'S',s[i],1});
    REP(j)if(T[j]<n)que.push({T[j],j,'T',t[j],1});

    while(que.size()){
      P p=que.top();que.pop();
      if(p.ve=='S'){
        int i=p.idx;
        if(p.va<S[i])continue;
        REP(j)
          if(!~tmp[i][j]){
            F(p.ne);
            p.ne^=p.al;p.al=0;
          }
        AL();
      }
      else{
        int j=p.idx;
        if(p.va<T[j])continue;
        REP(i)
          if(!~tmp[i][j]){
            F(p.ne);
            p.ne^=p.al;p.al=0;
          }
        AL();
      }
    }
  }

  REP(i){
    ul A=ans[i][0];
    REP(j)
      if(s[i])A|=ans[i][j];
      else A&=ans[i][j];
    if(A!=u[i])ng();
  }
  REP(j){
    ul A=ans[0][j];
    REP(i)
      if(t[j])A|=ans[i][j];
      else A&=ans[i][j];
    if(A!=v[j])ng();
  }

  REP(i){
    REP(j)cout<<ans[i][j]<<" ";cout<<endl;
  }
}

出すと通るのでこれが数学的にも正しく計算量的にも問題がないことが分かる（分かるので）
Submission #12534981 - AtCoder Beginner Contest 164
ちゃんとした証明や計算量解析が欲しいって人はごめんね
だいぶ無駄のある動きの多いコードだから同じ方針でも時間はもっと縮められるはず

感想

怠いね
苦労した理由はフローや乱拓に逃げようとしちゃったりバグを見逃しまくったりしたこと
特にマクロは使い慣れてないからいろんなタイプのミスをした
考え方としてはそんなに難しいことは使ってないつもりで、実装が大変なので構造体やマクロ、関数を上手に使ったり、自分が分かりやすい実装ルールをしっかりと決めるのがいいと思う（「必要な数」を表す変数の変数名はneedから取ってneとかループ変数は行をi,列をjを使うとか）