No.565 回転拡大 (行列の90度回転)

• Quiz
  • https://yukicoder.me/problems/no/565
• 行列の回転（90度刻み）、拡大（整数倍）を実装せよ
  • AC https://yukicoder.me/submissions/350976
• その他
  • 90度回転を何度か重ねがけすることで180, 270度回転を実装すると楽
• 注意※
  • 上記ACでは文字の行列を回転している（数字ではない）ので、数値行列の回転をしたい時はcharをllに書き換えること。（下記コードでは修正済み）

成果物

• 行列の回転
• 行列の拡大
• 行列のPrint

// 時計回りに回転
VV rot90(VV mat){
    ll H = mat.size();
    ll W = mat[0].size();
    
    ll new_W = H;
    ll new_H = W;

    VV M(new_H);
    FOR(y, 0, new_H){
        for(ll i=H-1; i>=0; i--){
            ll c = mat[i][y]; // 型に注意 (char or long long)
            M[y].push_back(c);
        }
    }
    return M;
}

別の問題にて再利用。数値行列の回転

• 「E-Lamps」にて、二次元配列を上下左右から累積を取る処理があり、同じようなコードが4つできる
• これを回転で共通化できると思い、やってみたらできた
• 😢ハマったのは、上記注意※でも書いているが、参考にしたrot90内にcharが混ざっていて特定ケースのみRE
• 😢ライブラリは信じているので最後までチェックが遅れた
• 😢同じようなコードをコピペしないというのは達成できたがハマる箇所も多かったのでコンテスト中は愚直に書いたほうがいいこともある。速い人も愚直に書いている
• AC✅https://atcoder.jp/contests/hhkb2020/submissions/23107393

E. Cover it!

Quiz

• https://codeforces.com/contest/1176/problem/E
• 高々N/2個の頂点で点被覆せよ

AC

• https://codeforces.com/contest/1176/submission/55399046
• bfsで黒と白(0, 1)に塗っている

解法

• グラフを2色に塗る（例えば白と黒とする）
• 現在見ているノードを白で塗ったなら、隣はできるだけ黒で塗るようにする
• 塗り終わった時、数の少ない色の方を答えとして出力

参考

(→)
D:最大値Mを見て,Mが素数ならM<p_Mよりあるkが存在してp_k=Mなのでkをaに入れkとMをbから消す.Mが合成数ならMの最小素因数qとしてM>M/qよりM/qをaに入れM,M/qをbから消す.これをbが空になるまでやる
E:グラフを2色で彩色(同色が隣り合っても気にしない)する,少ない方の色の頂点たちが答え
(→)

— satanic@競プロ🔥 (@satanic0258) 2019年6月9日

私の誤解法

• （白で最小点被覆を貪欲にやろうとして・・・↓）
• 次数多い点から取り出して、まだ塗られていないなら白で塗り、その隣は塗られていなければ黒で塗る
• 白を答えとして出力する
• ダメな例

別解

• dfsで2色に塗っても通った
• https://codeforces.com/contest/1176/submission/105019182
• ただ、グラフが木じゃない時のdfsは塗り順をイメージしづらいので避けた方がいいかも

n & (n-1)

用語

• LSB : least significant bit 一番右の立っているビット
• MSB : most significant bit 一番左の立っているビット

LSB 求め方

a = 1010
-a= 0110
(足すと0になる)

a & (-a) = 0010 (LSB)

その1: LSBを0にする

• 一番右の立っているビットを消す
• 例

101010 (n)
101001 (n-1)
------ (&)
101000

その2: 2のべき乗判定に使える

• nが2のべき乗なら(1, 2, 4, 8, ...) trueを返す関数なら、

bool is_power_of_two(ll n){
    return !(n & (n-1));
}

MSB 求め方1

• 2で割っていけばO(log(N))で求まる

// 0番目から数える
// v==0の時はどうする？
ll MSB(ll v){
  rep(i,50){
    v /= 2;
    if(v==0) return i;
  }
}

例
[MSB(2)]: 1
[MSB(3)]: 1
[MSB(4)]: 2
[MSB(15)]: 3
[MSB(16)]: 4
[MSB(17)]: 4

MSB 求め方2

#include<bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
using ll = long long;

#define p(s) cout<<(s)<<endl

ll MSB(ull i){
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    ull v = i - (i >> 1);
    return log2(v);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll v = 0b0001010100;
    auto bs = bitset<15>(v);
    p(bs);
    p(bs._Find_first()); // LSB

    p(MSB(v)); // MSB
    
    return 0;
}

// 出力
000000001010100
2
6

• 参考：https://codeforces.com/blog/entry/10330

No.267 トランプソート

Quiz

https://yukicoder.me/problems/no/267

Submission

https://yukicoder.me/submissions/350277

解法

• vector<pair<int, int> > Aをソートすると、firstの昇順でソート、firstが同じグループの中ではsecondの昇順でソートされる
• それを使うことを見越して絵柄(D, C, etc)や数字(A, 2, 3, etc)を数字に変換する
• 絵柄
  • "ダイヤ、クローバー、ハート、スペードの順に並べます"
  • とあるので、
  • ダイヤ=0, クローバー=1, ハート=2. スペード=3
  • とすればいい
• 数字 "𝐴:1 、𝑇:10、𝐽:11、𝑄:12、𝐾:13"
• ソート後はpairの数字を（必要なら）アルファベットに逆変換しながらprintすればいい

No.71 そろばん

Quiz

https://yukicoder.me/problems/no/71

Submission

https://yukicoder.me/submissions/350266

考察

• N=5
  • 普通のそろばんと同じ数
  • 1, 4に分けると0〜9までの10種類を表現できる
  • 一方、サンプルケースでは2, 3に分けることで11種類を表現できる
  • 等分すると表現できる数が増えそう
    • 11 -> 5, 6に分ける
• 2, 3に分けた場合
  • 下記の画像のようにすれば、隙間なく0から表現できる

No.72 そろばん

• https://yukicoder.me/problems/no/72
• O(1)解法なので、こちらも同様に解ける