D - AtCoder社の冬

Quiz

https://atcoder.jp/contests/abc003/tasks/abc003_4

Submit

https://atcoder.jp/contests/abc003/submissions/4361326

Note

  • editorialの通りに包除原理
  • サンプルが全部通ればほぼ通る
  • 101点の条件ではもっと小さいテストケースを作るといい

f:id:peroon:20190224063008j:plain

包除原理

  • ベン図にて、足しすぎたら引き、引きすぎたら足すこと
  • 特徴として、プラスマイナスが交互に出てくる

f:id:peroon:20190224062304j:plain

個人的な落とし穴

1 1
1 1
1 0
  • 上記テストケースの解は1
  • 包除原理で足す・引くしている中で下記のコード(途中打ち切り)が必要だった
    // 余分に数えた分を削る
    FOR(i, 1, 1<<4){
        ll x = X;
        ll y = Y;
        ll count = 0;
        FOR(j, 0, 4){
            if(i>>j & 1){
                count++;
                if(j==0 || j==1){
                    x--;
                }else{
                    y--;
                }
            }
        }

        // ココ
        if(x<=0 || y<=0){
            continue;
        }
  • これがないとx=-1, y=-1となったときも以降でx*yしたものが正となり誤作動した

学び

  • 以降を考えなくていいケースは早々に打ち切る(枝刈りする)