0 はじめに

0-1 記事について

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

1 ABC274 解説

1-1 個人的な感想

また情けない回です。Eを通せませんでした
Diffは、A,Bが灰前半、Cが灰と茶の中間、Dが緑前半、Eが水後半といった感じです。
Eで複雑に考えすぎました...

1-2 A問題 Batting Average

問題

整数$A,B$が与えられるので、$\tfrac{B}{A}$の値を小数第4位で四捨五入した値を出力して下さい。
出力は「整数部分一桁」「小数点」「小数点以下3桁」の順に、末尾の$0$を省略せずに行って下さい。

制約

・$1 \leq A \leq 10$
・$0 \leq B \leq A$

解説

計算は簡単ですが、出力の際の指定が面倒ですね。

プログラムを愚直に書いてもACできますが、各言語には出力の際に桁数を制限する便利な機能があるのでそれを使いましょう。

Pythonでの実装例

A,B=map(int,input().split())
N=B/A
print(f"{N:.3f}")

f文字列と呼ばれるものです。C++のprintfに似ていますね。
競プロでの使用頻度は限られますが便利なので覚えておいても良いでしょう。

C++での実装例

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

int main(){
  double A,B; cin>>A>>B;
  double ans=B/A;
  cout<<fixed<<setprecision(3)<<ans<<endl;
}

これ便利ですね...
printfを使っても書けます。printfかっこいいです。(個人的な感想)

結構手惑いました。

1-3 B問題 Line Sensor

問題

$H×W$のグリッドがあります。上から$i$行目、左から$j$列目のマスを$(i,j)$とします。
各マスの状態は$C_{i,j}$で表され、#の場合箱が一つ置いてあります。

$X_j$を、$j$列目に置いてある箱の数とした時、$X_1,X_2,X_3,...X_W$を求めて下さい。

制約

・$1 \leq H,W \leq 1000$

解説

入力を二次元配列で受け取り、for文を回すだけで解けます。
$X$などの値は配列や辞書型で管理すればよいです。

Pythonでの実装例

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

cnt=[0]*W
for i in range(H):
  for j in range(W):
    if A[i][j]=="#":
      cnt[j]+=1
print(*cnt,sep=" ")

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;
  
  vector<int> ans(W,0);
  vector<vector<char>> A(H,vector<char>(W));
  rep(i,0,H) rep(j,0,W){
    cin>>A[i][j];
    if(A[i][j]=='#'){
      ans[j]++;
    }
  }
  
  rep(i,0,W){
    cout<<ans[i];
    if(i!=W-1){
      cout<<" ";
    }else{
      cout<<endl;
    }
  }
}

やるだけです。

1-4 C問題 Ameba

問題

アメーバの観察記録を付けました。
最初、アメーバは一匹いて、番号は$1$です。
観察記録は時系列順に$N$個あり、「$A_i$のアメーバが二つに分裂した。二つの番号は$2i,2i+1$」というものです。
各$k(1 \leq k \leq 2N+1$)について、アメーバ$k$がアメーバ$1$から何回分裂してできたものか求めて下さい。

制約

・$1 \leq N \leq 2×10^5$

解説

解法1

アメーバの分裂は、アメーバ$1$を根とする木構造を為しています。

これを用いると、頂点$1$から頂点$k$までの最短パスの長さを求めれば、「アメーバ$k$がアメーバ$1$から何回分裂してできたか」が分かります。

木の辺は$A_i$と$2i,2i+1$を結んでおり、木は$O(N)$で構築できます。
木上の最短パスは、BFSによって$2N$個の頂点全てについて求められます。
BFSの計算量は$O(V+E)$($V$は頂点数、$E$は辺の数)となるので、最短距離は$O(N)$で求められます。

全体の計算量は$O(N)$となりこの方法で間に合います。

Pythonでの実装例

from collections import deque
INF=float("INF")

N=int(input())
A=list(map(int,input().split()))
 
G=[[] for _ in range(2*N+1)]
for i in range(N):
  G[A[i]-1].append((i+1)*2-1)
  G[A[i]-1].append((i+1)*2)

dist=[INF]*(2*N+1); dist[0]=0
D=deque(); D.append(0)
while D:
  now=D.popleft()
  for nxt in G[now]:
    if dist[nxt]!=INF:
      continue
    dist[nxt]=dist[now]+1
    D.append(nxt)

print(*dist,sep="\n")

C++での実装例

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

int main(){
  int N; cin>>N;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  vector<vector<int>> G(2*N+5);
  rep(i,0,N){
    G[A[i]-1].push_back((i+1)*2-1);
    G[A[i]-1].push_back((i+1)*2);
  }
  
  vector<int> dist(2*N+1,INF); dist[0]=0;
  deque<int> D; D.push_back(0);
  while(!D.empty()){
    int now=D.front(); D.pop_front();
    for(auto nxt:G[now]){
      if(dist[nxt]!=INF){
        continue;
      }
      dist[nxt]=dist[now]+1;
      D.push_back(nxt);
    }
  }
  
  for(auto i:dist){
    cout<<i<<endl;
  }
}

BFSは頻出のアルゴリズムで、グラフ問題の根幹とも言えるので書けるようになっておきましょう。

解法2

実は、木を構築せず、for文を回すだけでも解くことができます。

当然、アメーバ$A_i$についての答えは、アメーバ$A_i$の親についての答えに$1$を足したものです。
答えをfor文を回しながら配列に格納していけば全ての$k$に対する答えが求められます。

同じく計算量は$O(N)$です。

Pythonでの実装例

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

ans=[0]*(2*N+1)
for i in range(N):
  ans[2*i+1]=ans[A[i]-1]+1
  ans[2*i+2]=ans[A[i]-1]+1
print(*ans,sep="\n")

C++での実装例

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

int main(){
  int N; cin>>N;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  vector<vector<int>> G(2*N+5);
  rep(i,0,N){
    G[A[i]-1].push_back((i+1)*2-1);
    G[A[i]-1].push_back((i+1)*2);
  }
  
  vector<int> dist(2*N+1,INF); dist[0]=0;
  deque<int> D; D.push_back(0);
  while(!D.empty()){
    int now=D.front(); D.pop_front();
    for(auto nxt:G[now]){
      if(dist[nxt]!=INF){
        continue;
      }
      dist[nxt]=dist[now]+1;
      D.push_back(nxt);
    }
  }
  
  for(auto i:dist){
    cout<<i<<endl;
  }
}

この解法の方が簡潔ですね。

1-5 D問題 Robot Arms 2

問題

長さ$N$の正整数列$A$と整数$x,y$が与えられます。
次の条件を全て満たすように、$xy$平面上に$N+1$個の点$p_1,p_2,...p_{N+1}$を配置できるか判定して下さい。

・$p_1=(0,0),p_2=(A_1,0),p_{N+1}=(x,y)$
・$p_i,p_{i+1}$の距離は$A_i$
・$線分p_ip_{i+1}と線分p_{i+1}p_{i+2}の為す角は90°$

制約

・$2 \leq N \leq 10^3$
・$1 \leq A_i \leq 10$
・$|x|,|y| \leq 10^4$

解説

(ここでは、$p_i$から$p_{i+1}$へ点を取ることを移動と呼びます。)

どの方向に$A_i$移動するかを全探索することを考えてみます。
一回の移動につき$2$通りあり、移動は$N$回あるので、$p_{N+1}$としてあり得る点は$2^N$通りとなってしまい、間に合いません。

操作の特徴

ここで操作にどのような特徴があるか考えてみます。
「$線分p_ip_{i+1}と線分p_{i+1}p_{i+2}の為す角は90°$」という条件があります。
これより、一回の操作毎には$x$座標か$y$座標での移動が行われ、それらは交互に行われることが分かりますね。
更に、$p_1=(0,0),p_2=(A_1,0)$という条件より、最初の移動は$x$座標の移動です。

よって、操作はこのように言い換えることが出来ます。

$i$回目の動作では、$i$が奇数ならば$x$座標での移動を行い、そうでなければ$y$座標での移動を行う。

このような操作を$N$回行い、$p_{N+1}$が$(x,y)$となり得るかという判定問題を解く訳です。この判定問題は$x$座標と$y$座標に分けて考えることができます。

分けた判定問題

では、分けた判定問題はどのように解けるでしょうか。
ここでは$x$座標の場合を考えてみます。

$x$座標は、$N×A_i$の最大が$10^4$なので、$-10^4 \leq x \leq 10^4$となり多くとも$2×10^4$通りしか考えられません。
なので、次のようなBool値DPを使うと小さい計算量で解けます。

$DP_{i,j}=i回目の操作の後、x座標はjになり得るか$

遷移はこのようにすればよいです。$i$が奇数の時に限り$x$座標での移動を行うことに注意して下さい。

・$i$が奇数ならば、$DP_{i,j}$が$True$であれば、$DP_{i,j±A_i}$を$True$とする
・そうでないならば、$DP_{i,j}$が$True$であれば、$DP_{i,j}$を$True$とする

$x$座標について解く場合はこのようにし、$y$座標について解く場合は$i$の偶奇を逆にすればよいです。

最後

この判定問題を解き、両方$True$となった場合Yes、そうでない場合Noと出力すればよいです。

判定問題は$DP_{i,j}=i回目の操作の後、x座標はjになり得るか$というものです。
$0 \leq i \leq N, -sum(A) \leq j \leq sum(A)$より、判定問題の計算量は$O(N sum(A))$です。前述の通り、$sum(A)$は$10^4$くらいにしかならないので、これで間に合います。

実装の際、$DP_i$を集合の型とすると、$j$が負となる場合の工夫が無くなり、扱いやすいです。
$i$の偶奇の処理にも気を付けて下さい。

Pythonでの実装例

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

DPx=[set() for _ in range(N+1)]; DPy=[set() for _ in range(N+1)]
DPx[1]={A[0]}; DPy[0]={0};
for i in range(N):
  if i%2==0:
    for j in DPx[i]:
      DPx[i+1].add(j-A[i])
      DPx[i+1].add(j+A[i])
    DPy[i+1]=DPy[i]
  else:
    DPx[i+1]=DPx[i]
    for j in DPy[i]:
      DPy[i+1].add(j-A[i])
      DPy[i+1].add(j+A[i])

if x in DPx[N] and y in DPy[N]:
  print("Yes")
else:
  print("No")

PyPy3で提出すると圧倒的に速かったです。

C++での実装例

#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;
  vector<int> A(N);
  rep(i,0,N) cin>>A[i];
  
  vector<unordered_set<int>> DPx(N+1),DPy(N+1);
  DPx[1].insert(A[0]); DPy[0].insert(0);
  
  rep(i,0,N){
    if(i%2==0){
      for(auto j:DPx[i]){
        DPx[i+1].insert(j-A[i]);
        DPx[i+1].insert(j+A[i]);
      }
      DPy[i+1]=DPy[i];
    }else{
      DPx[i+1]=DPx[i];
      for(auto j:DPy[i]){
        DPy[i+1].insert(j-A[i]);
        DPy[i+1].insert(j+A[i]);
      }
    }
  }
  
  if(DPx[N].count(x) and DPy[N].count(y)){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

unordered_setは平均的に$O(1)$で処理が行えるのでこちらを採用しました。
今回は$N$が小さいので、対数時間掛るsetでもあまり変わりませんでした。

二次元DPを二つの一次元DPにするという工夫、面白いですね。緑Diff前半にしては結構難しかったと思います。 DはDPのDです。

1-6 E問題 Booster

問題

$xy$平面上に$N$個の街($(X_i,Y_i)$)と$M$個の宝箱($(P_i,Q_i)$)があります。
宝箱にはブースターがあり、ブースターを得ると移動速度が$2$倍になります。
原点から$N$個の街へ行き、原点へ戻ってくる旅行を行います。
宝箱を全て訪れる必要はありませんが、街は全て訪れる必要があります。
最初の速度を単位時間辺り$1$とした時、旅行に掛る時間の最小値を求めて下さい。

制約

・$1 \leq N \leq 12$
・$1 \leq M \leq 5$
・$-10^9 \leq X_i,Y_i,P_i,Q_i \leq 10^9$

解説

この問題は巡回セールスマン問題と呼ばれるものに似ています。

巡回セールスマン問題

巡回セールスマン問題とは、$N$個の都市があり、全ての都市をそれぞれ一回ずつ巡り出発地に戻る経路のうち最短のものを求めるという問題です。

都市を巡る順番を全探索するだけでも求められますが、それをすると計算量は$O(N!)$となり、$N=12$くらいで限界が来てしまいます。

しかし、bitDPと呼ばれる手法を使えばもう少し小さい計算量で求めることができます。

bitDP

bitDPは、集合に対して用いるDPです。要素を含むか含まないかをbitの$0,1$で管理することからbitDPと呼ばれています。

巡回セールスマン問題の場合、bitDPは次のように定義します。

$DP_{i,j}=既に訪れた都市を表す集合がiで、現在地がjの時の、それまでの経路の長さの最小値$

遷移は、$i$が小さいものから順に、「$DP_{i,j}$」から、「$DP_{i,j}$から$k(1 \leq k \leq N)$へ訪れた場合」への遷移をすればよいです。
(実装を見た方が分かりやすいです)

計算量は、各$DP_{i,j}$について$N$回のfor文を回すので$O(N^2 2^N)$です。
$N$が小さいうちは$O(N!)$の方が小さかったりしますが、大きくなると$O(N^2 2^N)$の方が圧倒的に小さくなります。
こっちの方だと$N=20$くらいまで耐えられたりします。

今回の問題

今回の問題は、この巡回セールスマン問題に、訪れなくてよい地点と移動速度アップがついたものです。
ですが、この問題もまたbitDPで解くことが出来ます。
移動速度アップに関しても、既に訪れた地点から求めることで、DPの次数を増やさずに済みます。

原点から移動を始め、原点へ戻ってくるということに気を付けて実装して下さい。

Pythonでの実装例

INF=float("INF")

N,M=map(int,input().split())
points=[list(map(int,input().split())) for _ in range(N+M)]
points+=[[0,0]]

def lng(x,y,z):#z回ブーストされた状態でxからyへ移動した時の掛る時間
  a,b=points[x],points[y]
  return ((a[0]-b[0])**2+(a[1]-b[1])**2)**0.5/(2**z)

def boosted(n):#訪れた頂点集合がnの時のブーストされた回数
  ret=0
  for i in range(N,N+M):
    ret+=n>>i&1
  return ret

DP=[[INF]*(N+M) for _ in range(1<<(N+M))]
DP[0][0]=0
for i in range(1<<(N+M)):
  if i==0:
    for j in range(N+M):
      DP[1<<j][j]=lng(N+M,j,0)
  else:
    b=boosted(i)
    for j in range(N+M):
      if not i>>j&1:
        continue
      for k in range(N+M):
        if i>>k&1:
          continue
        DP[i|(1<<k)][k]=min(DP[i][j]+lng(j,k,b),DP[i|(1<<k)][k])

ans=INF
for i in range((1<<N)-1,(1<<(N+M)),1<<N):
  b=boosted(i)
  for j in range(N+M):
    n=DP[i][j]+lng(N+M,j,b)
    ans=min(n,ans)
print(ans)

Pythonだと時間がギリギリめなので、無駄な処理をしないよう気を付けて実装しましょう。
PyPy3で1159ms、PythonだとTLEでした。

C++での実装例

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

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

const double INF=(double)1001001001001;

int N,M;
vector<pair<int,int>> points(20);

double lng(int a,int b,int z){
  int ax,ay,bx,by;
  tie(ax,ay)=points[a]; tie(bx,by)=points[b];
  return pow(pow(ax-bx,2)+pow(ay-by,2),0.5)/pow(2,z);
}

int boosted(int n){
  int ret=0;
  rep(i,N,N+M){
    ret+=n>>i&1;
  }
  return ret;
}

int main(){
  cin>>N>>M;
  rep(i,0,N+M){
    int a,b; cin>>a>>b;
    points[i]=make_pair(a,b);
  }
  points.push_back(make_pair(0,0));
  
  vector<vector<double>> DP(1<<(N+M),vector<double>(N+M,INF));
  
  DP[0][0]=0;
  rep(i,0,1<<(N+M)){
    if(i==0){
      rep(j,0,N+M){
        DP[1<<j][j]=lng(N+M,j,0);
      }
    }else{
      int b=boosted(i);
      rep(j,0,N+M){
        if(!(i>>j&1)){
          continue;
        }
        rep(k,0,N+M){
          if(i>>k&1){
            continue;
          }
          chmin(DP[i|(1<<k)][k],DP[i][j]+lng(j,k,b));
        }
      }
    }
  }
  
  double ans=INF;
  for(int i=(1<<N)-1; i<(1<<(N+M)); i+=(1<<N)){
    int b=boosted(i);
    rep(j,0,N+M){
      double n=DP[i][j]+lng(N+M,j,b);
      chmin(ans,n);
    }
  }
  
  cout<<fixed<<setprecision(10)<<ans<<endl;
}

実装下手です...

普通に難しいです。

DPは複雑すぎると普通に死ぬので気を付けましょう。 EはDPのEです。

2 さいごに

最後までお読み頂きありがとうございます。
今回はDPがDとEで出ましたね。bitDPは低頻度ながら重要なDPなので覚えておきましょう。
E解きたかった...
以上です。
ありがとうございました。
~~いいね下さい。~~