ABC271をPythonとC++で

0 はじめに

0-1 記事について

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

0-2 追記

2022/10/13 22時、F問題の解説を追加致しました。

1 ABC271 解説

1-1 個人的な感想

入水しました!!!

名前も水色になりました!!
それはさておき個人的な感想です。
Diffは、A,Bが灰前半、C,Dが緑前半、Eが水中間、Fが青前半という結果になりました。
私はABDEの4冠でした。
...Cはバグり散らかして萎え、DとEを解き、結局最後まで解きませんでした..
Perfは1348、Rating変動は1197→1213(+16)となりました。とても嬉しいです。
EのWriterさんに感謝感謝～～

1-2 A問題 484558

問題

整数$N$が与えられるので、その数の$16$進数表記を$2$桁で出力して下さい。

制約

・$0 \leq N \leq 255$,$N$は整数

解説

各言語に用意されている $16$進数のツールなどを使っても良いですが、せいぜい二桁なので、$16$進数表記の一桁目と二桁目を%などで計算しましょう。
多分そっちの方が楽です。
10→A、11→Bなどの変換を忘れずに。

Pythonでの実装例

N=int(input())

a,b=N//16,N%16
D={10:'A',11:'B',12:'C',13:'D',14:'E',15:'F'}
if a>=10: a=D[a]
if b>=10: b=D[b]
print(str(a)+str(b))

多分もう少し簡潔にできます..

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 a=N/16,b=N%16;
  
  map<int,char> ch;
  rep(i,0,16){
    if(i<10){
      ch[i]='0'+i;
    }else{
      ch[i]='A'+(i-10);
    }
  }
  
  cout<<ch[a]<<ch[b]<<endl;
}

C++だと'A'+iみたいに書けて良いですね..

問題名謎ですね..

1-3 B問題 Maintain Multiple Sequences

問題

整数列が$N$個与えられます。
$i$番目の数列は$L_i$項より成り、その内$j$番目の要素は$a_{i,j}$です。
$Q$個のクエリが与えられます。
$i$番目のクエリでは整数$s_k,t_k$が与えられるので、$s_k$番目の数列の$t_k$項目を出力して下さい。

制約

・$1 \leq N,Q \leq 2×10^5$
・$1 \leq L_i$
・$L$の総和は$2×10^5$以下
・$1 \leq a_{i,j} \leq 10^9$
・$1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k}$

解説

入力を受け取って出力するだけです。
二次元配列を使いますね。

Pythonでの実装例

N,Q=map(int,input().split())
A=[]
for i in range(N):
  s=list(map(int,input().split()))
  A.append(s[1:])

for i in range(Q):
  s,k=map(int,input().split()); s-=1; k-=1
  print(A[s][k])

Pythonだと1000ms近く掛ったのでヒヤヒヤしました。

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;
  vector<vector<int>> A(N);
  rep(i,0,N){
    int l; cin>>l;
    A[i]=vector<int>(l);
    rep(j,0,l){
      cin>>A[i][j];
    }
  }
  
  rep(i,0,Q){
    int s,k; cin>>s>>k;
    s--; k--;
    cout<<A[s][k]<<endl;
  }
}

C++速いですね。

詳しくないので断定はできませんが、結構なメモリを必要とする問題だったので通らない言語もありそうですね...

1-4 C問題 Manga

問題

全$10^9$巻の漫画を読むことにしました。
最初、単行本を$N$冊持っており、$i$冊目は$A_i$巻です。
あなたは次の操作を、読み始めるまでに何回でも行うことが出来ます。

・現在持っている単行本が$2$冊以上である時、現在持っているものから$2$冊選んで売り、好きな巻を$1$冊買う。

操作の後、$1$巻,$2$巻,$3$巻,...と、巻番号が連続となるように読んでいきます。読める巻数の最大値はいくつになるか求めて下さい。

制約

・$1 \leq N \leq 3×10^5$
・$1 \leq a_i \leq 10^9$

解説

問題を言い換えてみます。

操作を行った後、$1$巻から$n$巻まで連続で読める、最大の$n$を求めて下さい。

この形式は二分探索に他なりません。二分探索だとすると判定問題は以下のようになります。

適切な操作を施すことで、$1$巻から丁度$x$巻まで連続で読めますか？

丁度$x$巻まで連続で読めるかですが、持っておく巻の数をrem,売る巻の数をunusedとして、次のように判定を行えます。

・$i(1 \leq i \leq N)$について、もし$i \leq x$かつ$i∈A$ならremを$1$増やし($i$巻を持っておく)、そうでないならunusedを$1$増やす($i$巻を売りに出す)。
・$2$つ売って$1$つ買えるので、持っておく巻に加えて、買える巻の数はunused//2(//は切り捨て)。
・合計のrem+unused//2が$x$以上ならば$true$、そうでないなら$false$。

$A$を探索するだけなので判定問題の計算量は$O(N)$で、二分探索の左端、右端はそれぞれ$0,N+1$とすればよいです。
(右端を$N$とするとWAが出ます。$N+1$にしないと、実際$N$のところ$N-1$と出力してしまいます。)
ですから計算量は$O(N log N)$となり間に合います。
求めるべきはこの判定問題が$true$となる最大の$x$です。

不等号が等号を含むかなどに注意して実装しましょう。

Pythonでの実装例

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

def tf(x):
  rem,unused=0,0
  for i in range(1,N+1):
    if i in S and i<=x:
      rem+=1
    else:
      unused+=1
  return rem+unused//2>=x

left,right=0,N+1
while left+1<right:
  mid=(left+right)//2
  if tf(mid):
    left=mid
  else:
    right=mid
print(left)

C++での実装例

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

int N;
map<int,int> cnt;

bool tf(int x){
  int rem=0,unused=0;
  rep(i,1,N+1){
    if(i<=x and cnt[i]){
      rem++;
    }else{
      unused++;
    }
  }
  int num=rem+unused/2;
  return num>=x;
}

int main(){
  cin>>N;
  vector<int> A(N);
  rep(i,0,N){
    cin>>A[i];
    cnt[A[i]]++;
  }
  
  int left=0,right=N+1;
  while(left+1<right){
    int mid=(left+right)/2;
    if(tf(mid)) left=mid;
    else right=mid;
  }
  
  cout<<left<<endl;
}

mapを使っているのでC++だと$O(N log^2 N)$だったりしそうです。

二分探索の左端と右端の設定はミスるとWAが出て痛いので、支障を来さないならば右端を広くしておくなど工夫をしましょう。
又、この問題はdequeでのシミュレーションでも解けたようです。

1-5 D問題 Flip and Adjust

問題

両面に整数の書かれたカードが$N$枚あり、表には$A_i$、裏には$B_i$が書かれています。
それぞれのカードについて、表裏を好きなように設定することができます。
上に向いている面に書かれた数の総和が$S$となるような表裏の設定が存在するか判定し、存在するならばその設定の仕方も出力して下さい。

尚、存在するならYes、存在しないならNoを出力し、カードの表裏は、「カードの$i$枚目が表向きならば$S_i$はH、裏向きならばT」となるような長さ$N$の文字列$S$で出力して下さい。

制約

・$1 \leq N \leq 100$
・$1 \leq S \leq 10000$
・$1 \leq a_i,b_i \leq 100$

解説

もし$N$の制約が小さければ、$N$枚の表裏の組合せ$2^N$通りを全探索することで解けますが、今回は制約からして明らかに無理です。
なので動的計画法(DP)が使えそうですね。

カードの枚数($N$)も、指定された総和($S$)もそう大きくはないので次のDPが適正です。

DP[i][j]=i枚目まで表裏を設定した時に、総和がjとなるようなものが存在するか

遷移はDP[i][j]からDP[i+1][j+k]($k∈{A_{i+1},B_{i+1}}$)のように行えばよいです。
これだけでは表裏がわかりませんが、DPテーブルに、その状態がどのような表裏の組合せでなのか遷移を受けたか載せることで解けます。

計算量は$O(NS)$なので間に合います。

Pythonでの実装例

N,S=map(int,input().split())
L=[list(map(int,input().split())) for _ in range(N)]

DP=[[0]*(S+2) for _ in range(N+1)]
DP[0][0]=[0]
for i in range(N):
  for j in range(S):
    if DP[i][j]:
      a,b=L[i]
      DP[i+1][min(j+a,S+1)]=DP[i][j]+["H"]
      DP[i+1][min(j+b,S+1)]=DP[i][j]+["T"]

print("Yes" if DP[N][S] else "No")
if DP[N][S]:
  print(*DP[N][S][1:],sep="")

Pythonでの実装は @Kentuc_ohさんより提供頂きました。ありがとうございます!!

C++での実装例

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

int main(){
  int N,S; cin>>N>>S;
  vector<vector<int>> L(N,vector<int>(2));
  rep(i,0,N){
    rep(j,0,2){
      cin>>L[i][j];
    }
  }
  
  vector<vector<string>> DP(N+1,vector<string>(S+2));
  DP[0][0]="0";
  rep(i,0,N){
    rep(j,0,S){
      if(DP[i][j]!=""){
        int a=L[i][0],b=L[i][1];
        DP[i+1][min(j+a,S+1)]=DP[i][j]+'H';
        DP[i+1][min(j+b,S+1)]=DP[i][j]+'T';
      }
    }
  }
  
  string ans=DP[N][S];
  if(ans=="0"){
    cout<<"No"<<endl;
  }else{
    cout<<"Yes"<<endl;
    rep(i,1,(int)ans.size()){
      cout<<ans[i];
    }
    cout<<endl;
  }
}

C++勉強中です、簡潔感の無い実装でごめんなさい... アドバイス頂ければ幸いです...

ABC240-C Jumping Takahashiと問題は殆ど一緒ですが、実際の選び方を出力するというのが加わっただけでDiffが400も違っています。

又、今回のように、「全探索が厳しければDP」という考え方は完全に正しくはありませんが、よく的中するものなので覚えておきましょう。
余談ですが巷では「DはDPのD」というスラングが存在するようです。覚えておきましょう。(いいえ)

1-6 E問題 Subsequence Path

問題

$N$個の都市と$M$個の道があります。
全ての道は一方通行で、道$i$を通ると$A_i$から$B_i$まで移動でき、道の長さは$C_i$です。
長さ$K$の数列$E$が与えられます。
都市$1$から$N$への移動経路のうち次の条件を満たすものを良い経路と呼びます。

通った道の番号を通った順に並べた数列$F$は$E$の連続するとは限らない部分列である。

良い経路としてあり得るものの中の、通った道の長さの合計の最小値を出力して下さい。
尚、良い経路が一つも存在しない場合は-1を出力して下さい。

制約

・$2 \leq N \leq 2×10^5$
・$1 \leq M,K \leq 2×10^5$
・$1 \leq A_i,B_i \leq N, A_i \neq B_i$
・$1 \leq C_i \leq 10^9$
・$1 \leq E_i \leq M$

解説

与えられるグラフは重み付きの有向グラフですので、普通に$1$から$N$への最短経路を求めるならばダイクストラ法を使えますが、今回は通る道の順番に制限が掛っているのでダイクストラ法は厳しそうです。
あの教えを思い出してください。「全探索が厳しそうならDP」です。

良い経路とは、「通った道の番号をそのままの順番で並べた数列$F$が$E$の部分列となる」経路です。
逆を返せば、「$E$の部分列$F$を設定し、$F$の順に道を選んで進んだ経路」は、成立すればですが良い経路になります。

ですから今回のはこのようなDPを立てればよいです。(DPの定義上、変数名はdistとしています。)

E[j]を見ている時のdist[i]=E[j]個目の道を選んだ時の、1からiへの最短経路

$E$を左から見ていけば、通った道の順番は$E$の部分列となるので、dist[i]で得られる最短経路は全て、良い経路のものとなります。
なので、最終的には

dist[i]=1からiまでの最短の良い経路の長さ

となります。

$E$を左から見るだけなので、計算量(DPのみ)は$O(K)$です。
これを実装すればよいです。

Pythonでの実装例

INF=float("INF")

N,M,K=map(int,input().split())
edge=[]
for i in range(M):
  a,b,c=map(int,input().split()); a-=1; b-=1
  edge.append([a,b,c])
E=list(map(int,input().split()))
for i in range(K): E[i]-=1

dist=[INF]*N; dist[0]=0
for i in range(K):
  a,b,c=edge[E[i]]
  dist[b]=min(dist[b],dist[a]+c)

print(dist[N-1] if dist[N-1]!=INF else -1)

C++での実装例

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

const ll INF=1000000000000000;

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

int main(){
  int N,M,K; cin>>N>>M>>K;
  vector<tuple<int,int,int>> edge(M);
  rep(i,0,M){
    int a,b,c; cin>>a>>b>>c; a--; b--;
    edge[i]=make_tuple(a,b,c);
  }
  vector<int> E(K);
  rep(i,0,K){
    cin>>E[i];
    E[i]--;
  }
  
  vector<ll> dist(N,INF);
  dist[0]=0;
  rep(i,0,K){
    int a,b,c;
    tie(a,b,c)=edge[E[i]];
    chmin(dist[b],dist[a]+c);
  }
  
  ll ans=dist[N-1];
  if(ans==INF){
    ans=-1;
  }
  printf("%ld\n",ans);
}

一見難しい問題ですが、$E$の部分列という制限に親切なDPを作ることで解けました。問題文の長さや問題の煩雑さに比べてコードは短いですね。

個人的には、Diff1400の問題だったのでコンテスト中に通せてとても嬉しかったです。

1-7 F問題 XOR on Grid Path

2022/11/03に新しく書きました。

問題

$N×N$のマス目があり、マス$(i,j)$には非負整数$A_{i_j}$が書いてあります。
マス$(i,j)$にいる時、マス$(i,j+1)$か$(i+1,j)$のどちらかに進むことが出来ます。
マス$(1,1)$から移動を繰り返して$(N,N)$まで行く経路のうち、通ったマスに書かれた非負整数の全てのXORが$0$となるものがいくつあるか求めて下さい。

制約

・$1 \leq N \leq 20$
・$0 \leq A_{i_j} \leq 2^{30}$

解説

まず普通に全探索すると計算量はどれくらいになるでしょうか。
マスを移動するのは合計で等しく$2(N-1)$回です。それぞれの移動で最大で$2$通りに分かれるので、移動経路を全探索すると計算量は$O(N・2^{2N})$となります。
(実際の存在する経路は $_{2N-2}C_{N-1}$ 通りですが説明の都合上こうしています)

半分全列挙

このような場合では、半分全列挙と呼ばれる手法が使えます。

半分全列挙は、次のような問題について有効です。

・裏表それぞれに整数の書かれたカードが$2N$枚ある。これらのカードについて、裏表をどちらかを上にして置き、カードの表に書かれた数の総和を求める。 与えられた整数$S$が、この総和の値としてあり得るか判定する。

前半$N$枚の総和として考えられる数の集合($A$とする)と、後半$N$枚の総和として考えられる数の集合($B$とする)をそれぞれbit全探索で求めておきます。
そして、全ての$a(a∈A)$について、次の小問題を解きます。

・$S-a$が$B$に含まれているか判定する。

この小問題が一つでも$True$となれば、判定問題の答えは$True$となり、そうでなければ$False$となります。

計算量は、最初に$A$と$B$を求めるのに$O(2^N)$かかり、平均計算量$O(1)$で解ける小問題を$2^N$個解くので、全体での計算量は$O(2^N)$です。

言い方を変えると、組合せが全体で$N$通りあるものを、約$\sqrt{N}$個の二つの集合に分けて$O(\sqrt{N})$くらいに高速化しようというアイデアです。

今回の問題

今回の問題はこの半分全列挙を使って解くことができる訳ですがどのように解けるか考えてみます。

経路全体の集合は$2^{2N-2}$個あります。これを丁度同じくらいの大きさの二つに分けたいです。
$(x,y)$を$(1,N)$から$(N,1)$に引いた直線上の格子点として、次のように分けるとよいです。
①$(1,1)$から$(x,y)$までの経路
②$(x,y)$から$(N,N)$までの経路

これらは$O(2^N)$で求められます。

今求めるべきは、経路上にある非負整数のXORが$0$になる点です。

ある2整数$A,B$があり、$A$と$B$のXORが$0$になる時必ず$A=B$です。
なので、全ての$(x,y)$について次の計算を行い、その総和を求めればよいです。

・①、②で得られた集合をそれぞれ$S$、$T$とする。
・$S_i=T_j$となる$i,j(1 \leq i,j \leq 2^{N-1})$の組を数える。

この計算は辞書型を使うことで簡単に行えます。①、②を先に求めておけば一回毎の計算量は小さくできます。(Pythonではdict、C++ではunordered_mapを用いて$O(1)$です。mapの$O(log N)$でも通ります)。
$(x,y)$の組は$N$個あり、それぞれについて$O(2^N)$掛かるのでこの部分の計算量は$O(N 2^N)$です。

$S,T$を計算するの$O(2^N)$掛かり、それから答えを求めるのに$O(N 2^N)$掛かるので、全体の計算量は$O(N 2^N)$です。

以下に実装例を貼ります。

Pythonでの実装例

from collections import Counter

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

cnt=[Counter() for _ in range(N)] #(1,1)から(x,y)までの経路
for i in range(1<<(N-1)):
  n=0
  x,y=0,0
  for j in range(N-1):
    n^=A[x][y]
    if i>>j&1:
      x+=1
    else:
      y+=1
  cnt[x][n]+=1

cnt2=[Counter() for _ in range(N)] #(x,y)から(N,N)までの経路
for i in range(1<<(N-1)):
  n=0
  x,y=N-1,N-1
  for j in range(N-1):
    n^=A[x][y]
    if i>>j&1:
      x-=1
    else:
      y-=1
  n^=A[x][y]
  cnt2[x][n]+=1

#求める
ans=0
for i in range(N):
  for n,m in cnt[i].items():
    ans+=m*cnt2[i][n]
print(ans)

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<vector<ll>> A(N,vector<ll>(N));
  rep(i,0,N){
    rep(j,0,N){
      cin>>A[i][j];
    }
  }
  
  vector<map<ll,ll>> cnt(N);
  rep(i,0,1<<(N-1)){
    ll n=0;
    int x=0,y=0;
    rep(j,0,N-1){
      n^=A[x][y];
      if(i>>j&1){
        x++;
      }else{
        y++;
      }
    }
    cnt[x][n]++;
  }
  
  vector<map<ll,ll>> cnt2(N);
  rep(i,0,1<<(N-1)){
    ll n=0;
    int x=N-1,y=N-1;
    rep(j,0,N-1){
      n^=A[x][y];
      if(i>>j&1){
        x--;
      }else{
        y--;
      }
    }
    n^=A[x][y];
    cnt2[x][n]++;
  }
  
  ll ans=0;
  rep(i,0,N){
    for(auto [n,m]:cnt[i]){
      ans+=m*cnt2[i][n];
    }
  }
  
  cout<<ans<<endl;
}

long long型を使いましょう。

半分全列挙は水Diff以降の高難易度な問題で稀に出題されます。 覚えておきましょう。

2 さいごに

最後までお読み頂きありがとうございます。
CとDが両方緑Diffという珍しい回でしたね。
私は入水できてとても嬉しかったです。後に色変記事など書く予定です。
やはりC++はまだ下手なので、アドバイスなど頂けると幸いです。
あと今回は解説が難しかったので日本語が崩壊してるところも多々あったかもしれません。発見した方はコメント欄より教えて下さい...お願いします..
以上です。
お読み頂きありがとうございました!!
よい競プロライフを!!
いいね下さい..(切実)