0 はじめに

0-1 記事について

AtCoder Beginner Contest 276の解説です。
実装はPythonとC++で書きます。
公式解説と違いがあるかも知れませんがご了承。
ミス等発見されましたらコメント欄にお願いします。

1 ABC276 解説

1-1 個人的な感想

今回もFを通せませんでした。
Diffは、Aが灰前半、Bが灰後半、Cが灰茶中間、Dが茶後半、Eが緑後半、Fが水後半と言った感じです。
先週と似てませんか？私はそう思います。
いい加減水後半を通したいです。

1-2 A問題 Rightmost

問題

英小文字列$S$が与えられます。
$S$に含まれるaのうち最も右にあるものが$S$の左から何番目かを求めて下さい。
尚、$S$にaが含まれない場合は-1を出力して下さい。

制約

・$1 \leq |S| \leq 100$

解説

Sについてfor文を回し、今見ている文字がaならば答えを更新する、という操作を実装すれば解けます。
一回も更新されなかったならば-1を、そうでないならその答えを出力すればよいです。

出力の際は1-indexedにするのを忘れずに。

Pythonでの実装例

S=input()

ans=-1
for i in range(len(S)):
  if S[i]=="a":
    ans=i+1
print(ans)

PythonのS.index(n)は、Sに含まれるnのうち最初のもののindexを返すので注意しましょう。
(文字列を反転させれば使えないことはないですが..)

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  string S; cin>>S;
  int l=S.size();
  
  int ans=-1;
  rep(i,0,l){
    if(S[i]=='a'){
      ans=i+1;
    }
  }
  cout<<ans<<endl;
}

1-3 B問題 Adjacency List

問題

$1,2,...,N$と番号の付いた$N$個の都市と、それらを結ぶ$M$本の道があります。
$i$本目の道は都市$A_i,B_i$を結び、$A_i,B_i$は相互に行き来できます。
$k(1 \leq k \leq N)$について次を出力して下さい。

都市$k$と直接繋がっている都市の個数$d_k$と、そのような都市の番号を昇順に並べた数列$a_k$

制約

・$2 \leq N \leq 10^5$
・$1 \leq M \leq 10^5$
・$1 \leq A_i < B_i \leq N$
・$(A_i,B_i)$は相異なる

解説

都市$i$について直接繋がっている都市を格納する配列$L_i$を用意し、入力の際にそれにメモをしていけばよいです。$L$は二次元配列にしましょう。
入力が終わったら、ソートして出力すればよいです。

Pythonでの実装例

N,M=map(int,input().split())
L=[[] for _ in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  L[a].append(b); L[b].append(a)

for i in range(N):
  print(len(L[i+1]),*sorted(L[i+1]),sep=" ")

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  int N,M; cin>>N>>M;
  vector<vector<int>> L(N+1);
  rep(i,0,M){
    int a,b; cin>>a>>b;
    L[a].push_back(b); L[b].push_back(a);
  }
  
  rep(i,1,N+1){
    int n=L[i].size();
    cout<<n<<" ";
    sort(L[i].begin(),L[i].end());
    rep(j,0,n){
      cout<<L[i][j];
      if(j!=n-1){
        cout<<" ";
      }else{
        cout<<endl;
      }
    }
  }
}

このように、頂点$i$と接続する頂点を格納する二次元配列でグラフを表すことを隣接行列表現といいます。
グラフ系の問題の殆どの入力はこれなので覚えておきましょう。

1-4 C問題 Previous Permutation

問題

$(1,2,...,N)$の順列$P$が与えられます。
$(1,2,...,N)$の順列を辞書順に全て並べた時、$P$の前に来る順列を出力して下さい。
尚、$(1,2,...,N)$の順列のうち、$P$より辞書順で前に位置する順列が存在することが保証されます。

制約

・$1 \leq N \leq 100$

解説

愚直に$(1,2,...,N)$の順列を列挙するのは$O(N!)$掛かり、今回の制約では無謀です。
与えられる順列$P$から、求めるべき順列$Q$を割り出す方法を考えます。

$P$を並べ替えて$Q$を作ることを考えます。
$P$の左の方の変化は最小限にした方がよいです。
変える部分を右から$n$項とすると、$P$の右から$n$項が単調増加となっている場合に限り、$P$の右から$n$項を変える必要があります。
例として入出力例2を挙げると、$A=(9,8,6,5,10,3,1,2,4,7)$の一つ前の順列は$B=(9,8,6,5,10,2,7,4,3,1)$です。
$(1,2,4,7)$は単調増加なので並べ替えてもこれ以上辞書順で小さくできませんが、$(3,1,2,4,7)$まで見ると単調増加ではないので、$(2,7,4,3,1)$のように辞書順で小さくできます。

そして、上の図のように、$P$の右から$n$項のうち最も左の$3$は、$(1,2,3,4,7)$の中で$3$の次に小さい$2$に変わり、単調増加となっている部分は単調減少となっています。。

つまり、これを実装すればよいです。
①$A$の右から$i$項が単調増加となっている、最大の$i$を探し$n$とする。
②$A$の右から$n$項の中で$A$の右から$n$項目の次に小さい数を探し、そのインデックスを$m$とする。
③$A$の右から$n$項目と$A_m$を交換し、右から$n-1$項を反転させる。

これらの操作は全て$O(N)$で行えるので、全体の計算量は$O(N log N)$となり間に合います。

「右から$i$項」とすると実装が複雑になるので「左から$i$項」に言い換えて実装すると楽です。

Pythonでの実装例

N=int(input())
P=list(map(int,input().split()))

n=N-2 #P[n]より右は単調増加
while P[n]<P[n+1]:
  n-=1

m=N-1 #P[n]より右にある、P[n]未満の最小
while P[n]<P[m]: 
  m-=1

P[n],P[m]=P[m],P[n] #P[n],P[m]を交換
ans=P[:n+1]+P[n+1:][::-1] #P[n]より左はそのまま、P[n]以右は反転させる
print(*ans)

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  int N; cin>>N;
  vector<int> P(N);
  rep(i,0,N) cin>>P[i];
  
  int n=N-2;
  while(P[n]<P[n+1]){
    n--;
  }
  
  int m=N-1;
  while(P[n]<P[m]){
    m--;
  }
  
  swap(P[n],P[m]);
  reverse(P.begin()+n+1,P.end());
  rep(i,0,N){
    cout<<P[i];
    if(i==N-1){
      cout<<endl;
    }else{
      cout<<" ";
    }
  }
}

公式解説の完全下位互換になってしまった...

ちなみに

C++には、prev_permutationという、辞書順で一つ前の順列を返すチートのような関数が標準ライブラリにあるそうです。怒りますよ。

C++での実装例(`prev_permutation`)

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  int N; cin>>N;
  vector<int> P(N);
  rep(i,0,N) cin>>P[i];
  
  prev_permutation(P.begin(),P.end());
  rep(i,0,N){
    cout<<P[i];
    if(i==N-1){
      cout<<endl;
    }else{
      cout<<" ";
    }
  }
}

1-5 D問題 Divide by 2 or 3

問題

長さ$N$の整数列$A$が与えられます。
あなたは次の操作を何回でも行えます。

①$2$の倍数である$A_i$を一つ選び、$\tfrac {A_i}{2}$で置き換える。
②$3$の倍数である$A_i$を一つ選び、$\tfrac {A_i}{3}$で置き換える。

この操作で、$A$の要素を全て等しくしたいです。
その為に必要な操作回数の最小を求めて下さい。

制約

解説

$A$を全て等しくした時、$A_i$の値は$A$の公約数です。
そして、操作回数が最小となるように操作すると$A_i$は$A$の最大公約数となります。

従って、次の実装をすればよいです。
①$A$の最大公約数$g$を求める。
②各$\tfrac{A_i}{g}$について、何回$2$か$3$で割れば$1$にできるか求める。この値の総和が答え。$1$にできないものが一つでも存在すれば答えは$-1$。

①の部分の計算量は$O(N \log \max A)$です。

最大公約数の計算量

ここでは、$2$自然数$A,B$の最大公約数を求める計算量について解説します。
現在知られている中で最も効率的な、最大公約数を求める方法はユークリッドの互除法です。
ユークリッドの互除法を行っていくと、2数$A,B$は指数関数的に小さくなっていきます。
$2$回互除法のステップを行った時、$A,B$は必ず半分以下となっています。
よって計算量は$O(\log \min (A,B))$です。

②の部分は、各$\tfrac{A_i}{g}$について$2$か$3$で割るので$O(N \log \max A)$です。

従って、全体の計算量は$O(N \log \max A)$で間に合います。

Pythonでの実装例

from math import gcd

N=int(input())
A=list(map(int,input().split()))

g=0
for i in range(N):
  g=gcd(g,A[i])

ans=0
for i in range(N):
  now=A[i]//g
  while now%2==0:
    now//=2
    ans+=1
  while now%3==0:
    now//=3
    ans+=1
  if now!=1:
    print(-1); exit()
print(ans)

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int main(){
  int N; cin>>N;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  int g=0;
  rep(i,0,N){
    g=gcd(g,A[i]);
  }
  
  int ans=0;
  rep(i,0,N){
    int now=A[i]/g;
    while(now%2==0){
      now/=2; ans++;
    }
    while(now%3==0){
      now/=3; ans++;
    }
    if(now!=1){
      cout<<-1<<endl; return 0;
    }
  }
  cout<<ans<<endl;
}

1-6 E問題 Round Trip

問題

$H×W$のマス目があり、上から$i$行目で左から$j$列目にあるマスを$(i,j)$と表します。
各マスは始点(S)か道(.)か障害物(#)のいずれかで、障害物のあるマスには行けません。
始点からスタートし、道のマスを上下左右に進み、また始点に帰ってくる、長さが$4$以上の経路のうち最初と最後以外に同じマスを通らないものが存在するか判定して下さい。

制約

・$2 \leq H,W $
・$4 \leq H×W \leq 10^6$

解説

まず「経路」について考えてみましょう。
経路は始点→始点と隣接する道$A$→始点に隣接する道$B$→始点に戻るというものです。
ここで、始点に隣接する任意の道$A,B$について、$A,B$が始点以外を通じて行き来できるならば、必ず長さが$4$以上の経路が存在します。

証明

「始点→始点と隣接する道$A$」と「始点と隣接する道$B$→始点」は共に長さ$1$です。
そして、始点と隣接する任意の道$A,B$は、$A$から$B$へ行けるならばその距離は必ず$2$以上あります。$A,B$が隣接することはあり得ないからです。
従って、「経路」の長さは$1+1+2=4$以上あります。

これを使えば簡単に判定問題を解くことが出来ます。

$(A,B)$としてあり得る全ての道の組(最大$6$つ)について、$A$と$B$が始点以外を通じて行き来でいるかを判定すればよく、これにはUnionFindやBFSを使って答えられます。

計算量は、BFSの場合$O(HW)$、UnionFindの場合も基本的にクエリを$O(1)$で処理できるので$O(HW)$で間に合います。。

実装はBFSで行います。

Pythonでの実装例

from collections import deque

H,W=map(int,input().split())
C=[list(input()) for _ in range(H)]

sx,sy=0,0
for i in range(H):
  for j in range(W):
    if C[i][j]=="S":
      sx,sy=i,j

dir=[[0,-1],[0,1],[-1,0],[1,0]]
ok=lambda x,y:0<=x<H and 0<=y<W and C[x][y]=="."

def BFS(X,Y):
  D=deque(); D.append((X,Y))
  dist=[[-1]*W for _ in range(H)]; dist[X][Y]=0
  while D:
    x,y=D.popleft()
    for a,b in dir:
      nx,ny=x+a,y+b
      if not (ok(nx,ny) and dist[nx][ny]==-1): continue
      dist[nx][ny]=dist[x][y]+1
      D.append((nx,ny))
  return dist

l=[]
for a,b in dir:
  x,y=sx+a,sy+b
  if ok(x,y):
    l.append((x,y))

for i in range(len(l)):
  x,y=l[i]
  dist=BFS(x,y)
  for j in range(i+1,len(l)):
    nx,ny=l[j]
    if dist[nx][ny]!=-1:
      print("Yes")
      exit()
print("No")

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N,M) for(int i=N; i<M; i++)

int H,W;
vector<string> C(1000000);
vector<pair<int,int>> dir={{0,-1},{0,1},{-1,0},{1,0}};

bool ok(int x,int y){
  return 0<=x and x<H and 0<=y and y<W and C[x][y]=='.';
}

vector<vector<int>> BFS(int X,int Y){
  deque<pair<int,int>> D; D.push_back(make_pair(X,Y));
  vector<vector<int>> dist(H,vector<int>(W,-1)); dist[X][Y]=0;
  
  while(!D.empty()){
    int x,y; tie(x,y)=D.front(); D.pop_front();
    rep(i,0,4){
      int a,b; tie(a,b)=dir[i];
      int nx=x+a,ny=y+b;
      if(ok(nx,ny) and dist[nx][ny]==-1){
        dist[nx][ny]=dist[x][y]+1;
        D.push_back(make_pair(nx,ny));
      }
    }
  }
  return dist;
}

int main(){
  cin>>H>>W;
  int sx=0,sy=0;
  rep(i,0,H){
    cin>>C[i];
    rep(j,0,W){
      if(C[i][j]=='S'){
        sx=i; sy=j;
      }
    }
  }
  
  vector<pair<int,int>> l;
  rep(i,0,4){
    int a,b; tie(a,b)=dir[i];
    int nx=sx+a,ny=sy+b;
    if(ok(nx,ny)){
      l.push_back(make_pair(nx,ny));
    }
  }
  
  int n=l.size();
  rep(i,0,n){
    int ax,ay; tie(ax,ay)=l[i];
    vector<vector<int>> dist=BFS(ax,ay);
    rep(j,i+1,n){
      int bx,by; tie(bx,by)=l[j];
      if(ok(bx,by) and dist[bx][by]!=-1){
        cout<<"Yes"<<endl; return 0;
      }
    }
  }
  cout<<"No"<<endl;
}

実装大変すぎません？

1-7 F問題 Double Chance

問題

あとで解説かきます。

2 さいごに

最後までお読み頂きありがとうございます。
今回は結構難しい回だったのではないでしょうか。
Cがギリギリ灰Diffなのは驚きました。
以上です。
ありがとうございました。
よい競プロライフを!!
~~いいね下さい...~~