2022年2月10日

はやりの曲っぽいな
ApeX,マッドマギー実装されったぽいな。ウルトがValorantのRazeのブームボットっぽいな

- ABC226 D - Teleportation

[全探索、辞書型配列,比の約分]

各頂点から(自身以外の)各頂点へ、1つの魔法のみを使って移動する
1つの魔法であれば、何回使ってもいい
任意の頂点から、任意の頂点へ、上記のルールで移動するとき、魔法が最小で何種類あればいいかを求める問題

例えば、頂点Aの座標が(1,2)であるとき、A(1,2)のように書きます。超簡単に、A(1,2), B(3,6)の2点だけの場合を考えますか。これはもう、頭使わずに「２」が答えって言えるようにしようね。

A->Bに行くために魔法1種類問題の表記に合わせると、魔法は(2,4)
B->Aに行くために上とは別の魔法を1種類魔法は(-2,-4)

1個目の魔法の2,4それぞれに-1をかけたものが2個目の魔法になってるね

そんなこんなで、次はもう1個座標を追加するよ。

A(1,2), B(3,6), C(7,14)

答えがどうなるかわかるかな？
まあ、答えは「２」なんですよね。

A->Bに行くために魔法1種類問題の表記に合わせると、魔法は(2,4)

B->Aに行くために上とは別の魔法を1種類魔法は(-2,-4)

この、さっきの頂点が2個だけだった場合の魔法だけで移動が可能です。

A -> Cは、魔法(2,4)を3回使えば行けるﾖ
これ、どうやって考えればいいかっていうと、A->Cに行くとき、座標の変化は(7-1, 14-2)で(6,12)なんだけど、これを最大公約数(=6)で割ってあげると(1,2)ってなるんだよね。
(1,2)じゃあピンとこないかもしれないんだけど、そもそもの魔法(2,4)のほうも、最大公約数(=2)で割ると(1,2)になる。
つまり、魔法(1,2)のみを習得してしまえば、魔法(2,4)も魔法(6,12)も習得したも同然ってことになっちゃうんだよね～。お得。
ってなわけで、一般化?した言い方をすると、頂点Aから頂点Bへ移動するとき、その座標の差が(X,Y)であるなら、GCD(X,Y)=Gとして、魔法(X/G, Y/G)を習得するのがお得。
よし解けた。
N=500だから、任意の2頂点に対してx座標とy座標の差(X,Y)を求めて、__GCD(X,Y)でそれぞれを割って、mapに登録してやって、最後にmapに登録されているものの数を答えとして、、、出力すれば間に合う!!
任意の二頂点の選び方がNの2乗、 gcd(x,y)が確か計算量がlog(max(x,y))だから、まあ普通に間に合うっしょ。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
typedef pair<int,int> P;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)

int main()
{
    int n; 
    cin >> n;
    vector<int> x(n), y(n);
    rep(i,n) cin >> x[i] >> y[i];
    map<P,bool> mp;
    rep(i,n){
        rep(j,n){
            if(i == j) continue;
            int x1,x2,y1,y2;
            x1=x[i] - x[j];
            y1=y[i] - y[j];
            // x1-x2, y1-y2 をGCD(正)で割る
            int G = __gcd(x1,y1);
            G=abs(G); //一応明示的に正の値に変換しておく
            x1 /= G;
            y1 /= G;
            mp[P(x1,y1)]=true;
        }
    }
    int ans = 0;
    for(auto x:mp){
        ans++;
    }
    cout << ans << endl;
}

GCDが負の値とるかわからないので明示的に正の値に変換しておきます。

ABC232 C - Graph Isomorphism

[順列全探索,,nextpermutation,頭壊れる]
next permutationっぽいなコレ。こういう問題頭壊れるｯｽﾈ
ただまあ、言ってることは結局…
- 1..Nを並び替えて作れるPを用意する
- 任意の1以上N以下の整数i,jに対して…
  - 高橋側でボールi,jがひもでつながれているとき、青木川でボールPi,Pjがひもでつながれていればおk
なるほどね。これをそのまま実装すればいいんだけど、適当に言い換えると嬉しいかも
- 高橋側でi,jが結ばれているとき、あおきがわでp[i],p[j]のボールをつなぐ辺が存在する
やまあ、特に何も言い換えてないんだけど…。これで何が楽になってほしいかっていうと、1本目の辺が高橋側で(2,3)を結んでいるとき、青木川の1本目が(2,3)じゃなくても、4本目とかで(2,3)を結んでいればokみたいなそういうことが言いたい。(正確にはp[2],p[3])を結んでいればおｋなんだけど、、、ごめんね)

で、あとはPをネクストぱーみゅテーションで結んでやればokっぽいな。
高橋がi,j結んでいるとき、p[i], p[j]を結ぶ辺があるかどうかの判定は、mapでok
マップ大好き
```
#include <bits/stdc++.h>

using namespace std;
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}

int main()
{
    int n,m; cin >> n >> m;
    vector<int> a(m), b(m);
    rep(i,m){
        int x,y;
        cin >> x >> y;
        --x,--y;
        a[i] = x; b[i] = y;
    }
    vector<int> c(m), d(m);
    map<P,bool> mp;
    rep(i,m){
        int x,y;
        cin >> x >> y;
        --x,--y;
        c[i] = x; d[i] = y;
        mp[P(x,y)] = true;
    }
    vector<int> p(n);
    rep(i,n) p[i]=i;
    do {
        bool flag=true;
        rep(i,m){
            int x, y;
            x = a[i]; y = b[i];
            if(mp[P(p[x],p[y])] || mp[P(p[y],p[x])]) continue;
            else flag = false;
        }
        if(flag){
            coY();
            return 0;
        }
    } while(next_permutation(p.begin(),p.end()));
    coN();

}
```
コード

草体にぼ日記

だらだらと

2022年2月10日

2022年2月10日

- ABC226 D - Teleportation

ABC232 C - Graph Isomorphism