行列のアフィン変換(平行移動・回転・X軸で反転(-1倍の拡大))

  • 自分の検索用の記事です

アフィン変換とは?平行移動、拡大縮小、回転、スキューができる。2次元平面を考えているなら3x3の行列で表現。ベクトルは(x,y,1)

使った問題

言い換え

  • x=pで反転とは、平行移動・-1倍・平行移動(戻し)に分解できるので、アフィン変換行列で表現できる

その他のキーワード

  • 線対称

fake nodeと二部グラフ 2部グラフ

  • Quiz
  • 感想
    • 有向グラフの問題に見えるが、よく考えると無向グラフ
    • imposterと言っているなら、頂点x, yは違う色
    • crewmateと言っているなら、頂点x, yは同じ色★
    • ★について、色はまだ不明だけど同じ色であることは確定しているときに使えるのがfake node。x---fake_node---yのように繋げる
    • editorialに書いていて、初めて知った
    • 後は(連結成分ごとに)2部グラフであることを確認して、多い色の方をimposterとして数えればいい
  • editorial
  • 元ネタ:among us

f:id:peroon:20211009090304j:plain

RUPC2018 C-一致 mapの一致判定は速い!?

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

    // input
    ll N;
    cin>>N;

    VI A(N);
    rep(i, N){
      cin >> A[i];
    }

    map<ll,ll> left,right;

    VI Ans;
    rep(i,N){
      {
        ll a = A[i];
        left[a]++;
      }
      {
        ll a = A[N-1-i];
        right[a]++;
      }
      if(left==right){
        Ans.push_back(i+1);
      }
    }
    print_vector(Ans);
    
    return 0;
}

ACPC2021 day1, day2, day3 解説リンク

day1 農工

day2 会津

day3 北海道

Twitter

  • 検索で「ACPC2021 day1」「#ACPC2021day1」などで検索すると色々な人の解法が見つかる