# パソコン甲子園 2023 解答

PCK2023 の問題 1~6 までの予想解法を書きました

問題文はチラ見しただけですし提出もしていないのでもしかすると色々と間違えているかもしれません...

## 問題 1

入力された友達の人数+自分でキャンディの数を割ったときのあまりを出力すれば良い

#include<bits/stdc++.h>
using namespace std;
int main(){
    //友達がN人、キャンディがC個ある時
    int N,C;
    cin>>N>>C;
    cout<<C%(N+1)<<endl;
    return 0;
}

## 問題 2

この問題文の的はマンハッタン距離での円であるので abs(x+y)<=d という条件を満たせば Yes である

#include<bits/stdc++.h>
using namespace std;
int main(){
    int x,y,d;
    cin>>d>>x>>y;
    if(abs(x+y)<=d)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

## 問題 3

自分の番号を 2 で割って小数点以下を切り捨てれば自分の親になる

なので番号が 1 になるまで 2 で割っていきながら出力していけば良い

#include<bits/stdc++.h>
using namespace std;
int main(){
    int b;
    cin>>b;
    while(b>1){
        cout<<b<<endl;
        b/=2;
    }
    cout<<1<<endl;
    return 0;
}

## 問題 4

正方形であると判定するためには

- 各辺の長さが同じある
- 対角線の長さが同じである

この２つの条件を判定すれば良い

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
//2点a,b間の距離の2乗を返す
ll dist(pair<ll,ll> a,pair<ll,ll> b){
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}
int main(){
    vector<pair<ll,ll>> v(4);
    for(int i=0;i<4;i++){
        cin>>v[i].first>>v[i].second;
    }
    set<ll> st;
    bool isok=false;
    // 各辺の長さ
    for(int i=0;i<4;i++){
        st.insert(dist(v[i%4],v[(i+1)%4]));
    }
    // 対角線の長さ
    isok = dist(v[0],v[2]) == dist(v[1],v[3]);
    //すべての辺の長さが等しいかつ対角線の長さも等しければ正方形
    cout<<((st.size()==1&&isok)?"Yes":"No")<<endl;
    return 0;
}

## 問題 5

素因数分解をして $p\times p \times q$の形になっているかを判定する

ただし素因数分解をする数が大きすぎるため、高速素因数分解ではなく、普通の素因数分解をすること

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    int cnt=0;//素因数の個数
    map<int,int> mp;//各素因数の数
    int X=N;
    //素因数分解
    for(int i=2;i*i<=N;i++){
        while(X%i==0){
            cnt++;
            mp[i]++;
            X/=i;
        }
    }
    //もし素因数の個数が3個かつ素因数の種類が2種類ならYes
    if(cnt==3&&mp.size()==2){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
    return 0;
}

## 問題 6

$H\times W \times 3$の 3 次元配列を用意する(ここでは num とする)

移動した回数を t とすると

num[i][j][t%3] = 上から i 行目、左から j 列目のマスに t 回目の手拍子のときにたどり着いたときの最小の移動回数

という条件で BFS を使って配列を更新していく

計算量は$O(HW)$

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
vector<ll> dx = {-1,0,1,0},dy = {0,1,0,-1};
int main(){
    int H,W;
    cin>>H>>W;
    map<tuple<ll,ll,ll,ll>,ll> mp;
    vector<vector<ll>> row(H,vector<ll>(W-1,0)),col(W,vector<ll>(H-1,0));
    for(int i=0;i<H;i++){
        for(int j=0;j<W-1;j++){
            cin>>row[i][j],row[i][j]--;
            mp[{i,j,i,j+1}] = row[i][j];
            mp[{i,j+1,i,j}] = row[i][j];
        }
    }
    for(int i=0;i<W;i++){
        for(int j=0;j<H-1;j++){
            cin>>col[i][j],col[i][j]--;
            mp[{i,j,i+1,j}] = col[i][j];
            mp[{i+1,j,i,j}] = col[i][j];
        }
    }
    vector<vector<vector<ll>>> num(H,vector<vector<ll>>(W,vector<ll>(3,-1)));
    queue<tuple<ll,ll,ll>> q;
    q.push({0,0,0});
    num[0][0][0]=0;
    while(!q.empty()){
        auto now = q.front();
        q.pop();
        ll x = get<1>(now),y = get<0>(now),t = get<2>(now);
        for(int i=0;i<4;i++){
            if(x+dx[i]<0||x+dx[i]>=W||y+dy[i]<0||y+dy[i]>=H)continue;
            //まだ探索していない且つ扉があいていれば探索する
            if(num[y+dy[i]][x+dx[i]][(t+1)%3]==-1&&mp[{y,x,y+dy[i],x+dx[i]}]==t%3){
                num[y+dy[i]][x+dx[i]][(t+1)%3] = num[y][x][t%3]+1;
                q.push({y+dy[i],x+dx[i],(t+1)%3});
            }
        }
    }
    ll ans=1e17;
    for(int i=0;i<3;i++){
        if(num[H-1][W-1][i] != -1){
            ans = min(ans,num[H-1][W-1][i]);
        }
    }
    if(ans == 1e17){
        cout<<-1<<endl;
    }else{
        cout<<ans<<endl;
    }
    return 0;
}