ABC326F問題

Robot Rotation

atcoder.jp

まず、全探索を考えます。
単純なBit全探索だと、入力が最大の時に計算量が2^80になってしまい、間に合わないので工夫する必要があります。

まず、行動をする時に向くことができる方向が右と左の２つだけなので、配列Aのうち、奇数番目の要素はY軸方向、偶数番目の要素はX軸方向にしか関係がないとわかります。

つまり、２つにわけて考えることができるので、ここで計算量が2^40*2になります。

また、例えばY軸に関係する要素も前から全探索するのと後ろから全探索する、の２つにわけると、入力が最大のときでも計算量は2^20*2*2にまで落とすことができます。

このように、うまく工夫して計算量を落とすとACを得ることができます。

(Y軸方向と、X軸方向の２回、Bit全探索を行うので関数にしました）

#include <bits/stdc++.h>
using namespace std;
pair<int,int> rotti(int n,vector<long long>a,long long mokuteki){
  long long count;
  if(n<=20){
    for(int tmp=0;tmp<(1<<n);tmp++){
      bitset<20>s(tmp);
      count=0;
      for(int i=0;i<n;i++){
	if(s[i]==1)count+=a[i];
	else count-=a[i];
      }
      if(count==mokuteki){
	return {tmp,-1};
      }
    }
    return {-1,-1};
  }
  map<long long,int>dict;
  for(int tmp=0;tmp<(1<<20);tmp++){
    bitset<20>s(tmp);
    count=0;
    for(int i=0;i<20;i++){
      if(s[i]==1)count+=a[i];
      else count-=a[i];
    }
    dict[count]=tmp;
  }
  for(int tmp=0;tmp<(1<<(n-20));tmp++){
    bitset<20>s(tmp);
    count=0;
    for(int i=0;i<n-20;i++){
      if(s[i]==1)count+=a[i+20];
      else count-=a[i+20];
    }
    if(dict.count(mokuteki-count)==0)continue;
    return {dict[mokuteki-count],tmp};
  }
  return {-1,-1};
}
int main()
{
  long long n,x,y;
  cin >> n >> x >> y;
  vector<long long>A(n),a,b;
  for(int i=0;i<n;i++)cin >> A[i];
  for(int i=0;i<n;i++){
    if(i%2==0)a.emplace_back(A[i]);
    else b.emplace_back(A[i]);
  }
  //たて
  pair<int,int>tate=rotti(a.size(),a,y);
  if(tate.first==-1){
    cout << "No" << endl;
    return 0;
  }
  vector<int>tate_muki;
  bitset<20>t(tate.first);
  for(int i=0;i<min(int(a.size()),20);i++){
    if(t[i]==1)tate_muki.emplace_back(1);
    else tate_muki.emplace_back(0);
  }
  bitset<20>s(tate.second);
  if(tate.second!=-1){
    for(int i=0;i<a.size()-20;i++){
      if(s[i]==1)tate_muki.emplace_back(1);
      else tate_muki.emplace_back(0);
    }
  }
  pair<int,int>yoko=rotti(b.size(),b,x);
  if(yoko.first==-1){
    cout << "No" << endl;
    return 0;
  }
  bitset<20>ss(yoko.first);
  vector<int>yoko_muki;
  for(int i=0;i<min(int(b.size()),20);i++){
    if(ss[i]==1)yoko_muki.emplace_back(1);
    else yoko_muki.emplace_back(0);
  }
  bitset<20>tt(yoko.second);
  if(yoko.second!=-1){
    for(int i=0;i<b.size()-20;i++){
      if(tt[i]==1)yoko_muki.emplace_back(1);
      else yoko_muki.emplace_back(0);
    }
  }
  char hako='R',muki='R';
  x=0,y=0;
  cout << "Yes" << endl;
  for(int i=0;i<n;i++){
    if(i%2==0){
      if(x==tate_muki.size())break;
      if(muki=='L'){
	if(tate_muki[x]==1)hako='R';
	else hako='L';
      }
      else{
	if(tate_muki[x]==1)hako='L';
	else hako='R';
      }
      if(tate_muki[x]==1)muki='U';
      else muki='D';
      x++;
    }
    else{
      if(y==yoko_muki.size())break;
      if(muki=='U'){
	if(yoko_muki[y]==1)hako='R';
	else hako='L';
      }
      else {
	if(yoko_muki[y]==1)hako='L';
	else hako='R';
      }
      if(yoko_muki[y]==1)muki='R';
      else muki='L';
      y++;
    }
    cout << hako;
  }
  cout << endl;
  return 0;
}

重み付きUnionFind木の実装

重みつきUnionFindは、UnionFind木を理解していればあっという間に実装できます。

と、言うのも、UnionFind木で親をたどっていく操作の途中で、重みも一緒に計算すればいいだけだからです。

ホントにそれだけです。添字がめんどくさいぐらい。

#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
  //配列のでかさは調整
  vector<vector<long long int>>par;
  //int par[1000009];
  int siz[1000009];

  // N 頂点の Union-Find を作成
  void init(int N) {
    for (int i = 1; i <= N+10; i++) par.push_back({-1,0}); // 最初は親が無い
    for (int i = 1; i <= N; i++) siz[i] = 1; // 最初はグループの頂点数が 1
  }

  // 頂点 x の根を返す関数
  int root(int x) {
    while (true) {
      if (par[x][0] == -1) break; // 1 個先（親）がなければ、ここが根
      x = par[x][0]; // 1 個先（親）に進む
    }
    return x;
  }

  // 要素 u と v を統合する関数(v+w==u)
  void unite(int u, int v,int w) {
    int RootU = root(u);
    int RootV = root(v);
    if (RootU == RootV) return; // u と v が同グループのときは処理を行わない
    if (siz[RootU] < siz[RootV]) {
      par[RootU][1] = w+kyori_ne(v)+kyori_ne(u)*-1;
      par[RootU][0] = RootV;
      siz[RootV] = siz[RootU] + siz[RootV];
    }
    else {
      par[RootV][1] = w*-1+kyori_ne(u)+kyori_ne(v)*-1;
      par[RootV][0] = RootU;
      siz[RootU] = siz[RootU] + siz[RootV];
    }
  }

  // 要素 u と v が同一のグループかどうかを返す関数　
  bool same(int u, int v) {
    if (root(u) == root(v)) return true;
    return false;
  }
  //その頂点の根との差を出力
  long long int kyori_ne(int x){
    long long int count=0;
    while(true){
      if(par[x][0]==-1)break;
      count+=par[x][1];
      x=par[x][0];
    }
    return count;
  }

  //v-uを出力
  long long int kyori(int u,int v){
    //もし同一グループでなかったら-1を返す
    if(same(u,v)==false)return -1;
    return kyori_ne(u)-kyori_ne(v);
  }

    
  //要素ｎが属しているグループのデカさ
  int dekasa(int n){
    return siz[root(n)];
  }
  void checker(){
    for (int i=0;i<par.size();i++)cout << par[i][0] << " " << par[i][1] << endl;
  }
};

約数列挙

任意の非負整数Nの約数を求めたい場合、愚直な実装をすると１からNまでの数字すべてがNの約数かどうかを確認することになると思います。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>ans;
  for (int i=1;i<=n;i++)if(n%i==0)ans.emplace_back(i);
  for (int i=0;i<ans.size();i++)cout << ans[i] << endl;
  return 0;
}

となると思います。

しかし、約数が見つかったときに、N//iも約数として列挙するようにすると、計算量√Nで約数をすべて列挙することができます。

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n;
  cin >> n;
  vector<int>ans;
  set<int>irane;
  for (int i=1;i<=int(sqrt(n))+10;i++){
    if(n%i!=0)continue;
    if(irane.count(i)>0)continue;
    ans.emplace_back(i);
    ans.emplace_back(n/i);
    irane.insert(i);
    irane.insert(n/i);
  }
  sort(ans.begin(),ans.end());
  for (int i=0;i<ans.size();i++)cout << ans[i] << endl;
  return 0;
}

set使わない方が良かったな…（あとでカエル）

ABC257F問題

atcoder.jp

４つに場合分けできる
・町１から町Nまで未定のテレポーターを使わないで行く。
・町１から近い未定のテレポーターまで行き、町iから未定のテレポーターを使わないで町Nまでいく。
・町１から町iまで行き、未定のテレポーターにテレポートした後、町Nまで行く
・町１から未定のテレポーターに行き、町iに行く。さらに町iから未定のテレポーターにテレポートし、町Nまで行く。

また、使う未定のテレポーターはそれぞれ町１、町Nから一番近いものを使用する。

双方向からBFSなどを行い、町１からそれぞれの町までの距離、町Nからそれぞれの町までの距離を配列に格納し、町１から一番近い未定のテレポーターまでの距離、町Nから一番近い未定のテレポーターまでの距離を変数などに格納し、この動作を高速に行う。

#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(int n,vector<vector<int>>rotti,int start){
  vector<int>stack{start},amount(n,1000000000);
  int iti=0,hako;
  amount[start-1]=0;
  while (stack.size()>iti){
    hako=stack[iti];
    for (int i=0;i<rotti[hako-1].size();i++){
      if(amount[rotti[hako-1][i]-1]<=amount[hako-1]+1)continue;
      amount[rotti[hako-1][i]-1]=amount[hako-1]+1;
      stack.emplace_back(rotti[hako-1][i]);
    }
    iti++;
  }
  return amount;
}
int main()
{
  int n,m,a,b;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  vector<int>x;
  for (int i=0;i<m;i++){
    cin >> a >> b;
    if(a==0){
      x.emplace_back(b);
      continue;
    }
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  vector<int>amount=bfs(n,rotti,1);
  vector<int>amount2=bfs(n,rotti,n);
  int count=100000000,count2=100000000;
  for (int i=0;i<x.size();i++)count=min(count,amount[x[i]-1]);
  for (int i=0;i<x.size();i++)count2=min(count2,amount2[x[i]-1]);
  for (int i=0;i<n;i++){
    if (min({amount[n-1],count2+1+amount[i],count+1+amount2[i],count2+count+2})>=10000000)cout << -1 << " ";
    else cout << min({amount[n-1],count+1+amount2[i],count2+1+amount[i],count+2+count2}) << " ";
  }
  cout << endl;
  return 0;
}

atcoder.jp

最小全域木の実装

備忘録

最小全域木は、重み付きグラフなどにおいて、連結なグラフにするために最小で重みがいくつになるかです（日本語変かも）。

大きくクラスカル法とプリム法がありますが、ぼくはプリム法の方で実装しました（一般的にはクラスカル法のほうがシンプルなので使われている）。

実装

int purimu(int n,int m,vector<vector<vector<int>>>rotti)
{
  //二次元配列の中身は{行く頂点、距離}
  priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>prq;
  //優先度つきキューの中身は{距離、スタート頂点、ゴール頂点}
  set<int>irane{1};
  for (int i=0;i<rotti[0].size();i++)prq.push({rotti[0][i][1],1,rotti[0][i][0]});
  vector<int>hako;
  int ans=0;
  while (prq.size()>0){
    hako=prq.top();
    prq.pop();
    if (irane.count(hako[2])>0)continue;
    ans+=hako[0];
    irane.insert(hako[2]);
    for (int i=0;i<rotti[hako[2]-1].size();i++)prq.push({rotti[hako[2]-1][i][1],hako[2],rotti[hako[2]-1][i][0]});
  }
  if (irane.size()<n)return -1;
  return ans;
}

頂点の数、辺の数、連結関係と重みを格納した三次元配列を引数とし、最小全域木の重みを返します。
もし、どうやっても連結なグラフにできなかった場合、-1を返します。

プリム法について軽く説明すると

最初にスタートする頂点を決める。
そして、優先度付きキューなどに、その頂点から使える辺の長さなどを格納しておく

そして、以下の動作を優先度付きキューが空になるまで続けます。

優先度付きキューから、今使える中で一番短い辺を選ぶ
もしその辺を追加することによって閉路になってしまうのなら以下の動作をスキップする
・その辺を使うことにする。そして、その結果連結となる頂点から使える辺をまた優先度付きキューに追加する

例えば、以下のような実装で最小全域木の重みを出力することができます。

#include <bits/stdc++.h>
using namespace std;
//最小全域木の重みを返す
int purimu(int n,int m,vector<vector<vector<int>>>rotti)
{
  //二次元配列の中身は{行く頂点、距離}
  priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>>prq;
  //優先度つきキューの中身は{距離、スタート頂点、ゴール頂点}
  set<int>irane{1};
  for (int i=0;i<rotti[0].size();i++)prq.push({rotti[0][i][1],1,rotti[0][i][0]});
  vector<int>hako;
  long long ans=0;
  while (prq.size()>0){
    hako=prq.top();
    prq.pop();
    if (irane.count(hako[2])>0)continue;
    ans+=hako[0];
    irane.insert(hako[2]);
    for (int i=0;i<rotti[hako[2]-1].size();i++)prq.push({rotti[hako[2]-1][i][1],hako[2],rotti[hako[2]-1][i][0]});
  }
  if (irane.size()<n)return -1;
  return ans;
}
int main()
{
  int n,m,a,b,c;
  cin >> n >> m;
  vector<vector<vector<int>>>rotti(n);
  for (int i=0;i<m;i++){
    cin >> a >> b >> c;
    rotti[a-1].push_back({b,c});
    rotti[b-1].push_back({a,c});
  }
  cout << purimu(n,m,rotti) << endl;
  return 0;
}

DFSの実装

DFSは、ある頂点が他の頂点と連結してるかどうかを確認するアルゴリズムです（頂点１からスタートした場合、それぞれの頂点が頂点１と連結かどうか確認できる）。

BFSの下位互換でしかないので、めったに使わないです。

rotti-coder.hatenablog.com

まあ、たまにDFSの考え方を使って理解しやすくなるアルゴリズムだったりはあるけど（lowlinkとか？）

rotti-coder.hatenablog.com

実装

vector<int> dfs(int n,int m,vector<vector<int>>rotti){
  vector<int>stack{1};
  vector<int>num(n,0);
  int check=0,hako;
  num[0]=1;
  while (stack.size()>0){
    hako=stack[stack.size()-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]==1)continue;
      num[rotti[hako-1][i]-1]=1;
      check=1;
      stack.emplace_back(rotti[hako-1][i]);
    }
    if (check==0)stack.pop_back();
  }
  return num;
}

この関数は頂点の数N、辺の数M（いらない）、連結関係を格納した二次元配列を引数とし、１からDFSを初めます。
それぞれの頂点が１と連結してるかどうかを配列（num）に格納し、連結の場合値は１、非連結の場合は0になっています。

例えば、以下のようなコードでそれぞれの頂点が頂点１と連結かどうかを出力することができます。

#include <bits/stdc++.h>
using namespace std;
vector<int> dfs(int n,int m,vector<vector<int>>rotti){
  vector<int>stack{1};
  vector<int>num(n,0);
  int check=0,hako;
  num[0]=1;
  while (stack.size()>0){
    hako=stack[stack.size()-1];
    check=0;
    for (int i=0;i<rotti[hako-1].size();i++){
      if (num[rotti[hako-1][i]-1]==1)continue;
      num[rotti[hako-1][i]-1]=1;
      check=1;
      stack.emplace_back(rotti[hako-1][i]);
    }
    if (check==0)stack.pop_back();
  }
  return num;
}

int main()
{
  int n,m,a,b,hako;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  vector<int>num;
  for (int i=0;i<m;i++){
    cin >> a >> b;
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  num=dfs(n,m,rotti);
  for (int i=0;i<n;i++){
    if (num[i]==1)cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}

BFSの実装

BFSは幅優先探索と言って、まあだいたいグラフが連結かどうかだったり、ある頂点から初めてその頂点には何通りの行き方があるかとか、最小で何手である頂点からある頂点まで行けるかを確かめたりするのに使います（他にもたくさん使いみちあるけど）。

実装

vector<int> bfs(int n,int m,vector<vector<int>>rotti){
  vector<int>amount(n,100000000);
  amount[0]=0;
  vector<int>stack={1};
  int iti=0,hako;
  set<int>irane;
  irane.insert(1);
  while (stack.size()>iti){
    hako=stack[iti];
    for (int i=0;i<rotti[hako-1].size();i++){
      if (irane.count(rotti[hako-1][i])>0)continue;
      if (amount[rotti[hako-1][i]-1]<amount[hako-1]+1)continue;
      stack.emplace_back(rotti[hako-1][i]);
      irane.insert(rotti[hako-1][i]);
      amount[rotti[hako-1][i]-1]=amount[hako-1]+1;
    }
    iti++;
  }
  for (int i=0;i<n;i++)if (amount[i]==100000000)amount[i]=-1;
  return amount;
}

この関数は、頂点の数N、辺の数M（なくてもいいけど）、頂点と頂点の連結関係を表した二次元配列を引数とし、頂点１からそれぞれの頂点への最短移動回数を格納した配列を戻り値とします。

もし、頂点ｘに頂点１から行けることができない場合、値は-1になって帰ってきます。

この関数を使う場合は、例えば以下のようなコードを書くことによって、頂点１からそれぞれの頂点への最短移動回数を出力させることができます。
i行目には頂点１から頂点iまでの最短移動回数が出力されます。

#include <bits/stdc++.h>
using namespace std;
vector<int> bfs(int n,int m,vector<vector<int>>rotti){
  vector<int>amount(n,100000000);
  amount[0]=0;
  vector<int>stack={1};
  int iti=0,hako;
  set<int>irane;
  irane.insert(1);
  while (stack.size()>iti){
    hako=stack[iti];
    for (int i=0;i<rotti[hako-1].size();i++){
      if (irane.count(rotti[hako-1][i])>0)continue;
      if (amount[rotti[hako-1][i]-1]<amount[hako-1]+1)continue;
      stack.emplace_back(rotti[hako-1][i]);
      irane.insert(rotti[hako-1][i]);
      amount[rotti[hako-1][i]-1]=amount[hako-1]+1;
    }
    iti++;
  }
  for (int i=0;i<n;i++)if (amount[i]==100000000)amount[i]=-1;
  return amount;
}
int main()
{
  int n,m,a,b;
  cin >> n >> m;
  vector<vector<int>>rotti(n);
  vector<int>amount;
  for (int i=0;i<m;i++){
    cin >> a >> b;
    rotti[a-1].emplace_back(b);
    rotti[b-1].emplace_back(a);
  }
  amount=bfs(n,m,rotti);
  for (int i=0;i<n;i++)cout << amount[i] << endl;
  return 0;
}