0 はじめに

0-1 記事について

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

1 ABC272 解説

1-1 個人的な感想

情けない回です。19分でDまで来たのにギリギリEを通せませんでした
DiffはAが灰前半、B,Cが灰後半、Dが緑前半、Eが水後半、Fが黄といった感じです。
Eがとにかく悔やまれます。ほぼぼ実装出来ていたんですけどね...

1-2 A問題 Integer Sum

問題

$N$項の数列$A$が与えられるので$A$の総和を求めて下さい。

制約

・$1 \leq N \leq 100$
・$1 \leq A_i \leq 1000$

解説

入力を受け取って足していくだけでよいです。

Pythonでの実装例

N=int(input())
print(sum(list(map(int,input().split()))))

)の個数でバグらせないようにしましょう。

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;
  int ans=0;
  rep(i,0,N){
    int a; cin>>a;
    ans+=a;
  }
  cout<<ans<<endl;
}

C++で実装する時でも、$A_i$の大きさは大したことないのでint型で大丈夫です。

Pythonだとfor文は必要ないですし、sumが標準ライブラリにあるので短く書けます。

1-3 B問題 Everyone is Friends

問題

$N$人の人がいます。
$M$回の舞踏会が行われ、$i$回目の舞踏会には$k_i$人が参加し、人$x_{i,j}$が参加しました。
どの$2$人の組も、少なくとも$1$回は同じ舞踏会に出ているか判定して下さい。

制約

・$2 \leq N \leq 100$
・$1 \leq M \leq 100$
・$2 \leq k_i \leq N$
・$1 \leq x_1 \leq x_2 \leq ... \leq x_{k_i} \leq N$

解説

あり得る全ての$2$人の組を全探索し、その組について同じ舞踏会に出たことがあるか判定します。その中で、一度も同じ舞踏会に出たことのない組が存在すればNo、そうでなければYesです。
判定には集合を扱う型(Pythonならset、C++ならunordered_set)を使いましょう。
計算量は$O(N^2 M)$です。

Pythonでの実装例

N,M=map(int,input().split())

X=[]
for i in range(M):
  k,*x=list(map(int,input().split()))
  X.append(set(x))

for i in range(N):
  for j in range(N):
    fl=0
    for k in range(M):
      if i+1 in X[k] and j+1 in X[k]:
        fl=1
    if not fl:
      print("No")
      exit()
print("Yes")

*は便利です。

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<set<int>> X(M);
  rep(i,0,M){
    int k; cin>>k;
    rep(j,0,k){
      int x; cin>>x;
      X[i].insert(x);
    }
  }
  
  rep(i,0,N){
    rep(j,0,N){
      bool fl=false;
      rep(k,0,M){
        if(X[k].count(i+1)>0 and X[k].count(j+1)>0){
          fl=true;
        }
      }
      if(!fl){
        cout<<"No"<<endl;
        return 0;
      }
    }
  }
  cout<<"Yes"<<endl;
}

Pythonの`set`、C++での`unordered_set`は、要素の所属判定が$O(1)$でできるので覚えておきましょう。

1-4 C問題 Max Even

問題

長さ$N$の非負整数列$A$が与えられます。
$A$の異なる$2$要素の和としてあり得るものに偶数が存在するか判定し、存在するならその中で最大のものを求めて下さい。

制約

・$2 \leq N \leq 2×10^5$
・$0 \leq A_i \leq 10^9$
・$A$の要素は相異なる

解説

愚直に$2$数の組を全探索すると$O(N^2)$となって間に合いません。
工夫しましょう。

まず、$2$つの整数$N,M$が存在して、$N+M$が偶数であるならば$N,M$の偶奇は一致します。
なので、$A$の異なる$2$要素の和としてあり得るものに偶数が存在するならば、$A$を偶数列$B$と奇数列$C$に分けた時に、$B$か$C$どちらかの長さはが$2$以上であることになります。
又、存在する時、そのような数の最大値は、$B$と$C$それぞれについて大きいものから$2$つの和のうち大きい方です。

これを実装すればよいです。
$A$を偶奇で$B$と$C$に分けるのは$O(N)$で、あり得る最大を求めるのにはソートが必要なので$O(N log N)$となります。
全体の計算量は$O(N log N)$で間に合います。

$B$,$C$に分けるのではなく、一つの二次元配列とした方が実装しやすそうです。

Pythonでの実装例

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

L=[[] for _ in range(2)]
for n in A:
  L[n%2].append(n)

ans=-1
for i in range(2):
  if len(L[i])>=2:
    L[i].sort()
    ans=max(L[i][-1]+L[i][-2],ans)
print(ans)

C++での実装例

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

template <typename T>
T chmax(T &x, const T& y){
  if(x<y){x=y; return true;}
  return false;
}

int main(){
  int N; cin>>N;
  vector<vector<int>> L(2);
  rep(i,0,N){
    int a; cin>>a;
    L[a%2].push_back(a);
  }
  
  int ans=-1;
  rep(i,0,2){
    if(L[i].size()>=2){
      sort(L[i].rbegin(),L[i].rend());
      chmax(ans,L[i][0]+L[i][1]);
    }
  }
  cout<<ans<<endl;
}

1-5 D問題 Root M Leaper

問題

座標上に$N×N$のマス目があります。
最初にマス$(1,1)$に駒が置いてあります。次の操作を何度でも行えます。

・駒の置かれている場所から丁度$\sqrt{M}$離れた格子点へ駒を移動させる。

ここで、$(i,j),(k,l)$間の距離は$\sqrt{(i-k)^2+(j-l)^2}$であるとします。
全てのマス$(i,j)$について、次の問題を解いてください。

・$(1,1)$から$(i,j)$まで駒を移動させるのに必要な操作の回数を求めて下さい。
尚到達不可能である場合はそれを報告して下さい。

制約

・$1 \leq N \leq 400$
・$1 \leq M \leq 10^6$

解説

「問題」はBFSで解けますが、一回を解くのに最低でも$O(N^2)$掛かるので、$N^2$個のマス
それぞれについて問題を解くと$O(N^4)$となり間に合わなさそうです。

ここで、マス$(a,b)$から一回の操作で移動させることができるマスを計算することを考えます。
問題の指定より、$\sqrt{i^2+j^2}=\sqrt{M}$、即ち${i^2+j^2=M}$であれば一回の操作で$(a,b)$から$(a+i,b+j)$へ移動させられます。
各$i,j$は整数なので、$i$でfor文を回して、${i^2+j^2=M}$なる整数$j$が存在するか判定すればよいです。これは$O(1)$でできます。
$M$の制約より、この計算は$O(M)$で行えます。

一回の操作でどこへ移動させられるかわかったので、その移動を用いてそれぞれのマスへの最短距離を求めます。
先程求めたものを使って、始点を$(1,1)$としたBFSをするとよいです。$N^2$個の全てのマスへの最短距離がわかります。

今回はマスの数は$N^2$で、移動先は大して多くありません。${i^2+j^2=M}$より、$O(\sqrt{M})$に比例する量でしょう。
ですからこの問題の計算量は$O(N^2 \sqrt{M})$で間に合います。

移動先を求める際には、$i,j > 0$と限定しておいてから求め、$(i,j),(i,-j),(-i,j),(-i,-j)$を登録すると楽です。

Pythonでの実装例

from collections import deque

N,M=map(int,input().split())

able=[]
for i in range(M+1):
  n=M-i**2
  if n<0:
    break
  n=n**0.5
  if int(n)==n:
    n=int(n)
    able.append([i,n])
    able.append([i,-n])
    able.append([-i,n])
    able.append([-i,-n])

D=deque(); D.append([0,0])
dist=[[-1]*N for _ in range(N)]; dist[0][0]=0
ok=lambda x,y:0<=x<N and 0<=y<N and dist[x][y]==-1
while D:
  x,y=D.popleft()
  for a,b in able:
    nx,ny=x+a,y+b
    if not ok(nx,ny):
      continue
    dist[nx][ny]=dist[x][y]+1
    D.append([nx,ny])

for n in dist:
  print(*n,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<pair<int,int>> able;
  vector<int> pm={1,-1};
  rep(i,0,M+1){
    int n=M-i*i;
    if(n<0){
      break;
    }
    int m=sqrt(n);
    if(m*m==n){
      rep(a,0,2) rep(b,0,2){
        able.push_back(make_pair(i*pm[a],m*pm[b]));
      }
    }
  }
  
  deque<pair<int,int>> D; D.push_back(make_pair(0,0));
  vector<vector<int>> dist(N,vector<int>(N,-1)); dist[0][0]=0;
  while(!D.empty()){
    int x,y; tie(x,y)=D.front(); D.pop_front();
    for(auto [a,b]:able){
      int nx=x+a,ny=y+b;
      if(!(0<=nx and nx<N and 0<=ny and ny<N and dist[nx][ny]==-1)){
        continue;
      }
      dist[nx][ny]=dist[x][y]+1;
      D.push_back(make_pair(nx,ny));
    }
  }
  
  rep(i,0,N){
    rep(j,0,N){
      cout<<dist[i][j];
      if(j==N-1){
        cout<<endl;
      }else{
        cout<<" ";
      }
    }
  }
}

今回は、一回で移動できるマスの数・方向がそれぞれの移動で等しいので、それを先に計算しておくことで計算量を落とせました。

1-6 E問題 Add and Mex

問題

長さ$N$の整数列$A$が与えられます。
次の操作を$M$回行ってください。

・全ての$i$について、$A_i$に$i$を加算する。$A$のmexを求める。

尚、数列のmexとはその数列に含まれない最小の非負整数です。

制約

・$1 \leq N,M \leq 2×10^5$
・$1 \leq A_i \leq 10^9$

解説

mex

最初にmexについて触れておきましょう。
問題文にもあるように、mexは、与えられた整数列に含まれない最小の非負正数です。
例えば、$[0,1,2,4]$のmexは$3$、$[1,2,4]$のmexは$0$です。
少し考えれば分かりますが、与えられた整数列の長さを$n$として、その整数列のmexは$0$以上$n$以下にしかなりません。
ですからmexの値は、$0$から$n$までfor文を回して存在を確認することで$O(n)$で求められます。
以下にmexを求めるプログラムを貼っておきます。稀に使うことがあるのでライブラリに貼っておいても良いでしょう。

mexをPythonで求める

def mex(L):
  N=len(L)
  s=set(L)
  for i in range(N+1):
    if i not in s:
      return i

mexをC++で求める

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

int mex(vector<int> L){
  int N=L.size();
  unordered_set<int> S;
  for(auto i:L) S.insert(i);
  rep(i,0,N+1){
    if(!S.count(i)){
      return i;
    }
  }
}

本題

本題に戻ります。
愚直に指定された操作を$M$回行うとすると、各操作に$O(N)$掛かる為、全体の計算量は$O(NM)$となり間に合いません。
どうすればよいでしょうか。

具体的な例で考えてみましょう。ここでは入力例2を使います。
$A_i$と操作回数を表にしたものです。

冒頭に話した通り、mexの値は、数列の長さを$n$として$0$以上$n$以下にしかなり得ませんから、数列から、$0$以上$n$以下でない要素は取り払っても結果は変わりません。

この場合でも、数列の長さは$N$なので、mexを求める為には、見る数は$0$以上$N$以下の要素だけで十分です。

実際に、$0$以上$N$以下のものだけに色を付けてみましょう。

左から右にかけて、見るべき数が減っています。
$i$列目の見るべき数は多くとも$\lfloor {\tfrac{N}{i}} \rfloor $個(正確には$\lfloor {\tfrac{N+1}{i}} \rfloor $)です。
考えればわかりますが、公差が$i$の等差数列で、$0$以上$N$以下の要素がいくつ存在し得るかと言われれば$\lfloor {\tfrac{N}{i}} \rfloor $個ですよね。

ですから、合計で見るべき数は多くても$N log_2 N$個程度です。

なんで? なんで合計にlog出てくんの??

次のような式変形をすることで$N log_2 N$が導き出せます。

$ \tfrac{1}{1} +\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{4}+\tfrac{1}{5}+\tfrac{1}{6}+\tfrac{1}{7}+\tfrac{1}{8}+...$
$ \leq \tfrac{1}{1} +\tfrac{1}{2}+\tfrac{1}{2}+\tfrac{1}{4}+\tfrac{1}{4}+\tfrac{1}{4}+\tfrac{1}{4}+\tfrac{1}{8}+...$
$ = 1 + 1 + 1 + ...$

少し考えればわかりますが、最後の式に並ぶ$1$の数は$ \lfloor {log_2 N} \rfloor$となります。
ですから、最初の式$ \tfrac{1}{1} +\tfrac{1}{2}+\tfrac{1}{3}+\tfrac{1}{4}+\tfrac{1}{5}+\tfrac{1}{6}+\tfrac{1}{7}+\tfrac{1}{8}+...+\tfrac{1}{N}$は$log_2 N$より小さいです。

よって、今求めるべき、$\lfloor {\tfrac{N}{1}} \rfloor +\lfloor {\tfrac{N}{2}} \rfloor +\lfloor {\tfrac{N}{3}} \rfloor +\lfloor {\tfrac{N}{4}} \rfloor ...\lfloor {\tfrac{N}{N}} \rfloor $は、明らかに$N log_2 N$よりも小さいです。

グラフで見てみても実際にそうなることがわかります。(青い方が$N log_2 N$です)

見るべき数の総数が$N log_2 N$となるので、見るべき数だけを取得して、そこから操作回数が$j$の時のmexをそれぞれ求めるという風にしても間に合います。
mexは、数列の大きさを$n$として$O(n)$で求められるので、mexの部分の計算量は$O(N log N)$となります。

見るべき数の取得は、各$A_i$について、次の計算ができればよいです。

・$A_i$が$0$以上となる最小の操作回数($0$以上$M$以下)
・$A_i$が$N$以下となる最大の操作回数($0$以上$M$以下)

これは割り算で求められます。
求めたら、それをfor文で回します。
前述の通り、見るべき数は合計で$N log_2 N$より小さいのでこの部分の計算量は$O(N log N)$となります。

よって全体の計算量は$O(N log N)$となり、間に合います。

これを実装すればよいです。
操作回数が$j$回の時に作られうる$0$以上$N$以下の数を収納する配列を作ると楽です。(実装例では$L$としています)

Pythonでの実装例

def mex(L):
  N=len(L)
  s=set(L)
  for i in range(N+2):
    if i not in s:
      return i

def divceil(x,y):
  return (x+y-1)//y
    
N,M=map(int,input().split())
A=list(map(int,input().split()))

L=[[] for _ in range(M+1)]
for i in range(N):
  l,r=0,0
  if A[i]<0:
    l=divceil(-A[i],i+1)
  else:
    l=1
  r=min(M+1,divceil(N-A[i],i+1))
  for j in range(l,r):
    num=j*(i+1)+A[i]
    L[j].append(num)

for i in range(1,M+1):
  print(mex(L[i]))

C++での実装例

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

int mex(vector<int> L){
  int N=L.size();
  unordered_set<int> S;
  for(auto i:L) S.insert(i);
  rep(i,0,N+1){
    if(!S.count(i)){
      return i;
    }
  }
}

int divceil(int x,int y){
  return (x+y-1)/y;
}

int main(){
  int N,M; cin>>N>>M;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  vector<vector<int>> L(M+1);
  rep(i,0,N){
    int l,r;
    if(A[i]<0){
      l=divceil(-A[i],i+1);
    }else{
      l=1;
    }
    r=min(M+1,divceil(N-A[i],i+1));
    rep(j,l,r){
      int num=j*(i+1)+A[i];
      L[j].push_back(num);
    }
  }
  
  rep(i,1,M+1){
    cout<<mex(L[i])<<endl;
  }
}

unordered_setの計算量が不安定らしいです。
そして実行速度が何故かPyPyより遅かったです。
詳しい方教えて下さい..お願いします

割り算の部分の実装が割と難しいです。 $1$から$N$の逆数の総和(調和級数といいます)は$O(log N)$、というのは稀に出て来るので覚えておきましょう。

合計で$O(N log N)$個であることに気付いたのに、最後にmexの計算量も$O(N log N)$となるのには気付かず沼り続けて結局解けませんでした。
水Diffだったので解きたかったですが...

2 さいごに

最後までお読み頂きありがとうございます。
A,B,Cまで灰Diffで、Dも緑Diffだったので早解きな部分もありましたが、面白い回だったと思います。
特に、Dの「先に移動先を計算しておく」というのは重要なテクニックなので覚えておきましょう。
話は変わりますが、unordered_setの計算量がよくわからないので詳しい方はコメント欄よりご教示下されば幸いです。
以上です。
よい競プロライフを!!
~~いいね下さい...(切実)~~