0 はじめに

0-1 記事について

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

1 ABC270 解説

1-1 個人的な感想

今回は本当は高Diffが狙える筈の回でした。
Diffは、A,B問題が灰前半、Cが茶後半、D,Eが水前半(D>E)、Fが青後半といった感じです。
僕はABCEの四冠で、80分も掛ってしまいました。
Perfは1223、Rating変動は1194→1197(+3)でした。
Dを通せなかった上結構ギリギリで入水できなかったのでとても残念です。。。

1-2 A問題 1-2-4 Test

問題

配点がそれぞれ$1,2,4$点の、$3$問より成る試験があり、$A$くん、$B$くん、$C$くんがその試験を受けました。
$C$くんは、$A$くんと$B$くんのうちどちらかは正解した問題は正解し、両方が正解しなかった問題は正解できませんでした。
$A$くんと$B$くんの点数が与えられるので、$C$くんの点数を求めて下さい。
$C$くんの点数が一意に定まることは証明できます。

制約

・$A,B$は整数、$0 \leq A,B \leq 7$

解説

(以下、各登場人物は敬称略とします)

解法-1

$A$,$B$の正解した問題は特定可能です。
例えば、問題の配点が$1,2,3$点だと、合計点数が$3$点の時、$1,2$点問題を正解した場合と$3$点の問題を正解した場合と二通りあります。
対して配点が$1,2,4$点の場合だと、あり得る点数$8$通りに重複が無い為、どの問題を正解したかを一通りに特定することができます。

この性質を利用して、$A$と$B$の正解した問題を割り出し、その情報から$C$の正解した問題がどれか特定しましょう。

Pythonでの実装例

A,B=map(int,input().split())

def q(n):
  if n==0: return {}
  elif n==1: return {1}
  elif n==2: return {2}
  elif n==3: return {1,2}
  elif n==4: return {4}
  elif n==5: return {1,4}
  elif n==6: return {2,4}
  else: return {1,2,4}

c=set()
for a in q(A):
  c.add(a)
for b in q(B):
  c.add(b)
print(sum(c))

C++での実装例

#include <bits/stdc++.h>
using namespace std;

vector<int> q(int n){
  if(n==0) return {};
  else if(n==1) return {1};
  else if(n==2) return {2};
  else if(n==3) return {1,2};
  else if(n==4) return {4};
  else if(n==5) return {1,4};
  else if(n==6) return {2,4};
  else return {1,2,4};
}

int main(){
  int A,B; cin>>A>>B;
  
  vector<int> a=q(A),b=q(B);
  int ans=0;
  
  for(auto i:{1,2,4}){
    if(count(a.begin(),a.end(),i) or count(b.begin(),b.end(),i)){
      ans+=i;
    }
  }
  cout<<ans<<endl;
}

解法-2

勿論、上に挙げた解法でもACできます。
しかし、今回の問題では、bit演算のうちorを使って解くことができます。

bit演算とは、二進法表記した時の各桁のビットを色々操作する演算です。(語彙力)
こちらの記事に詳しく載っています。

話を戻します。この問題に於いて、$1,2,4$点の問題はそれぞれビットとして捉えられます。
それぞれのビットで、$A$と$B$どちらかが$1$であれば$C$のそのビットは$1$になる訳ですから、問題の指示はorと変わりありません。詳しくは上のリンクをご参照ください。
例えば、入力例2で考えてみましょう。
$A$は$5$点ですから、二進法表記すると$101$です。$B$は$3$点ですから$011$です。
$101$と$011$のor(論理和)は$111$です。$111$を十進法表記に直すと$7$ですから、確かに解けていますね。

これを実装すればいい訳ですが、幸いにも多くのプログラミング言語にはorが存在します。
以降はやるだけですね。

Pythonでの実装例

A,B=map(int,input().split())
print(A|B)

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int A,B; cin>>A>>B;
  cout<<(A|B)<<endl;
}

A問題の割には、様々な考察ができて、興味深いものだったように思います。

1-3 B問題 Hammer

問題

数直線の原点に$A$くんがいます。
$A$くんは$X$にあるゴールに行きたいです。
$Y$には壁があり、$Z$にはその壁を壊すことができるハンマーがあります。
壁はそのハンマーを使う以外では壊せません。
さて、$A$くんはゴールへ辿り着けるでしょうか。

制約

・$X,Y,Z$は相異なる整数、$-1000 \leq X,Y,Z \leq1000$

解説

$0,X,Y,Z$の大小の場合分けの問題です。
以下の3ステップに場合分けして合計距離を求めましょう。

①$0$からゴールまでに壁がなく、そのままゴールできる
②$0$からゴールまでに壁はあるが、ハンマーを取れるので壁を壊してゴールできる
③①のようにストレートにゴールできない上、ハンマーも壁の奥にあるので壁を壊せず、ゴールできない

どれも、$0,X,Y,Z$の大小のみで表すことができます。
$X,Y,Z$が負にもなり得ることに注意して実装しましょう。

Pythonでの実装例

X,Y,Z=map(int,input().split())

if Y<X and Y<0:
  print(abs(X)); exit()
elif X<Y and 0<Y:
  print(abs(X)); exit()

if Z<Y<0 or 0<Y<Z:
  print(-1); exit()
else:
  ans=abs(Z)
  ans+=abs(Z-Y)
  ans+=abs(X-Y)
  print(ans); exit()

print(-1)

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main(){
  int X,Y,Z; cin>>X>>Y>>Z;
  
  if(Y<X and Y<0){
    cout<<abs(X)<<endl;
    return 0;
  }else if(X<Y and 0<Y){
    cout<<abs(X)<<endl;
    return 0;
  }
  
  if(Z<Y and Y<0){
    cout<<-1<<endl;
    return 0;
  }else if(0<Y and Y<Z){
    cout<<-1<<endl;
    return 0;
  }else{
    int ans=abs(Z)+abs(Z-Y)+abs(Y-X);
    cout<<ans<<endl;
    return 0;
  }
  
  cout<<-1<<endl;
}

このような場合分け問題では、落ち着いて簡潔な場合分けを行うことが重要です。

1-4 C問題 Simple path

問題

$N$頂点の木があり、$i$番目の辺は頂点$U_i,V_i$を結んでいます。
木にある$2$頂点$X,Y$が与えられるので、頂点$X,Y$の単純パスに含まれる頂点を順に列挙して下さい。

制約

・$1 \leq N \leq 2×10^5$
・$1 \leq X,Y \leq N , X \neq Y$
・$1 \leq U_i, V_i \leq N$

解説

完全な知識ゲーです。
グラフ理論を知らないと解けないです。(多分)
グラフや木についてはこちらの記事を見てみて下さい。

これは入力で与えられた木の、頂点$X$から$Y$へのパスを出力する問題です。
木を$X$から探索していき、それぞれの頂点について前に通った頂点をメモし、最後に復元すればよいです。
BFS(幅優先探索)でもDFS(深さ優先探索)でも解けます。
どちらにしても計算量は$O(N)$です。
それぞれの場合の実装を載せておきます。

Pythonでの実装(BFS)

from collections import deque

N,X,Y=map(int,input().split()); X-=1; Y-=1
G=[[] for _ in range(N)]
for i in range(N-1):
  u,v=map(int,input().split()); u-=1; v-=1
  G[u].append(v); G[v].append(u)

D=deque(); D.append(X)
seen=[0]*N; seen[X]=1
rec={}
while D:
  now=D.popleft()
  for nxt in G[now]:
    if seen[nxt]:
      continue
    seen[nxt]=1
    rec.setdefault(nxt,now)
    D.append(nxt)

ans=[]
n=Y
while n!=X:
  ans.append(n+1)
  n=rec[n]
ans.append(n+1)
print(*reversed(ans),sep=" ")

C++での実装(BFS)

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

int main(){
  int N,X,Y; cin>>N>>X>>Y; X--; Y--;
  vector<vector<int>> G(N);
  rep(i,0,N-1){
    int a,b; cin>>a>>b; a--; b--;
    G[a].push_back(b); G[b].push_back(a);
  }
  
  queue<int> Q; Q.push(X);
  vector<int> seen(N,0); seen[X]=1;
  map<int,int> rec;
  while(!Q.empty()){
    int now=Q.front(); Q.pop();
    for(auto nxt:G[now]){
      if(seen[nxt]){
        continue;
      }
      seen[nxt]=1;
      rec[nxt]=now;
      Q.push(nxt);
    }
  }
  
  vector<int> ans;
  int n=Y;
  while(n!=X){
    ans.push_back(n+1);
    n=rec[n];
  }
  ans.push_back(n+1);
  reverse(ans.begin(),ans.end());
  for(auto i:ans){
    cout<<i<<" ";
  }
  cout<<endl;
}

Pythonでの実装(DFS)

import sys
sys.setrecursionlimit(10**9)

N,X,Y=map(int,input().split()); X-=1; Y-=1
G=[[] for _ in range(N)]
for i in range(N-1):
  u,v=map(int,input().split()); u-=1; v-=1
  G[u].append(v); G[v].append(u)

rec={}
def DFS(now,prev):
  for nxt in G[now]:
    if nxt==prev:
      continue
    rec.setdefault(nxt,now)
    DFS(nxt,now)
  return 

DFS(X,None)
ans=[]
now=Y
while now!=X:
  ans.append(now+1)
  now=rec[now]
ans.append(now+1)
print(*reversed(ans),sep=" ")

C++での実装(DFS)

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

vector<vector<int>> G(200000);
map<int,int> rec;

void DFS(int now,int prev){
  for(auto nxt:G[now]){
    if(nxt==prev){
      continue;
    }
    rec[nxt]=now;
    DFS(nxt,now);
  }
  return;
}

int main(){
  int N,X,Y; cin>>N>>X>>Y; X--; Y--;
  
  rep(i,0,N-1){
    int a,b; cin>>a>>b; a--; b--;
    G[a].push_back(b); G[b].push_back(a);
  }
  
  DFS(X,-1);
  
  vector<int> ans;
  int now=Y;
  while(now!=X){
    ans.push_back(now+1);
    now=rec[now];
  }
  ans.push_back(now+1);
  reverse(ans.begin(),ans.end());
  
  for(auto i:ans){
    cout<<i<<" ";
  }
  cout<<endl;
}

個人的にはもう少し低いDiffが出る感じがしていました。グラフ理論を勉強するだけで解ける問題は大幅に上がります。未習得の方はこれを機に習得しましょう。(この台詞何回目??)

1-5 D問題 Stones

問題

数列$A={A_1,A_2,...,A_N}$と$N$個の石を使って、二人が先手と後手に分かれて次のようなゲームをします。

・先手から、次の操作を交互に行う。

・$A$から残っている石の数以下のものを選び、その数だけ石を取る。

・石が無くなったら終了。

両者とも、ゲーム終了時の手持ちの石が多くなるように最適な行動をとります。
先手はいくつ石を取れるでしょうか。

制約

・$1 \leq N \leq 10^4$
・$1 \leq K \leq 100$
・$1 = A_1 < A_2 < ... < A_N \leq N$

解説

二人ともが結果が最適となるようにゲームを進める問題です。
私が一番嫌いな問題です。
色々な条件が組み合わさって複雑ですが、この種の問題では、如何に簡潔なDPを作るかが重要になってきます。
ARC038は、このゲーム系の問題が集まっていて、特にその解説が参考になります。

この種の問題では幾つか解法のパターンがありますが、DPを立てる場合は次のようなDPが有効となることが多いです。

$DP[i]=$何かしらの数値が$i$の時の先手のスコア

今回はこのようにDPを立てます。

$DP[i]=$残りの石が$i$個の状態からゲームを始めた時の、先手が合計で取れる石の数

そして、$DP[i]$は$A_j+$「$i-A_j$個の状態で始めた時の、後手が合計で取れる石の数」と言い換えられます。又、$A_1=1$であるので、最終的には全ての石が取られます。
よって
$DP[i]=A_j+$「$i-A_j$個の状態で始めた時の、後手が合計で取れる石の数」
$=A_j+i-A_j-$「$i-A_j$個の状態で始めた時の、先手が合計で取れる石の数」
$=A_j+i-A_j-DP[i-A_j]$
$=i-DP[i-A_j]$
となります。

再帰DPとすることによって$i$が小さい場合から求めていけばよいです。

Pythonでの実装例

import sys
sys.setrecursionlimit(10**9)

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

DP=[None]*(N+1)

def DFS(now):
  if DP[now]!=None:
    return DP[now]
  ret=0
  for i in range(K):
    if A[i]<=now:
      ret=max(ret,A[i]+now-A[i]-DFS(now-A[i]))
  DP[now]=ret
  return ret

DFS(N)
print(DP[N])

C++での実装例

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

int N,K;
vector<int> DP(10001,-1);
vector<int> A(100);

int DFS(int now){
  if(DP[now]!=-1){
    return DP[now];
  }
  int ret=0;
  rep(i,0,K){
    if(A[i]<=now){
      ret=max(ret,A[i]+now-A[i]-DFS(now-A[i]));
    }
  }
  DP[now]=ret;
  return ret;
}

int main(){
  cin>>N>>K;
  rep(i,0,K) cin>>A[i];
  
  DFS(N);
  cout<<DP[N]<<endl;
}

区間スケジューリングやクラスカル法とは異なり、今回の問題では貪欲法で解くことができません。問題は、最終的な結果を最適化したときのスコアを求めています。稀に、貪欲法をするだけで解ける問題も存在しますが、その見分けが重要となってきます。

1-6 E問題 Apple Baskets on Circle

問題

$N$個のカゴが円状に置かれています。
カゴ$i$には$A_i$個リンゴが入っています。
今カゴ$1$の前に立っており、今から次の操作を行います。

目の前のカゴにリンゴが入っているなら$1$つ取り、カゴ$(i+1) \mod N$の前へ移動する。

リンゴを$K$個取った時点で操作を終える時、それぞれのカゴに最終的に入っているリンゴの数を求めて下さい。

制約

・$1 \leq N \leq 10^5$
・$0 \leq A_i \leq 10^{12}$
・$1 \leq K \leq 10^{12}$
・$A$の総和は$K$以上

解説

愚直に$K$回の操作を行うシミュレーションをすると、$K$の制約が大きすぎるので当然TLEが出てしまいますね。
ではどのように工夫をすればいいでしょうか。

操作を$N$回行ってカゴを一周することを「$1$巡する」という事にします。
$K$回リンゴを取る作業が、$n$巡した後$m$回カゴを移動した時に終わったとすると、$m$は$n$と$K$などから求められるので良いとして、$n$は次の判定問題を対数回数行う二分探索法で求められそうです。

・$x$巡した時既に$K$のリンゴを取る作業を終えているか

$x$巡するということは、それぞれのカゴを等しく$x$回訪れるということなので、$i$個目のカゴからは$min(A_i,x)$回リンゴを取ったことになります。この値の総和が$K$以上ならば$true$,$K$未満ならば$false$を返せばよいです
$N$個のカゴそれぞれについて$min(A_i,x)$を求めるだけなので、この判定問題の計算量は$O(N)$です。

求めるべき$n$は、判定問題の結果が$false$となる最大の
二分探索の左端は$0$、右端は$10^{12}$くらいにすれば良いでしょう。
$m$は、それまでにリンゴを取った回数などから求められます。

以下に実装を示します。

Pythonでの実装例

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

def calc(n):
  num=0
  for i in A:
    num+=min(i,n)
  return num

left,right=0,10**12
while left+1<right:
  mid=(left+right)//2
  if calc(mid)<=K:
    left=mid
  else:
    right=mid

done=calc(left)

for i in range(N):
  if K-done==0:
    break
  if A[i]-left>0:
    A[i]-=1
    done+=1

for i in range(N):
  print(max(0,A[i]-left),end=" ")

C++での実装例

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

vector<ll> A(100000);

ll calc(ll n){
  ll ret=0LL;
  for(auto i:A){
    ret+=min(i,n);
  }
  return ret;
}

int main(){
  ll N,K; cin>>N>>K;
  rep(i,0,N) cin>>A[i];
  
  ll left=0LL,right=10000000000000LL;
  while(left+1<right){
    ll mid=(left+right)/2;
    if(calc(mid)<=K){
      left=mid;
    }else{
      right=mid;
    }
  }
  
  ll done=calc(left);
  rep(i,0,N){
    if(K-done==0){
      break;
    }
    if(A[i]-left>=0){
      A[i]--;
      done++;
    }
  }
  
  rep(i,0,N){
    cout<<max(0LL,A[i]-left)<<" ";
  }
  cout<<endl;
}

中々面白い問題だったと思います。

2 さいごに

最後までご覧頂きありがとうございます。
C++は本業でないので可也読みにくいかもしれません。その辺りご意見下さると嬉しいです。
C++での二分探索なども勉強していきたいです。
以上です。
お読み頂きありがとうございました!!
よい競プロライフを!!
~~いいね下さい...(定期)~~