Help us understand the problem. What is going on with this article?

Codeforces Round #481 (Div. 3) バチャ復習(9/24)

今回の成績

スクリーンショット 2020-09-24 14.26.02.png

今回の感想

今回はあまりバグらせずに通すことができました。良い傾向なので、引き続き頑張りたいと思います。

一部詰まる部分はありましたが今回のような安定したムーブが毎回できることを目標に頑張りたいです。

A問題

数列の右側から見て同じ数が二回現れないように取ってくれば良いです。したがって、数列の右側から数を見ていき、どの数が現れたかをsetの$s$に保存します。この時、$s$に含まれていない場合は答えで出力する配列ansに挿入し、含まれている場合は次の数を見ます。

A.py
n=int(input())
a=list(map(int,input().split()))[::-1]
s={a[0]}
ans=[str(a[0])]
for i in range(1,n):
    if a[i] not in s:
        s.add(a[i])
        ans.append(str(a[i]))
print(len(ans))
print(" ".join(ans[::-1]))

B問題

文字列は以下のように$x$が連続している部分と連続してない部分に分けることができます。

IMG_0647.JPG

この$x$が連続している部分の長さ$l$をそれぞれ2以下にすることができれば題意を満たします。また、これに必要な削除の最小回数は$min(0,l-2)$で求められるので、$x$がどれだけ連続するかをそれぞれチエックします。ここで、$x$の連続する部分についてはgroupby関数を使えば以下のように簡単に求めることができます。

B.py
from itertools import groupby
n=int(input())
s=[]
for i in groupby(input(),lambda x:x=="x"):
    s.append(list(i[1]))
#s=list(groupby(input(),lambda x:x=="x"))
ans=0
for i in s:
    if i[0]=="x":
        ans+=max(0,len(i)-2)
print(ans)

C問題

全ての寮に対しての部屋番号からそれぞれの寮の番号と寮内での部屋番号を復元する問題です。とりあえず、番号がどうなっているかを把握するために全ての寮に対しての部屋番号を以下のように書き出しました。

IMG_0649.jpg

また、それぞれの寮の部屋番号が最も小さい部屋に注目すると、$1 \rightarrow 1+a_1\rightarrow 1+a_1+a_2 \rightarrow … \rightarrow 1+a_1+a_2+…+a_{n-1}$と累積和になっているので、これを配列$s$として保存しておきます。この時、与えられた部屋番号を$b_i$とすれば、どの寮にいるかは配列$s$内で$b_i$以下で最大の要素のインデックスに対応します($bisect$_$right$)。また、その寮内での部屋番号は$b_i$から先ほど求めた最大の要素との差を考えれば良いだけです。

上記を任意の$i$に対して行えば$O(m \log{n})$でこの問題を解くことができます。

C.py
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from itertools import accumulate
s=list(accumulate([1]+a))[:-1]
from bisect import bisect_right
#print(s)
ans=[]
for i in range(m):
    c=bisect_right(s,b[i])-1
    #print(c)
    ans.append(str(c+1)+" "+str(b[i]-s[c]+1))
for i in range(m):
    print(ans[i])

D問題

やることの見えていた問題ではありますが自分的にはかなり早くコードの実装をできたので、最近のバチャの成果を少しだけ感じました。

貪欲に考えると自由度が高いので、どこかを固定して考えようと思いました。この時、自分は両端を固定して考えることにしました。この時、$a[0],a[n-1]$の両端は$-1,0,+1$のいずれかの変化しかせず合計9通りの場合が存在します。

よって、両端の変化をさせた元での操作回数を返す関数$check$を定義することを以下では考えます。まず、変化後の$a[0],a[n-1]$に対して題意のように等差数列にするには$abs(a[n-1]-a[0])$が$n-1$の倍数であることが必要です($n-1$の倍数でない場合は$inf$を返します。)。この時の公差は$\frac{a[n-1]-a[0]}{n-1}$になります。したがって、$a[1]-a[0],a[2]-a[1],…,a[n-1]-a[n-2]$が全て$\frac{a[n-1]-a[0]}{n-1}$となるかどうかを前から貪欲に調べていきます。この時、$+1,-1$のいずれかの変化をして$\frac{a[n-1]-a[0]}{n-1}$となる場合はその変化を貪欲に行い、変える操作をカウントします。また、$+1,0,-1$のいずれの変化でも公差が$\frac{a[n-1]-a[0]}{n-1}$とならない要素があった場合はその時点で$inf$を返します。また、上記の判定をいずれもクリアした場合はカウントした操作の回数を返します。

以上より、9通りのそれぞれの場合の操作回数を求めることができ、最小値を出力します。また、最小値が$inf$になる場合は条件を満たさないので、-1を出力します。

また、自分の実装だと両端での操作回数を数えないミスが発生しうるので注意が必要です。さらに、場合分けが面倒だと思ったので、$n=1,2$の場合は先に0を出力しておきました。加えて、公差が負の場合にミスをしそうだと感じたので、その場合は反転して公差を非負にするようにしました。

D.py
n=int(input())
b=list(map(int,input().split()))
if n==1 or n==2:
    print(0)
    exit()
inf=10**12
#x,yはchangeの量(0,-1,+1),9通り
def check(x,y):
    global b,n
    ret=0
    if x!=0:
        ret+=1
    if y!=0:
        ret+=1 
    a=[i for i in b]
    a[0]+=x
    a[n-1]+=y
    #昇順に
    if a[n-1]<a[0]:
        a=a[::-1]
    if (a[n-1]-a[0])%(n-1)!=0:
        return inf
    d=(a[n-1]-a[0])//(n-1)
    for i in range(n-1):
        if a[i+1]-a[i]==d:
            pass
        elif a[i+1]-a[i]==d+1:
            a[i+1]-=1
            ret+=1
        elif a[i+1]-a[i]==d-1:
            a[i+1]+=1
            ret+=1
        else:
            return inf
    return ret

ans=inf
for i in range(-1,2):
    for j in range(-1,2):
        ans=min(ans,check(i,j))
        #print(i,j,check(i,j))
if ans==inf:
    print(-1)
else:
    print(ans)

E問題

考え忘れていたケースがあって2WAを出したので反省しています。冷静に考えれば少なくとも1WAに抑えられていたはずです。

まずは、どんな値であれば成り立つのかを考えるために、初めに$x$だけの人を載せていたとして条件を考えます。この時、$i$番目のバス停で人数の変化は$a_i$なので、それぞれのバス停を通過した後に$x+a_0,x+a_0+a_1,…,x+a_0+a_1+…+a_{n-1}$だけの人が乗っています。よって、これらが全て0以上$w$以下になれば良い(✳︎)ことがわかります。よって、$a_0,a_0+a_1,…,a_0+a_1+…+a_{n-1}$を累積和で求め、この中の最大値と最小値をそれぞれ$u,d$とします。ここで、$x+u \leqq w$かつ$x+d \geqq 0$を満たしていれば任意のバス停を通過した時に(✳︎)を満たします(最大値と最小値のみに注目!)。また、$0 \leqq x \leqq w$も満たす必要があります(これを忘れていたために2WAでした、勿体ないです。)。したがって、$x+u \leqq w$かつ$x+d \geqq 0$かつ$0 \leqq x \leqq w$を満たすので、これを全てマージすれば$max(0,-d) \leqq x \leqq min(w,w-u)$を満たすような整数$x$の個数を求めればよく、共通部分がない場合も考慮すれば$min(0,min(w,w-u)-max(0,-d)+1)$となります。

(上記ではまとまった考察ができており実装も簡潔ですが、コンテスト中は汚い実装と考察になってしまいました。反省です。)

E.py
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
print(max(0,min(w,w-u)-max(0,-d)+1))
E2.py
#コンテスト中の実装
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
if u-d>w:
    print(0)
    exit()
if u>w:
    print(0)
    exit()
ran=[max(0,-d),min(w,w-u)]
if ran[1]<ran[0]:
    print(0)
    exit()
print(ran[1]-ran[0]+1)

F問題

初めに誤読しかけたので危なかったです。まず、問題設定として、$a,b$の二人がいた時に$r_a>r_b$かつ$a,b$が口論をしていなければ$a$は$b$のメンターをすることができます。

ここで、一つ目の条件のみであれば、$r$の値を昇順に持つことで$bisect$_$left$でインデックスを取ってきて簡単に求められます(大小は昇順で並べて数える!)。また、一つ目の条件を考えた後に二つ目の条件を加えると、一つの条件を満たしながら口論している人を除くとすれば良いこともわかります。

よって、$i$番目の人($r_i$)がメンターをできる相手の人数は、(①$r_i$よりスキルが低い人の人数)-(②$r_i$よりスキルが低いが口論をしている人の人数)となります。また、$check[i]:=$($i$番目の人が口論している中で$r_i$よりスキルが低い人の人数)、$p:=$(それぞれの人が持つスキルを順に並べた配列)とおけば、$check$は口論する人の組を受け取った時点で数えられ、$p$も入力を並べ替えるだけです。よって、①は$bisect$_$left(p,r_i)$をした際のインデックス(0-indexed)が相当し、②は$check[i]$が相当します。

以上より、$i$を順に動かして答えを配列$ans$に格納し、最終的に答えとして出力します。また、計算量は$O(k+n \log{n})$です。

F.py
n,k=map(int,input().split())
r=list(map(int,input().split()))
check=[0]*n
for i in range(k):
    x,y=map(int,input().split())
    x-=1
    y-=1
    if r[x]>r[y]:
        check[x]+=1
    if r[y]>r[x]:
        check[y]+=1
from bisect import bisect_left
ans=[0]*n
p=sorted(r)
for i in range(n):
    b=bisect_left(p,r[i])
    ans[i]=str(b-check[i])
print(" ".join(ans))

G問題

計算量に余裕がありすぎたのと問題文が長いので勘繰ってしまいましたが、実装をするだけで拍子抜けしました。また、実装をするだけだったにもかかわらず30分程度解くのにかかってしまったので、半分くらいの時間で通せるように努力したいです。

まず、見落としがちな点を問題文から抜粋すると以下の二つになります。

・複数の試験を一日に受け取ることはできないが、問題の制約上そのような入力はない
・準備は連続している必要はない

この時、最も試験日の近い試験から準備する貪欲法で行けるのではないかと思いました。遠い試験日を先に順に準備する際のメリットがないので、この貪欲法は正しいです。また、これは遠い試験日を先に準備したとしてもそれよりも近い試験日の準備と入れ替えられることからも示せます。よって、以下ではこの貪欲法を実装します。

まず、以下の四つのデータ構造を用意します。それぞれが必要な理由は後述します。また、①と②を初期化する必要がありますが、これは入力を受け取った後に簡単に処理できるので説明は省きます。

①配列$exams[i]:=$($i$日目に準備を始められる試験の(試験日,必要な準備日数)を保持した配列)
②配列$ind[i]:=$($i$日目が試験日の試験の入力での受け取り順,ただし試験日がない場合は-1)
③配列$ans[i]:=$($i$日目の出力すべき答え)
④集合$cand:=$(準備のできる試験の(試験日,必要な準備日数)を保持した配列)

まず、試験日の近い試験から準備をするために試験日の昇順で保持する④を用意します。これにより、それぞれの日では$cand$の最小の要素から順に準備していけば良いです。また、$i$日目に新たに準備を始められる試験が増えます。これは、①を用意すれば、$cand$に$exams[i]$の中身をすべて挿入するだけです。次に、その日が試験日である場合は準備ができないので、$ans[i]$を$m+1$にして次の日を考えます。これは、②を用意しておけば$ind[i]$が-1かどうかで判定することができ、$ind[i]$が-1でない場合は次の操作を考えます。

以上の判定を行った元で準備を行うことを考えますが、$cand$が空である可能性があります。この際は準備が行えないので$ans[i]=0$として次の日を考えます。そして、準備を行います。準備を行う際、見れば良いのは$cand$の最小の試験のみです(コンテスト中には気づかなかったため若干実装量が増えました。)。また、その試験の試験日がすでに過ぎている場合は準備が間に合ってないので、-1を出力してプログラムを終了します。それ以外の場合はその試験の対策をすればよく$ans[i]$にはその試験の入力での受け取り順を$ind$を用いて代入します。また、その試験の対策を行ってもまだ準備が必要な場合は$cand$から削除した後に必要な準備日数を-1して再度挿入します。

以上を全ての日で行った後に$ans$を出力すれば良いですが、まだ$cand$に要素が残っている可能性を考慮しなければなりません。この場合は準備が間に合ってない試験があるのと同義なので-1を出力します。それ以外の場合については試験の準備が全ての試験について間に合っているので$ans$を出力します。

(下記のコードは無駄のないように実装してあり上記の考察も無駄のないようにしていますが、コンテスト中はもう少し条件分岐などが多く間違いうるコードでした。反射神経で動くのも良いですが、もう少し考察を深めてから実装した方が良いかもしれません。)

G.cc
//デバッグ用オプション:-fsanitize=undefined,address

//コンパイラ最適化
#pragma GCC optimize("Ofast")

//インクルードなど
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
//FORAは範囲for文(使いにくかったら消す)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

signed main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<vector<ll>> exams(n);
    //準備できた日に対して
    vector<vector<pair<ll,ll>>> preparation(n);
    //試験日に対してのind
    vector<ll> ind(n,-1);
    REP(i,m){
        ll s,d,c;cin>>s>>d>>c;
        exams[i]={s-1,d-1,c};
        ind[d-1]=i;
        preparation[s-1].PB(MP(d-1,c));
    }
    vector<ll> ans(n,-1);
    set<pair<ll,ll>> cand;
    REP(i,n){
        REP(j,SIZE(preparation[i])){
            cand.insert(preparation[i][j]);
        }
        if(ind[i]!=-1){
            ans[i]=m+1;
            continue;
        }
        if(SIZE(cand)==0){
            ans[i]=0;
            continue;
        }
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S==0){
                j=cand.erase(j);
            }else{
                if(j->F<i){
                    cout<<-1<<endl;
                    return 0;
                }
                ans[i]=ind[j->F]+1;
                pair<ll,ll> p=*j;p.S-=1;
                cand.erase(j);
                if(p.S!=0){
                    cand.insert(p);
                }
                break;
            }
        }
        if(ans[i]==-1)ans[i]=0;
    }
    if(SIZE(cand)==0){
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }else{
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S!=0){
                cout<<-1<<endl;
                return 0;
            }
        }
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }

}
DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away