ABC278をPythonとC++で

0 はじめに

0-1 記事について

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

1 ABC278 解説

1-1 個人的な感想

苦手な回です。
Diffは、A,Bが灰前半、Cが灰後半、Dが茶前半、Eが緑中間、Fが水後半と言った感じです。
F解けませんでした。かなしい

1-2 A問題 Shift

問題

長さ$N$の整数列$A$があります。
次の操作を丁度$K$回行います。

・$A$の先頭の要素を取り除き、$A$の末尾に$0$を追加する。

操作の後の$A$の要素を全て出力して下さい。

制約

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

解説

問題の指示通りに愚直にシミュレーションをしてもよいです。
$A$を配列として受け取り、$K$回「$A_0$を削除して$0$を末尾に追加する」操作をすればよいです。
$A_0$の削除の操作に$O(N)$掛かってしまうので計算量は$O(NK)$となりますが、十分速いです。
(配列の代わりにdequeを用いると$O(K)$となってよいですがここでは配列を用いた実装をします。)

Pythonでの実装例

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

for i in range(K):
  del A[0]
  A.append(0)

print(*A,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,K; cin>>N>>K;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  rep(i,0,K){
    A.erase(A.begin());
    A.push_back(0);
  }
  
  rep(i,0,N){
    cout<<A[i];
    if(i==N-1){
      cout<<endl;
    }else{
      cout<<" ";
    }
  }
}

C++で配列LのL_iを削除する時にはL.erase(L.begin()+i)とすればよいです。
これは$N=L$の大きさとして$O(N)$掛かるので容易にfor文の中で使わない方が良いですが、このような低難易度の問題で使うことはあるので覚えておきましょう。

1-3 B問題 Misjudge the Time

問題

デジタル時計があります。
このデジタル時計は四角形状に数字を示す為、AB:CDである時、AC:BDのように読み間違えてしまうことがあります。
そこで、次を満たす時刻AB:CDを見間違えやすい時刻と定義します。

正しい時刻$AB:CD$に対して、読み間違えた$AC:BD$は24時制での時刻としてあり得る。

現在時計はH時W分を示しているので、以後、時計が見間違えやすい時刻を指すのは何時何分か求めて下さい。

制約

・$0 \leq H <24$
・$0 \leq W <60$

解説

大まかな解法

24時制であり得る時刻はせいぜい$1440$通りしかないので、全探索めいたことをしても間に合いそうです。

辞書順で$(H,W)$以後の組$(h,w)$(=H時W分以後に現れるh時w分)を見て行き、見間違えやすい時刻を見つけ次第それを答えとして出力すればよいです。

見間違えやすいかの判定

ある時刻$h:w$を見間違えやすい時刻か判定することを考えます。
元の時刻$h:w$に対して見間違えた後の時刻$h_2:w_2$を求め、それが時刻としてあり得るか、つまり$0 \leq h_2 < 24$かつ$0 \leq w_2 <60$か判定すればよいです。
$h_2:w_2$は、$h:w$の$10$の位や$1$の位から求められます。

まとめ

最初に$0 \leq h <24, 0 \leq w <60$のループを回し、$h:w$が$H:W$以後であれば見間違えやすい時刻か判定し、そうであればそれを出力して終了する、というようにすればよいです。
十分速いので間に合います。

尚、答えが見つからなければ0 0を出力するというようにしないと$H=23 ,W=59$のようなケースで引っ掛かります。
$23:59$より辞書順で後の時刻で「見間違えやすい時刻」なものは存在しないからです。

Pythonでの実装例

H,W=map(int,input().split())

for i in range(24):
  for j in range(60):
    if (i,j)<(H,W):
      continue
    a,b=i//10,i%10; c,d=j//10,j%10
    n,m=a*10+c,b*10+d
    if 0<=n<24 and 0<=m<60:
      print(i,j)
      exit()

print(0,0)

C++での実装例

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

int main(){
  int H,W; cin>>H>>W;
  
  rep(i,0,24){
    rep(j,0,60){
      if(make_pair(i,j)<make_pair(H,W)) continue;
      int a=i/10,b=i%10,c=j/10,d=j%10;
      int h2=a*10+c,w2=b*10+d;
      if(0<=h2 and h2<24 and 0<=w2 and w2<60){
        cout<<i<<" "<<j<<endl;
        return 0;
      }
    }
  }
  cout<<0<<" "<<0<<endl;
}

C++もpairで<使えるんですね。

1-4 C問題 FF

問題

あるSNSには$N$人のユーザーがいます。ユーザーは他のユーザーをフォローしたりフォローを解除したりできます。
SNSがスタートしてから$Q$回の操作が行われました。$i$回目の操作は$t_i,a_i,b_i$で表されます。
・$t_i=1$の時 : ユーザー$a_i$が$b_i$をフォローする。元々フォローしているなら何も起こらない。
・$t_i=2$の時 : ユーザー$a_i$が$b_i$のフォローを解除する。元々フォローしていないなら何も起こらない。
・$t_i=3$の時 : ユーザー$a_i$と$b_i$が相互にフォローしているか判定する。

$t_i=3$の操作について、$i$の小さい順に判定の結果をYesかNoで出力して下さい。

制約

・$2 \leq N \leq 10^9$
・$1 \leq Q \leq 10^5$

解説

特に重い操作は無いので、各人がフォローしている人の集合を格納する辞書型$S$を用意すればよいです。
$t=1$のクエリでは、$S_a$に$b$を追加し、$t=2$のクエリでは$S_a$から$b$を削除し、$t=3$のクエリでは、$S_a$に$b$が含まれ、且つ$S_b$に$a$が含まれているか判定すればよいです。

集合を扱う型の計算量は、Pythonでのset、C++でのunordered_setを使えば$O(1)$、C++のsetを使ってもせいぜい$O(\log n)$($n$は要素数)なので高速です。
計算量は$O(Q)$や$O(Q \log N)$で十分高速です。

Pythonでの実装例

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

S={}
for i in range(Q):
  t,a,b=map(int,input().split())
  if t==1:
    S.setdefault(a,set()); S[a].add(b)
  elif t==2:
    if a in S and b in S[a]:
      S[a].remove(b)
  else:
    if a in S and b in S and b in S[a] and a in S[b]:
      print("Yes")
    else:
      print("No")

C++での実装例

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

int main(){
  int N,Q; cin>>N>>Q;
  
  map<int,set<int>> S;
  rep(i,0,Q){
    int t,a,b; cin>>t>>a>>b;
    if(t==1){
      S[a].insert(b);
    }else if (t==2){
      S[a].erase(b);
    }else{
      if(S[a].count(b) and S[b].count(a)){
        cout<<"Yes"<<endl;
      }else{
        cout<<"No"<<endl;
      }
    }
  }
}

Twidaiて...

1-5 D問題 All Assign Point Add

問題

長さ$N$の整数列$A$が与えられます。
$Q$個のクエリが与えられます。クエリの種類は以下の通りです。

・1 x : $A$の全ての要素を$x$で書き換える。
・2 i x : $A_i$に$x$を加える。
・3 i : $A_i$を出力する。

クエリを上から順番に処理して下さい。

制約

・$1 \leq N \leq 10^5$
・$1 \leq Q \leq 10^5$
・$1 \leq x \leq 10^9$

解説

現在の$A$を配列に持って愚直にクエリを実行しても間に合いそうですが、$1$のクエリで$O(N)$掛かってしまうので最悪計算量は$O(NQ)$となり通りません。

ここで、次のような工夫をすればよいです。

・最後に全体が書き換えられた値 $base$を記録する。
・各$i$について、$base$に加えて$A_i$に足された値を格納するような辞書型$plus$を用意する。

これを使えば各クエリは次のように処理できます。

・クエリ$1$ : $base$を$x$に変更する。
・クエリ$2$ : $plus_i$に$x$を足す。
・クエリ$3$ : $base$と$plus_i$を足した値が現在の$A_i$の値である。

これを使えば全てのクエリを$O(1)$で処理できるので全体の計算量は$O(Q)$となり間に合います。

C++ではlong long型を使いましょう。

Pythonでの実装例

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

base=0
plus={i:A[i] for i in range(N)}

for _ in range(Q):
  query=list(map(int,input().split()))
  n=query[0]
  if n==1:
    _,x=query
    base=x
    plus={}
  elif n==2:
    _,i,x=query; i-=1
    plus.setdefault(i,0); plus[i]+=x
  else:
    _,i=query; i-=1
    p=0
    if i in plus:
      p=plus[i]
    print(base+p)

C++での実装例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#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 Q; cin>>Q;
  
  ll base=0;
  map<ll,ll> plus;
  rep(i,0,N){
    plus[i]=A[i];
  }
  
  rep(a,0,Q){
    int n; cin>>n;
    if(n==1){
      ll x; cin>>x;
      base=x;
      plus.clear();
    }else if(n==2){
      ll i,x; cin>>i>>x; i--;
      plus[i]+=x;
    }else{
      ll i; cin>>i; i--;
      cout<<base+plus[i]<<endl;
    }
  }
}

Dが茶前半って結構珍しいですね

1-6 E問題 Grid Filling

問題

$H$行$W$列のグリッドがあります。$(i,j)$を上から$i$行目、左から$j$列目のマスとします。
整数$h,w$が与えられるので、$0 \leq k \leq H-h,0 \leq l \leq W-w$を満たす全ての$(k,l)$について次の小問題に答えて下さい。

・マス$(k,l)$を左上とする、縦$h$マス横$w$マスの長方形領域を塗りつぶす時、塗りつぶされていないマスにある数は何種類か。

又、これらの小問題は全て独立であり、問題を解く際に実際にマスを塗りつぶすことはありません。

制約

・$1 \leq H,W,N \leq 300$
・$1 \leq h \leq H,1 \leq w \leq W$
・$1 \leq A_{i,j} \leq N$

解説

一つ毎に小問題を求めていると、一つの問題につき$(hw)$掛かるので$O(HWhw)$も掛かってしまいます。(たぶん)
単純計算で$300^4=81$億にもなってしまうのでC++でも厳しそうです。

ここで、各$i(1 \leq i \leq N)$について、「塗りつぶされていないマスに$i$が存在しない」ことは、「塗りつぶしている長方形領域内にグリッドに書かれた$i$の全てが存在する」ということと同値です。

ですから、各長方形領域に数$i$がいくつあるかを求められれば解ける訳ですが、これには二次元累積和と呼ばれるものを使えばよいです。

二次元累積和

二次元累積和は累積和の拡張のようなもので、次の$cnt$のようなものを指します。

$cnt[i+1][j+1]=$$(0,0)$を左上、$(i,j)$を右下とする長方形領域の中にある数の総和

遷移はこのようにすればよいです。
$cnt[i+1][j+1]=cnt[i][j+1]+cnt[i+1][j]-cnt[i][j]+(i,j)に対応する数$
遷移は紙に書いてみたら納得できると思います。

今回の問題では

今回の問題では、次のような二次元累積和を用意すればよいです。

$cnt[i+1][j+1][n]=(0,0)$を左上、$(i,j)$を右下とする長方形領域の中に書いてある$n$の数

この二次元累積和はfor文で$O(NHW)$で用意できます。

そこからどのように答えを求めるべきかですが、前述の通り、各長方形領域(縦$h$マス横$w$マス)に数$i(1 \leq i \leq N)$がいくつあるかを求め、それがグリッド全体にある$i$の数と同じであるかを判定すればよいです。
それが$(x,y)$を左上とする長方形領域について$True$となれば、$(k,l)=(x,y)$の時の答えから$1$減らせばよいです。(塗りつぶした時に数$i$は全て隠れるから)
この部分の計算量は、各$i(1 \leq i \leq N)$について$O(HW)$掛かるので$O(NHW)$です。

計算量は、$O(NHW)$となり十分高速です。

これを実装すればよいですが、結構複雑なので頑張りましょう。

Pythonでの実装例

from collections import Counter

H,W,N,h,w=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]

cnt=[[[0]*N for _ in range(W+1)] for _ in range(H+1)]
al=Counter()
for i in range(H):
  for j in range(W):
    A[i][j]-=1
    al[A[i][j]]+=1
    for n in range(N):
      cnt[i+1][j+1][n]=cnt[i+1][j][n]+cnt[i][j+1][n]-cnt[i][j][n]
      if A[i][j]==n:
        cnt[i+1][j+1][n]+=1
        
for i in range(H-h+1):
  for j in range(W-w+1):
    ans=N
    for n in range(N):
      now=cnt[i+h][j+w][n]-cnt[i][j+w][n]-cnt[i+h][j][n]+cnt[i][j][n]
      if now==al[n]:
        ans-=1
    print(ans,end=" ")
    if j==W-w-1:
      print()

C++での実装例

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

int main(){
  int H,W,N,h,w; cin>>H>>W>>N>>h>>w;
  vector<vector<int>> A(H,vector<int>(W));
  rep(i,0,H) rep(j,0,W) cin>>A[i][j];
  
  map<int,int> al;
  vector<vector<vector<int>>> cnt(H+1,vector<vector<int>>(W+1,vector<int>(N)));
  
  rep(i,0,H){
    rep(j,0,W){
      A[i][j]-=1;
      al[A[i][j]]++;
      rep(n,0,N){
        cnt[i+1][j+1][n]=cnt[i+1][j][n]+cnt[i][j+1][n]-cnt[i][j][n];
        if(A[i][j]==n){
          cnt[i+1][j+1][n]+=1;
        }
      }
    }
  }
  
  rep(i,0,H-h+1){
    rep(j,0,W-w+1){
      int ans=N;
      rep(n,0,N){
        int now=cnt[i+h][j+w][n]-cnt[i][j+w][n]-cnt[i+h][j][n]+cnt[i][j][n];
        if(now==al[n]){
          ans--;
        }
      }
      cout<<ans;
      if(j==W-w) cout<<endl;
      else cout<<" ";
    }
  }
}

実装だるいです

2 さいごに

お読み頂きありがとうございました。
今回は色々実装が大変な回だったように思います。
加えて、重要な連絡です。
今回でABCの解説を書くのを最後にしようと思います(多分)。理由は時間が溶けまくるからです。
読んで下さった皆様ありがとうございました。
以上です。
よい競プロライフを!!