0 はじめに

0-1 記事について

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

1 ABC273 解説

1-1 個人的な感想

冷えました。
Diffは、A問題が灰前半、B問題が灰後半、C問題が茶前半、D問題が緑後半、E問題が青前半といった感じです。
私は80分で四冠したので久し振りに緑Perfとなり、4程冷えました。。
9分で三冠していたので情けないです。

1-2 A問題 A Recursive Function

問題

非負整数$x$の関数$f(x)$は次を満たします。

・$f(0)=1$
・任意の正整数$k$について、$f(k)=k・f(k-1)$

$f(N)$を求めて下さい。

制約

・$1 \leq N \leq 10$

解説

問題を言い換えると、$N$の階乗を求めろということです。
よって、定義より、$N$の階乗は$1$から$N$までの自然数の総積なので、for文を使えば解けます。

Pythonでの実装例

N=int(input())
ans=1
for i in range(1,N+1):
  ans*=i
print(ans)

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=1;
  rep(i,1,N+1){
    ans*=i;
  }
  cout<<ans<<endl;
}

int型でも通ります。($10 \geq N$より、最大でも$3628800$です。)

問題名を和訳すると再帰関数です。
再帰関数でも通りますがfor文の方が賢明です。

1-3 B問題 Broken Rounding

問題

非負整数$X$に対し、$i=0,1,...K-1$の順に次の動作を行った時、最終的な$X$の値を求めて下さい。

・$X$の$10^i$の位以下を四捨五入する。

制約

・$0 \leq X < 10^{15}$
・$1 \leq K \leq 15$

解説

四捨五入を何回も行う操作ですね。
四捨五入は各言語の標準ライブラリに一応あります。
整数$n$を$10^i$の位以下を四捨五入するには、$n$を$10^i$で割った値を整数に四捨五入すればよいです...

が、小数にしてしまうと誤差の影響を受けてしまう可能性があるので、自分で四捨五入の関数を作りましょう。

$n$の$10^i$の位以下を四捨五入するという動作は「$n$の$10^i$の位以下の部分を$m$とし、$m$が$10^i$の半分より大きければ切り上げ、そうでなければ切り下げる」と言い換えられます。
数学的にはこう表せます。(四捨五入した値$=n_2$とする)

・$m=mod(n,10^{i+1})$ ($mod(a,b)はaをbで割った余り$)
・$m<5・10^i$ならば、$n_2=n-m$ (切り下げ)
・そうでないなら$n_2=n-m+10^{i+1}$ (切り上げ)

これをそのまま実装すればよいです。

Pythonでの実装例

X,K=map(int,input().split())

def calc(m,i):
  m=m%(10**(i+1))
  if m<(10**i)*5:
    return m-m
  else:
    return m-m+(10**(i+1))

for i in range(K):
  X=calc(X,i)
print(X)

C++での実装例

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

ll pw(ll x,int n){
  ll ret=1LL;
  rep(i,0,n){
    ret*=x;
  }
  return ret;
}

ll calc(ll N,int i){
  i=(double)i;
  ll n=N%pw(10LL,i+1);
  if(n<pw(10LL,i)*5){
    return N-n;
  }else{
    return N-n+pw(10LL,i+1);
  }
}

int main(){
  ll X; int K; cin>>X>>K;
  
  rep(i,0,K){
    X=calc(X,i);
  }
  
  cout<<X<<endl;
}

$X$の最大値はほぼ$10^{15}$なのでC++の場合long longを使いましょう。
又、累乗の関数powは小数で返って来て面倒なので、自分で関数を作りました。

こういう問題に備え、四捨五入もライブラリにあると便利かも知れませんね。

1-4 C問題 (K+1)-th Largest Number

問題

長さ$N$の整数列$A$が与えられます。
$K=0,1,2,...N-1$について、次の小問題に答えて下さい。

$A$の中で、$A_i$より大きい数が$K$種類ある時、$i$として考えられる数はいくつありますか?

制約

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

解説

愚直に計算すると$O(N^2)$掛かってしまい、間に合いません。
工夫をします。

$A_i$より大きい数が$A$に$K$種類あるならば、$A_i$は$A$の中で$K+1$番目に大きいです。従って、小問題は、「$K+1$番目に大きい数はいくつあるか」と言い換えられます。

($B$を、$A$から重複を除いたものとします)
それぞれの数が数列内にいくつあるかを格納する辞書型を用意し、$B$の降順にその辞書型を参照していけばよいです。
又、これだと$K \leq Bの要素数$の場合のみしか出力されないので、$N-Bの要素数$回$0$を出力します。

辞書型の用意に$O(N)$、ソートに$O(N log N)$掛かるので全体の計算量は$O(N log N)$で間に合うます。

Pythonでの実装例

from collections import Counter

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

cnt=Counter(A)
B=sorted(list(set(A)))[::-1]
for n in B:
  print(cnt[n])
for i in range(N-len(B)):
  print(0)

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;
  
  vector<int> A(N),B;
  map<int,int> cnt;
  rep(i,0,N){
    cin>>A[i];
    if(!cnt.count(A[i])){
      B.push_back(A[i]);
    }
    cnt[A[i]]++;
  }
  
  sort(B.rbegin(),B.rend());
  for(auto n:B){
    cout<<cnt[n]<<endl;
  }
  rep(i,0,N-B.size()){
    cout<<0<<endl;
  }
}

辞書型の前処理で$O(N^2)$を$O(N)$にする問題です。辞書型の扱いに慣れておきましょう。

1-5 D問題 LRUD Instructions

問題

$H×W$のグリッドがあります。上から$i$行目、左から$j$列目にあるますを$(i,j)$と表します。
$N$個のマスには障害物があり進めません。
最初あなたはマス$(r_s,c_s)$にいます。
$Q$個のクエリが与えられます。

$d_i$の方向に、障害物に衝突するまで$l_i$マス進んで下さい。

それぞれのクエリを終えた後のいるマスを出力して下さい。

制約

・$2 \leq H,W \leq 10^9$
・$1 \leq r_s \leq H, 1 \leq c_s \leq W$
・$0 \leq N \leq 2×10^5$
・$1 \leq r_i \leq H, 1 \leq c_i \leq W$
・$(r_s,c_s)$と$(r_i,c_i)$に重複はない
・$1 \leq Q \leq 10^5$
・$1 \leq l_i \leq 10^9$

解説

愚直に移動を何回も行ってしまうと計算量は$O(\sum l)$で、明らかに間に合いません。
工夫を施しましょう。

移動のクエリは、「$l_i$個先までに障害物があればその手前で止まり、なければ$l_i$個先に進む」です。
L,R,U,Dを行った後のマスはこのように表せます。($(x,y)$を現在地とする)

L : $(x,max(y-d,yより左にある最も近い障害+1)$
R : $(x,min(y+d,yより右にある最も近い障害-1)$
U : $(max(x-d,xより上にある最も近い障害+1),y)$
D : $(min(x+d,xより下にある最も近い障害-1),y)$

求めるべき、「～より左/右にある最も近い障害」は、各行・列にある障害のマスを格納した配列を二分探索することで求められます。(その行・列に障害物がなければそのまま進めばよいです。)

各行・列にある障害のマスを格納する前計算で$O(N log N)$かかります。
(ソートするので$O(N)$ではないです)
クエリは、一回につき、大きさが最大$N$の配列を二分探索するので$(log N)$掛かります。
合計計算量は$O((N+Q) log N)$で、間に合います。

これを実装すればよいです。
二分探索をする部分はPythonではbisect.bisect_left、C++ではstd::lower_boundを用いましょう。
又、移動によってグリッドの外に出ないようにも気を付けましょう。
$(i,j)$として、$1 \leq i \leq H, 1 \leq j \leq W$です。

Pythonでの実装例

import sys
def input():
  return sys.stdin.readline().rstrip()
from bisect import bisect_left as bile

H,W,rs,cs=map(int,input().split())
N=int(input())
xn,yn={},{} #xn[x]はx行目、yn[y]はy列目に存在する障害物
xs,ys=set(),set() #xs,ysは障害物のない行、列
for i in range(N):
  x,y=map(int,input().split())
  xs.add(x); ys.add(y)
  xn.setdefault(x,[]); xn[x].append(y)
  yn.setdefault(y,[]); yn[y].append(x)

for i in xn.keys():
  xn[i].sort()
for i in yn.keys():
  yn[i].sort()

Q=int(input())
x,y=rs,cs #現在地
for i in range(Q):
  d,l=input().split(); l=int(l)
  
  if d=="L":
    if x not in xs:
      y-=l
    else:
      ind=bile(xn[x],y)-1
      if ind==-1: #左に障害物がない
        y-=l
      else:
        y=max(y-l,xn[x][ind]+1)
  elif d=="R":
    if x not in xs:
      y+=l
    else:
      ind=bile(xn[x],y)
      if ind==len(xn[x]): #右に障害物がない
        y+=l
      else:
        y=min(y+l,xn[x][ind]-1)
  elif d=="U":
    if y not in ys:
      x-=l
    else:
      ind=bile(yn[y],x)-1
      if ind==-1: #上に障害物がない
        x-=l
      else:
        x=max(x-l,yn[y][ind]+1)
  else:
    if y not in ys:
      x+=l
    else:
      ind=bile(yn[y],x)
      if ind==len(yn[y]): #下に障害物がない
        x+=l
      else:
        x=min(x+l,yn[y][ind]-1)
  x=max(1,min(x,H))
  y=max(1,min(y,W))
  print(x,y)

結構時間がかかります。
入力量が多いので、input()よりも高速な入力ツールを使っています。

C++での実装例

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

int main(){
  int H,W,rs,cs; cin>>H>>W>>rs>>cs;
  int N; cin>>N;
  map<int,vector<int>> xn,yn;
  set<int> xs,ys;
  rep(i,0,N){
    int x,y; cin>>x>>y;
    xs.insert(x); ys.insert(y);
    xn[x].push_back(y);
    yn[y].push_back(x);
  }
  
  for(auto i:xs) sort(all(xn[i]));
  for(auto i:ys) sort(all(yn[i]));
  
  int Q; cin>>Q;
  int x=rs,y=cs;
  rep(i,0,Q){
    char d; int l; cin>>d>>l;
    int ind;
    if(d=='L'){
      if(!xs.count(x)) y-=l;
      else{
        ind=lower_bound(all(xn[x]),y)-xn[x].begin();
        if(ind==0){ //左に障害物がない
          y-=l;
        }else{
          y=max(y-l,xn[x][ind-1]+1);
        }
      }
    }else if(d=='R'){
      if(!xs.count(x)) y+=l;
      else{
        ind=lower_bound(all(xn[x]),y)-xn[x].begin();
        if(ind==xn[x].size()){ //右に障害物がない
          y+=l;
        }else{
          y=min(y+l,xn[x][ind]-1);
        }
      }
    }else if(d=='U'){
      if(!ys.count(y)) x-=l;
      else{
        ind=lower_bound(all(yn[y]),x)-yn[y].begin();
        if(ind==0){ //上に障害物がない
          x-=l;
        }else{
          x=max(x-l,yn[y][ind-1]+1);
        }
      }
    }else{
      if(!ys.count(y)) x+=l;
      else{
        ind=lower_bound(all(yn[y]),x)-yn[y].begin();
        if(ind==yn[y].size()){ //下に障害物がない
          x+=l;
        }else{
          x=min(x+l,yn[y][ind]-1);
        }
      }
    }
    x=max(1,min(x,H));
    y=max(1,min(y,W));
    cout<<x<<" "<<y<<endl;
  }
}

C++の二分探索難しくないですか？

実装が結構重く大変ですね。

1-6 E問題 Notebook

問題

整数列$A$と$10^9$ページのノートがあります。
$Q$個のクエリが与えられます。クエリは次のうちどれかです。

ADD x : xを整数列の末尾に追加する。
DELETE : 空でなければ、整数列の末尾の要素を削除する。
SAVE y : yページを整数列$A$で上書きする。
LOAD z : 整数列$A$をzページに書いてあるものに変更する。

最初、$A$と全てのノートのページは空です。$Q$個のクエリを順に実行し、それぞれのクエリを終えた後、$A$の末尾の数を出力して下さい。($A$が空であれば-1)

制約

・$1 \leq Q \leq 5×10^5$
・$1 \leq x,y,z \leq 10^9$

解説

ノートの情報を一つ一つ格納する変数を作っても、MLEかTLEが出てしまいます。
工夫が必要です。

一回のクエリ毎に、整数を加えたり、前の情報に戻ったり、前の$A$に置き換えたりします。
それには木構造が使えそうです。

どのようにすれば少ない処理量でクエリを実行できるか考えてみます。

頂点には整数が一つずつ書かれており、一番上の親からその頂点まで最短で辿ると、その頂点を末尾とする数列が得られるような根付き木が望ましいです。

これを用いると、各クエリはこのように実現できます。

ADD x : 現在見ている頂点にxの書かれた子を付ける
DELETE : 見ている頂点の親へ移動する
SAVE y : yページに、見ている頂点を記録する
LOAD z : zページに記録した頂点へ移動する

こうすると、それぞれのクエリにつき$O(1)$で処理できます。
全体の計算量は$O(Q)$で間に合います。

Pythonでの実装例

import sys
def input():
  return sys.stdin.readline().rstrip()

Q=int(input())

pr={0:0} #親
num={0:-1} #頂点に書かれた数
to={} #nページに保存されている頂点
seen=set() #頂点が保存されたページ
now=0 #現在見ている頂点
ans=[]
for i in range(Q):
  query=input().split()
  s=query[0]
  
  if s=="ADD":
    x=query[1]
    nxt=len(num)
    num.setdefault(nxt,0); num[nxt]=x;
    pr.setdefault(nxt,0); pr[nxt]=now;
    now=nxt
  elif s=="DELETE":
    now=pr[now]
  elif s=="SAVE":
    y=query[1]
    to.setdefault(y,0); to[y]=now
    seen.add(y)
  else:
    z=query[1]
    if z in seen:
      now=to[z]
    else:
      now=0
  ans.append(num[now])

print(*ans,sep=" ")

入力の高速化をしましょう。

C++での実装例

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

int main(){
  ios::sync_with_stdio(false);
  
  int Q; cin>>Q;
  
  map<int,int> pr,num,to; //親、頂点に書かれた数、nページに保存されている頂点
  pr[0]=0; num[0]=-1; //根の初期化
  set<int> seen; //頂点の保存されたページ
  int now=0; //見ている頂点
  
  rep(i,0,Q){
    string s; cin>>s;
    if(s=="ADD"){
      int x; cin>>x;
      int nxt=num.size();
      num[nxt]=x;
      pr[nxt]=now;
      now=nxt;
    }else if(s=="DELETE"){
      now=pr[now];
    }else if(s=="SAVE"){
      int y; cin>>y;
      to[y]=now;
      seen.insert(y);
    }else{
      int z; cin>>z;
      if(seen.count(z)){
        now=to[z];
      }else{
        now=0;
      }
    }
    cout<<num[now]<<endl;
  }
}

std::ios::sync_with_stdio(false)で入力を高速化できるらしいです。

青Diffなだけあって思いつくのは相当難しいです。解けませんでした。

2 さいごに

最後までお読み頂きありがとうございます。
今回はD問題で実装ゲーが出て失敗した方($∋私$)多かったのではないでしょうか。
二分探索は頻出のアルゴリズムなので覚えておきましょう。
Eは知りません。難しいです。閃きゲーでしたね。
以上です。
よい競プロライフを!